首页|A matrix sampling approach for efficient SimRank computation
A matrix sampling approach for efficient SimRank computation
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
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. (C) 2020 Elsevier Inc. All rights reserved.
SimRankMatrix samplingSteepest descent
Lu, Juan、Gong, Zhiguo、Yang, Yiyang
展开 >
Beijing Inst Petrochem Technol, Beijing, Peoples R China
Univ Macau, Macau, Peoples R China
GuangDong Univ Technol, Guangzhou, Peoples R China
NSTL
Elsevier
