The Library
Fast all-pairs SimRank assessment on large graphs and bipartite domains
Tools
Tools
Tools
Yu, Weiren, Lin, Xuemin, Zhang, Wenjie and McCann, Julie A. (2015) Fast all-pairs SimRank assessment on large graphs and bipartite domains. IEEE Transactions on Knowledge and Data Engineering, 27 (7). pp. 1810-1823. doi:10.1109/TKDE.2014.2339828
|
PDF
WRAP-fast-all-pairs-SimRank-assessment-Yu-2015.pdf - Accepted Version - Requires a PDF viewer. Download (1916Kb) | Preview |
Official URL: http://dx.doi.org/10.1109/TKDE.2014.2339828
Abstract
SimRank is a powerful model for assessing vertex-pair similarities in a graph. It follows the concept that two vertices are similar if they are referenced by similar vertices. The prior work [18] exploits partial sums memoization to compute SimRank in O(Kmn) time on a graph of n vertices and m edges, for K iterations. However, computations among different partial sums may have redundancy. Besides, to guarantee a given accuracy ε, the existing SimRank needs K = [log C alterations, where C is a damping factor, but the geometric rate of convergence is slow if a high accuracy is expected. In this paper, (1) a novel clustering strategy is proposed to eliminate duplicate computations occurring in partial sums, and an efficient algorithm is then devised to accelerate SimRank computation to O(Kd'n 2 ) time, where d' is typically much smaller than mn. (2) A new differential SimRank equation is proposed, which can represent the SimRank matrix as an exponential sum of transition matrices, as opposed to the geometric sum of the conventional counterpart. This leads to a further speedup in the convergence rate of SimRank iterations. (3) In bipartite domains, a novel finer-grained partial max clustering method is developed to speed up the computation of the Minimax SimRank variation from O(Kmn) to O(Km'n) time, where m' (≤m) is the number of edges in a reduced graph after edge clustering, which can be typically much smaller than m. Using real and synthetic data, we empirically verify that (1) our approach of partial sums sharing outperforms the best known algorithm by up to one order of magnitude; (2) the revised notion of SimRank further achieves a 5X speedup on large graphs while also fairly preserving the relative order of original SimRank scores; (3) our finer-grained partial max memoization for the Minimax SimRank variation in bipartite domains is 5X-12X faster than the baselines.
| Item Type: | Journal Article | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | |||||||||||||||||||||
| Divisions: | Faculty of Science > Computer Science | |||||||||||||||||||||
| Library of Congress Subject Headings (LCSH): | Graph theory -- Data processing, SimRank, Graph algorithms | |||||||||||||||||||||
| Journal or Publication Title: | IEEE Transactions on Knowledge and Data Engineering | |||||||||||||||||||||
| Publisher: | IEEE | |||||||||||||||||||||
| ISSN: | 1041-4347 | |||||||||||||||||||||
| Official Date: | 2015 | |||||||||||||||||||||
| Dates: |
|
|||||||||||||||||||||
| Volume: | 27 | |||||||||||||||||||||
| Number: | 7 | |||||||||||||||||||||
| Page Range: | pp. 1810-1823 | |||||||||||||||||||||
| DOI: | 10.1109/TKDE.2014.2339828 | |||||||||||||||||||||
| Status: | Peer Reviewed | |||||||||||||||||||||
| Publication Status: | Published | |||||||||||||||||||||
| Publisher Statement: | © 2015 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. | |||||||||||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||||||||
| RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
