Affiliated with RCfalse
A Novel and Fast SimRank Algorithm
Juan Lu1; Zhiguo Gong1; Xuemin Lin2,3
2017-02-02
Source PublicationIEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
ISSN1041-4347
Volume29Issue:3Pages:572-585
Abstract

SimRank is a widely adopted similarity measure for objects modeled as nodes in a graph, based on the intuition that two objects are similar if they are referenced by similar objects. The recursive nature of SimRank definition makes it expensive to compute the similarity score even for a single pair of nodes. This defect limits the applications of SimRank. To speed up the computation, some existing works replace the original model with an approximate model to seek only rough solution of SimRank scores. In this work, we propose a novel solution for computing all-pair SimRank scores. In particular, we propose to convert SimRank to the problem of solving a linear system in matrix form, and further prove that the system is non-singular, diagonally dominate, and symmetric definite positive (for undirected graphs). Those features immediately lead to the adoption of Conjugate Gradient (CG) and Bi-Conjugate Gradient (BiCG) techniques for efficiently computing SimRank scores. As a result, a significant improvement on the convergence rate can be achieved; meanwhile, the sparsity of the adjacency matrix is not damaged all the time. Inspired by the existing common neighbor sharing strategy, we further reduce the computational complexity of the matrix multiplication and resolve the scalable issues. The experimental results show our proposed algorithms significantly outperform the state-of-the-art algorithms.

KeywordSimrank Linear System Conjugate Gradient
DOI10.1109/TKDE.2016.2626282
URLView the original
Indexed BySCIE
Language英語English
WOS Research AreaComputer Science ; Engineering
WOS SubjectComputer Science, Artificial Intelligence ; Computer Science, Information Systems ; Engineering, Electrical & Electronic
WOS IDWOS:000395563900008
PublisherIEEE COMPUTER SOC
The Source to ArticleWOS
Fulltext Access
Citation statistics
Cited Times [WOS]:8   [WOS Record]     [Related Records in WOS]
Document TypeJournal article
CollectionDEPARTMENT OF COMPUTER AND INFORMATION SCIENCE
Affiliation1.University of Macau, Taipa, Macau, China.
2.East China Normal University, Huashida, Putuo 200062, China
3.University of New South Wales, Sydney, NSW 2052, Australia
First Author AffilicationUniversity of Macau
Recommended Citation
GB/T 7714
Juan Lu,Zhiguo Gong,Xuemin Lin. A Novel and Fast SimRank Algorithm[J]. IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,2017,29(3):572-585.
APA Juan Lu,Zhiguo Gong,&Xuemin Lin.(2017).A Novel and Fast SimRank Algorithm.IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,29(3),572-585.
MLA Juan Lu,et al."A Novel and Fast SimRank Algorithm".IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 29.3(2017):572-585.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Juan Lu]'s Articles
[Zhiguo Gong]'s Articles
[Xuemin Lin]'s Articles
Baidu academic
Similar articles in Baidu academic
[Juan Lu]'s Articles
[Zhiguo Gong]'s Articles
[Xuemin Lin]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Juan Lu]'s Articles
[Zhiguo Gong]'s Articles
[Xuemin Lin]'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.