Means of Hitting Times for Random Walks on Graphs: Connections, Computation, and Optimization

For random walks on graph G with n vertices and m edges, the mean hitting time Hj from a vertex chosen from the stationary distribution to vertex j measures the importance for j, while the Kemeny constant K is the mean hitting time from one vertex to another selected randomly according to the stationary distribution. In this paper, we first establish a connection between the two quantities, representing K in terms of Hj for all vertices. We then develop an efficient algorithm estimating Hj for all vertices and (K) in nearly linear time of m. Moreover, we extend the centrality Hj of a single vertex to H(S) of a vertex set S, and establish a link between H(S) and some other quantities. We further study the NP-hard problem of selecting a group S of kll n vertices with minimum H(S), whose objective function is monotonic and supermodular. We finally propose two greedy algorithms approximately solving the problem. The former has an approximation factor (1-frackk-1frac1e) and O(kn3) running time, while the latter returns a (1-frackk-1frac1e-ε)-approximation solution in nearly-linear time of m, for any parameter 0<ε <1. Extensive experiment results validate the performance of our algorithms.