Optimal and suboptimal networks for efficient navigation measured by mean-first passage time of random walks

Abstract

For a random walk on a network, the mean first-passage time from a node $i$ to another node $j$ chosen stochastically according to the equilibrium distribution of Markov chain representing the random walk is called Kemeny constant, which is closely related to the navigability on the network. Thus, the configuration of a network that provides optimal or suboptimal navigation efficiency is a question of interest. It has been proved that complete graphs have the exact minimum Kemeny constant over all graphs. In this paper, by using another method we first prove that complete graphs are the optimal networks with a minimum Kemeny constant, which grows linearly with the network size. Then, we study the Kemeny constant of a class of sparse networks that exhibit remarkable scale-free and fractal features as observed in many real-life networks, which cannot be described by complete graphs. To this end, we determine the closed-form solutions to all eigenvalues and their degeneracies of the networks. Employing these eigenvalues, we derive the exact solution to the Kemeny constant, which also behaves linearly with the network size for some particular cases of networks. We further use the eigenvalue spectra to determine the number of spanning trees in the networks under consideration, which is in complete agreement with previously reported results. Our work demonstrates that scale-free and fractal properties are favorable for efficient navigation, which could be considered when designing networks with high navigation efficiency.

Definitive version accepted for publication in Chaos. 10 pages, 2 figures

References in corpus (15)

• Critical phenomena in complex networks
• First-passage times in complex scale-invariant media
• Scaling theory of transport in complex networks
• Fractal and Transfractal Recursive Scale-Free Nets
• Exact mean first-passage time on the T-graph
• Exact solution for mean first-passage time on a pseudofractal scale-free web
• Percolation in Hierarchical Scale-Free Nets
• Self-similarity, small-world, scale-free scaling, disassortativity, and robustness in hierarchical lattices
• Determining mean first-passage time on a class of treelike regular fractals
• Trapping in complex networks
• Random walks on the Apollonian network with a single trap
• Mean first-passage time for random walks on the T-graph
• Anomalous behavior of trapping on a fractal scale-free network
• Influences of degree inhomogeneity on average path length and random walks in disassortative scale-free networks
• Exact eigenvalue spectrum of a class of fractal scale-free networks