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 (32)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Critical phenomena in complex networks
• Self-similarity of complex networks
• Intermittent search strategies
• First-passage times in complex scale-invariant media
• Scaling theory of transport in complex networks
• Fractal and Transfractal Recursive Scale-Free Nets
• Global mean first-passage times of random walks on complex networks
• Biased random walks on complex networks: the role of local navigation rules
• Exact mean first-passage time on the T-graph
• Exact solution for mean first-passage time on a pseudofractal scale-free web
• First Passage Properties of the Erdos-Renyi Random Graph
• Random Walks on deterministic Scale-Free networks: Exact results
• Percolation in Hierarchical Scale-Free Nets
• Exact calculations of first-passage quantities on recursive networks
• 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
• Mean first-passage time for random walks on undirected networks
• Trapping in complex networks
• Random walks on the Apollonian network with a single trap
• Effective target arrangement in a deterministic scale-free graph
• Trapping in scale-free networks with hierarchical organization of modularity
• Mean first-passage time for random walks on the T-graph
• Close or connected? Distance and connectivity effects on transport in networks
• Random walks in modular scale-free networks with multiple traps
• Role of fractal dimension in random walks on scale-free networks
• Anomalous behavior of trapping on a fractal scale-free network
• Complete spectrum of stochastic master equation for random walks on treelike fractals
• 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

Cited by in corpus (12)

• Exact calculations of first-passage properties on the pseudofractal scale-free web
• Odd q-State Clock Spin-Glass Models in Three Dimensions, Asymmetric Phase Diagrams, and Multiple Algebraically Ordered Phases
• Lower-Critical Spin-Glass Dimension from 23 Sequenced Hierarchical Models
• Correlation Functions, Mean First Passage Times and the Kemeny Constant
• The Chiral Potts Spin Glass in d=2 and 3 Dimensions
• Multitarget search on complex networks: A logarithmic growth of global mean random cover time
• Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem
• Stepwise Positional-Orientational Order and the Multicritical-Multistructural Global Phase Diagram of the s=3/2 Ising Model from Renormalization-Group Theory
• Spectra, hitting times, and resistance distances of $q$-subdivision graphs
• Exact evaluation of the causal spectrum and localization properties of electronic states on a scale-free network
• Volatilities analysis of first-passage time and first-return time on a small-world scale-free network
• On the Kemeny time for continuous-time reversible and irreversible Markov processes with applications to stochastic resetting and to conditioning towards forever-survival