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 small-world 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.

Mean hitting time for random walks on a network, defined as the average of hitting times over all possible pairs of nodes, has found a large variety of applications in many areas. In this paper, we first prove that among all N-node networks, the complete graph has the minimum mean hitting time N - 1, which scales linearly with network size. We then study a random walk mobility model with location heterogeneity, modeled by scale-free networks, which are ubiquitous in realistic systems such as P2P networks. For this purpose, we consider random walks on two sparse scale-free small-world networks. By using the connection between random walks and electrical networks, we derive explicit formulas about mean hitting time for both networks, the dominant scaling of which exhibits the same behavior as that of complete graphs. This paper demonstrates that heterogeneous sparse networks can have low-mean hitting time with a behavior similar to that of dense complete graphs, which is instrumental in designing networks, where search is fast between any pair of nodes.