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

Preview

PDF WRAP-fast-incremental-SimRink-graphs-Yu-2014.pdf - Accepted Version - Requires a PDF viewer. Download (305Kb) | Preview

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:	Date Event 19 May 2014 Published
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

Downloads