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 H-j 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 article, we first establish a connection between the two quantities, representing K in terms of H-j for all vertices. We then develop an efficient algorithm estimating H-j for all vertices and K in nearly linear time of m. Moreover, we extend the centrality H-j 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 k << 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-k/k-1 1/e) and O(kn(3)) running time, while the latter returns a (1-k/k-1 1/e-& varepsilon;)-approximation solution in nearly-linear time of m, for any parameter 0<& varepsilon;<1. Extensive experiment results validate the performance of our algorithms.