Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

[img]
Preview
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

Request Changes to record.

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:
DateEvent
2015Published
16 August 2014Available
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:
Project/Grant IDRIOXX Funder NameFunder ID
61232006[NSFC] National Natural Science Foundation of Chinahttp://dx.doi.org/10.13039/501100001809
61021004[NSFC] National Natural Science Foundation of Chinahttp://dx.doi.org/10.13039/501100001809
DP140103578[ARC] Australian Research Councilhttp://dx.doi.org/10.13039/501100000923
DP120104168[ARC] Australian Research Councilhttp://dx.doi.org/10.13039/501100000923
DE120102144[ARC] Australian Research Councilhttp://dx.doi.org/10.13039/501100000923
DP120104168[ARC] Australian Research Councilhttp://dx.doi.org/10.13039/501100000923

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us