Fast and exact top-k search for random walk with restart
Open Access
- 1 January 2012
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 5 (5) , 442-453
Abstract
Graphs are fundamental data structures and have been employed for centuries to model real-world systems and phenomena. Random walk with restart (RWR) provides a good proximity score between two nodes in a graph, and it has been successfully used in many applications such as automatic image captioning, recommender systems, and link prediction. The goal of this work is to find nodes that have top-k highest proximities for a given node. Previous approaches to this problem find nodes efficiently at the expense of exactness. The main motivation of this paper is to answer, in the affirmative, the question, 'Is it possible to improve the search time without sacrificing the exactness?'. Our solution, K-dash , is based on two ideas: (1) It computes the proximity of a selected node efficiently by sparse matrices, and (2) It skips unnecessary proximity computations when searching for the top-k nodes. Theoretical analyses show that K-dash guarantees result exactness. We perform comprehensive experiments to verify the efficiency of K-dash. The results show that K-dash can find top-k nodes significantly faster than the previous approaches while it guarantees exactness.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Quick Detection of Top-k Personalized PageRank Lists2011
- Accuracy estimate and optimization techniques for SimRank computationProceedings of the VLDB Endowment, 2008
- Simrank++Proceedings of the VLDB Endowment, 2008
- Fast algorithms for topk personalized pagerank queries2008
- Center-piece subgraphs2006
- Optimization and evaluation of shortest path queriesThe VLDB Journal, 2006
- Automatic multimedia cross-modal correlation discovery2004
- The link prediction problem for social networks2003
- Multilevelk-way Partitioning Scheme for Irregular GraphsJournal of Parallel and Distributed Computing, 1998
- Computing the Minimum Fill-In is NP-CompleteSIAM Journal on Algebraic Discrete Methods, 1981