UM  > 科技學院  > 電腦及資訊科學系
A Novel and Fast SimRank Algorithm
Lu, Juan1; Gong, Zhiguo1; Lin, Xuemin2,3
2017-03
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 BySCI
Language英语
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]:2   [WOS Record]     [Related Records in WOS]
Document TypeJournal article
CollectionDEPARTMENT OF COMPUTER AND INFORMATION SCIENCE
Affiliation1.Univ Macau, Dept Comp & Informat Sci, Taipa, Macau, Peoples R China
2.East China Normal Univ, Huashida 200062, Putuo, Peoples R China
3.Univ New South Wales, Sch Comp Sci & Engn, Sydney, NSW 2052, Australia
First Author AffilicationUniversity of Macau
Recommended Citation
GB/T 7714
Lu, Juan,Gong, Zhiguo,Lin, Xuemin. A Novel and Fast SimRank Algorithm[J]. IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,2017,29(3):572-585.
APA Lu, Juan,Gong, Zhiguo,&Lin, Xuemin.(2017).A Novel and Fast SimRank Algorithm.IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,29(3),572-585.
MLA Lu, Juan,et al."A Novel and Fast SimRank Algorithm".IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 29.3(2017):572-585.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Lu, Juan]'s Articles
[Gong, Zhiguo]'s Articles
[Lin, Xuemin]'s Articles
Baidu academic
Similar articles in Baidu academic
[Lu, Juan]'s Articles
[Gong, Zhiguo]'s Articles
[Lin, Xuemin]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Lu, Juan]'s Articles
[Gong, Zhiguo]'s Articles
[Lin, Xuemin]'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.