Paper Info
Title
Nearly Linear Time Algorithm for Mean Hitting Times of Random Walks on a Graph.
Abstract
For random walks on a graph, the mean hitting time $H_j$ from a vertex i chosen from the stationary distribution to the target vertex j can be used as a measure of importance for vertex j, while the Kemeny constant K is the mean hitting time from a vertex i to a vertex j selected randomly according to the stationary distribution. Both quantities have found a large variety of applications in different areas. However, their high computational complexity limits their applications, especially for large networks with millions of vertices. In this paper, we first establish a connection between the two quantities, representing K in terms of $H_j$ for all vertices. We then express both quantities in terms of quadratic forms of the pseudoinverse for graph Laplacian, based on which we develop an efficient algorithm that provides an approximation of $H_j$ for all vertices and K in nearly linear time with respect to the edge number, with high probability. Extensive experiment results on real-life and model networks validate both the efficiency and accuracy of the proposed algorithm.
Year
DOI
Venue
2020
10.1145/3336191.3371777
WSDM '20: The Thirteenth ACM International Conference on Web Search and Data Mining Houston TX USA February, 2020
Keywords
Field
DocType
Random walk, hitting time, Kemeny constant, spectral algorithm, complex network, node centrality
Graph,Random walk,Computer science,Algorithm,Time complexity
Conference
ISBN
Citations 
PageRank 
978-1-4503-6822-3
0
0.34
References 
Authors
0
3
Name
Order
Citations
PageRank
Zuobai Zhang112.39
Wanyue Xu213.07
Zhongzhi Zhang38522.02