The Library
Fast incremental SimRank on link-evolving graphs
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. doi:10.1109/ICDE.2014.6816660 ISSN 1063-6382.
|
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
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, Engineering and Medicine > 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: |
|
||||
Page Range: | pp. 304-315 | ||||
DOI: | 10.1109/ICDE.2014.6816660 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Reuse Statement (publisher, data, author rights): | © 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 | ||||
Date of first compliant deposit: | 31 January 2020 | ||||
Date of first compliant Open Access: | 17 February 2020 | ||||
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
Downloads per month over past year