Mean first-passage time for maximal-entropy random walks in complex networks

Abstract

We perform an in-depth study for mean first-passage time (MFPT)---a primary quantity for random walks with numerous applications---of maximal-entropy random walks (MERW) performed in complex networks. For MERW in a general network, we derive an explicit expression of MFPT in terms of the eigenvalues and eigenvectors of the adjacency matrix associated with the network. For MERW in uncorrelated networks, we also provide a theoretical formula of MFPT at the mean-field level, based on which we further evaluate the dominant scalings of MFPT to different targets for MERW in uncorrelated scale-free networks, and compare the results with those corresponding to traditional unbiased random walks (TURW). We show that the MFPT to a hub node is much lower for MERW than for TURW. However, when the destination is a node with the least degree or a uniformly chosen node, the MFPT is higher for MERW than for TURW. Since MFPT to a uniformly chosen node measures real efficiency of search in networks, our work provides insight into general searching process in complex networks.

Definitive version accepted for publication in Scientific Reports

References in corpus (38)

• Emergence of scaling in random networks
• The structure and function of complex networks
• Specificity and stability in topology of protein networks
• Resilience of the Internet to random breakdowns
• Critical phenomena in complex networks
• Dynamical and correlation properties of the Internet
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Intermittent search strategies
• First-passage times in complex scale-invariant media
• Weighted evolving networks: coupling topology and weights dynamics
• The origin of degree correlations in the Internet and other networks
• Random walks on graphs: ideas, techniques and results
• Entropy Rate of Diffusion Processes on Complex Networks
• Global mean first-passage times of random walks on complex networks
• Localization of maximal entropy random walk
• Biased random walks on complex networks: the role of local navigation rules
• First-passage times for random walks in bounded domains
• First passage time for random walks in heterogeneous networks
• Exact mean first-passage time on the T-graph
• Maximal-entropy random walks in complex networks with limited information
• Random walks on weighted networks
• Exact solution for mean first-passage time on a pseudofractal scale-free web
• Langevin approach for the dynamics of the contact process on annealed scale-free networks
• Characteristic times of biased random walks on complex networks
• Random Walks on deterministic Scale-Free networks: Exact results
• Flow graphs: interweaving dynamics and structure
• Mean-field diffusive dynamics on weighted networks
• Exact calculations of first-passage quantities on recursive networks
• Random walks in weighted networks with a perfect trap: An application of Laplacian spectra
• Centrality measures and thermodynamic formalism for complex networks
• Trapping in complex networks
• Effective target arrangement in a deterministic scale-free graph
• Maximal entropy random walk in community finding
• Controlling the efficiency of trapping in treelike fractals
• Exact Solution for Statics and Dynamics of Maximal Entropy Random Walk on Cayley Trees
• Maximal-entropy random walk unifies centrality measures
• Random walks in unweighted and weighted modular scale-free networks with a perfect trap
• Maximal Entropy Random Walk: solvable cases of dynamics

Cited by in corpus (8)

• Search Optimization, Funnel Topography, and Dynamical Criticality on the String Landscape
• Reactive random walkers on complex networks
• Multitarget search on complex networks: A logarithmic growth of global mean random cover time
• Effects of reciprocity on random walks in weighted networks
• Mean trapping time for an arbitrary node on regular hyperbranched polymers
• Anomalous behavior of trapping in extended dendrimers with a perfect trap
• Random walks on graphs with interval weights and precise marginals
• Maximal dispersion of adaptive random walks