A matrix sampling approach for efficient SimRank computation
Lu,Juan1; Gong,Zhiguo2; Yang,Yiyang3
Source PublicationInformation Sciences
AbstractEvaluating similarities between node pairs in a graph is an important task for data analytics and mining. Among various similarity measures proposed in recent years, SimRank is regarded as one of the most influential measures. However, the computation of SimRank is very expensive especially for large graphs. Although pruning technique and random walk based methods were proposed to accelerate the computation, the accuracy of SimRank score is still very low. In this paper, we propose a novel matrix random sampling approach to accelerate computation speed and reduce memory cost. The matrix random sampling technique not only guarantees the sparsity of the involved matrices, but also enhances the precision of estimated SimRank scores. Moreover, we design a fast sparse matrix–matrix multiplication technique which makes the time complexity of single-source query free of the graph size. We further exploit the Steepest Decent technique to accelerate the speed of convergence. The experimental results show our proposed algorithms outperform the state-of-the-art SimRank algorithms.
KeywordMatrix sampling SimRank Steepest descent
URLView the original
Fulltext Access
Citation statistics
Cited Times [WOS]:0   [WOS Record]     [Related Records in WOS]
Document TypeJournal article
CollectionUniversity of Macau
Corresponding AuthorLu,Juan
Affiliation1.Beijing Institute of Petrochemical Technology,Beijing,China
2.University of Macau,Macau,China
3.GuangDong University of Technology,Guangzhou,China
Recommended Citation
GB/T 7714
Lu,Juan,Gong,Zhiguo,Yang,Yiyang. A matrix sampling approach for efficient SimRank computation[J]. Information Sciences,2021,556:1-26.
APA Lu,Juan,Gong,Zhiguo,&Yang,Yiyang.(2021).A matrix sampling approach for efficient SimRank computation.Information Sciences,556,1-26.
MLA Lu,Juan,et al."A matrix sampling approach for efficient SimRank computation".Information Sciences 556(2021):1-26.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Lu,Juan]'s Articles
[Gong,Zhiguo]'s Articles
[Yang,Yiyang]'s Articles
Baidu academic
Similar articles in Baidu academic
[Lu,Juan]'s Articles
[Gong,Zhiguo]'s Articles
[Yang,Yiyang]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Lu,Juan]'s Articles
[Gong,Zhiguo]'s Articles
[Yang,Yiyang]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.