title: Fast Inbound Top-K Query for Random Walk with Restart.
abstract: Random walk with restart (RWR) is widely recognized as one of the most important node proximity measures for graphs, as it captures the holistic graph structure and is robust to noise in the graph. In this paper, we study a novel query based on the RWR measure, called theinbound top-k(Ink) query. Given a query nodeqand a numberk, the Ink query aims at retrievingknodes in the graph that have the largest weighted RWR scoresto q. Ink queries can be highly useful for various applications such as traffic scheduling, disease treatment, and targeted advertising. Nevertheless, none of the existing RWR computation techniques can accurately and efficiently process the Ink query in large graphs. We propose two algorithms, namely Squeeze and Ripple, both of which can accurately answer the Ink query in a fast and incremental manner. To identify the top-knodes, Squeeze iteratively performs matrix-vector multiplication and estimates the lower and upper bounds for all the nodes in the graph. Ripple employs a more aggressive strategy by only estimating the RWR scores for the nodes falling in thevicinityofq, the nodes outside the vicinity do not need to be evaluated because their RWR scores are propagated from the boundary of the vicinity and thus upper bounded. Ripple incrementally expands the vicinity until the top-kresult set can be obtained. Our extensive experiments on real-life graph data sets show that Ink queries can retrieve interesting results, and the proposed algorithms are orders of magnitude faster than state-of-the-art method.
authors.forename: Chao
authors.initials: C
authors.lastname: Zhang
authors.forename: Shan
authors.initials: S
authors.lastname: Jiang
authors.forename: Yucheng
authors.initials: Y
authors.lastname: Chen
authors.forename: Yidan
authors.initials: Y
authors.lastname: Sun
authors.forename: Jiawei
authors.initials: J
authors.lastname: Han