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 incremental SimRank on link-evolving graphs

Tools
- Tools
+ Tools

Yu, Weiren, Lin, Xuemin and Zhang, Wenjie (2014) Fast incremental SimRank on link-evolving graphs. In: 2014 IEEE 30th International Conference on Data Engineering, Chicago, IL, USA, 31 Mar- Apr 2014. Published in: 2014 IEEE 30th International Conference on Data Engineering pp. 304-315. ISSN 1063-6382. doi:10.1109/ICDE.2014.6816660

[img]
Preview
PDF
WRAP-fast-incremental-SimRink-graphs-Yu-2014.pdf - Accepted Version - Requires a PDF viewer.

Download (305Kb) | Preview
Official URL: http://dx.doi.org/10.1109/ICDE.2014.6816660

Request Changes to record.

Abstract

SimRank is an arresting measure of node-pair similarity based on hyperlinks. It iteratively follows the concept that 2 nodes are similar if they are referenced by similar nodes. Real graphs are often large, and links constantly evolve with small changes over time. This paper considers fast incremental computations of SimRank on link-evolving graphs. The prior approach [12] to this issue factorizes the graph via a singular value decomposition (SVD) first, and then incrementally maintains this factorization for link updates at the expense of exactness. Consequently, all node-pair similarities are estimated in O(r 4 n 2 ) time on a graph of n nodes, where r is the target rank of the low-rank approximation, which is not negligibly small in practice. In this paper, we propose a novel fast incremental paradigm. (1) We characterize the SimRank update matrix ΔS, in response to every link update, via a rank-one Sylvester matrix equation. By virtue of this, we devise a fast incremental algorithm computing similarities of n 2 node-pairs in O(Kn 2 ) time for K iterations. (2) We also propose an effective pruning technique capturing the “affected areas” of ΔS to skip unnecessary computations, without loss of exactness. This can further accelerate the incremental SimRank computation to O(K(nd+|AFF|)) time, where d is the average in-degree of the old graph, and |AFF| (≤ n 2 ) is the size of “affected areas” in ΔS, and in practice, |AFF| ≪ n 2 . Our empirical evaluations verify that our algorithm (a) outperforms the best known link-update algorithm [12], and (b) runs much faster than its batch counterpart when link updates are small.

Item Type: Conference Item (Paper)
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, Link theory, Computer algorithms, SimRank, Graph algorithms
Journal or Publication Title: 2014 IEEE 30th International Conference on Data Engineering
Publisher: IEEE
ISSN: 1063-6382
Book Title: 2014 IEEE 30th International Conference on Data Engineering
Official Date: 19 May 2014
Dates:
DateEvent
19 May 2014Published
Page Range: pp. 304-315
DOI: 10.1109/ICDE.2014.6816660
Status: Peer Reviewed
Publication Status: Published
Publisher Statement: © 2014 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
Conference Paper Type: Paper
Title of Event: 2014 IEEE 30th International Conference on Data Engineering
Type of Event: Conference
Location of Event: Chicago, IL, USA
Date(s) of Event: 31 Mar- Apr 2014

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