A matrix sampling approach for efficient SimRank computation

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

Status	已發表Published
	A matrix sampling approach for efficient SimRank computation
	Lu, J; Gong, Z. G.; Yang, Y
	2021-05-01
Source Publication	Information Science
ISSN	0020-0255
Pages	1-26
Abstract	Evaluating 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.
Keyword	SimRank graph
URL	View the original
Language	英語English
The Source to Article	PB_Publication
PUB ID	59948
Document Type	Journal article
Collection	DEPARTMENT OF COMPUTER AND INFORMATION SCIENCE
Corresponding Author	Gong, Z. G.
Recommended Citation GB/T 7714	Lu, J,Gong, Z. G.,Yang, Y. A matrix sampling approach for efficient SimRank computation[J]. Information Science, 2021, 1-26.
APA	Lu, J., Gong, Z. G.., & Yang, Y (2021). A matrix sampling approach for efficient SimRank computation. Information Science, 1-26.
MLA	Lu, J,et al."A matrix sampling approach for efficient SimRank computation".Information Science (2021):1-26.

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