Power-Law Graphs Have Minimal Scaling of Kemeny Constant for Random Walks

The mean hitting time from a node i to a node j selected randomly according to the stationary distribution of random walks is called the Kemeny constant, which has found various applications. It was proved that over all graphs with N vertices, complete graphs have the exact minimum Kemeny constant, growing linearly with N. Here we study numerically or analytically the Kemeny constant on many sparse real-world and model networks with scale-free smallworld topology, and show that their Kemeny constant also behaves linearly with N. Thus, sparse networks with scale-free and small-world topology are favorable architectures with optimal scaling of Kemeny constant. We then present a theoretically guaranteed estimation algorithm, which approximates the Kemeny constant for a graph in nearly linear time with respect to the number of edges. Extensive numerical experiments on model and real networks show that our approximation algorithm is both efficient and accurate.

Download paper here

Recommended citation: Xu Wanyue, Sheng Yibin, Zhang Zuobai, Kan Haibin, and Zhang Zhongzhi. Power-law graphs with minimal scaling of Kemeny constant for random walks. In: Proceedings of the Web Conference (WWW 2020), Taipei, China, April 20-24, 2020, pp.46-56.