1. Fast All-Pairs SimRank Assessment on Large Graphs and Bipartite Domains.
- Author
-
Yu, Weiren, Lin, Xuemin, Zhang, Wenjie, and McCann, Julie A.
- Subjects
- *
BIPARTITE graphs , *GEOMETRIC vertices , *HYPERLINKS , *PARTIAL sums (Series) , *GRAPH theory - 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 edges, for K , the existing SimRank needs K=\lceil \log _C \,\epsilon \rceil time, where d^{\prime } to O(Km^{\prime }n) . 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. [ABSTRACT FROM PUBLISHER]- Published
- 2015
- Full Text
- View/download PDF