A Novel and Fast SimRank Algorithm

UM > Faculty of Science and Technology > DEPARTMENT OF COMPUTER AND INFORMATION SCIENCE

Status	已發表Published
	A Novel and Fast SimRank Algorithm
	Lu, J.; Gong, Z. G.; Lin, X.
	2017-03-01
Source Publication	IEEE Transactions on Knowledge and Data Engineering
ISSN	1041-4347
Pages	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 CG (Conjugate Gradient) and BiCG (Bi-Conjugate Gradient) 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.
Keyword	SimRank linear system conjugate gradient.
Language	英語English
The Source to Article	PB_Publication
PUB ID	25682
Document Type	Journal article
Collection	DEPARTMENT OF COMPUTER AND INFORMATION SCIENCE
Recommended Citation GB/T 7714	Lu, J.,Gong, Z. G.,Lin, X.. A Novel and Fast SimRank Algorithm[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 572-585.
APA	Lu, J.., Gong, Z. G.., & Lin, X. (2017). A Novel and Fast SimRank Algorithm. IEEE Transactions on Knowledge and Data Engineering, 572-585.
MLA	Lu, J.,et al."A Novel and Fast SimRank Algorithm".IEEE Transactions on Knowledge and Data Engineering (2017):572-585.

Files in This Item:
There are no files associated with this item.

If you have any objections to this item, please fill out the form below and the administrator will contact you as soon as possible.
Content:
Email：	*
Affiliation No.
Verification Code:	Refresh

Any comments and suggestions are welcomed.
Title:	*
Content:
Email：	*
Verification Code:	Refresh