Global mean first-passage times of random walks on complex networks

Abstract

We present a general framework, applicable to a broad class of random walks on complex networks, which provides a rigorous lower bound for the mean first-passage time of a random walker to a target site averaged over its starting position, the so-called global mean first-passage time (GMFPT). This bound is simply expressed in terms of the equilibrium distribution at the target, and implies a minimal scaling of the GMFPT with the network size. We show that this minimal scaling, which can be arbitrarily slow for a proper choice of highly connected target, is realized under the simple condition that the random walk is transient at the target site, and independently of the small-world, scale free or fractal properties of the network. Last, we put forward that the GMFPT to a specific target is not a representative property of the network, since the target averaged GMFPT satisfies much more restrictive bounds, which forbid any sublinear scaling with the network size.

4 pages, 1 figure

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
• Laplacian spectra of complex networks and random walks on them: Are scale-free architectures really important?
• Exact solution for mean first-passage time on a pseudofractal scale-free web
• Occupation times of random walks in confined geometries: From random trap model to diffusion limited reactions
• Standard random walks and trapping on the Koch network with scale-free behavior and small-world effect
• Random Walks on deterministic Scale-Free networks: Exact results
• Random walks on complex trees
• Trapping in complex networks
• Random walks on the Apollonian network with a single trap
• Influences of degree inhomogeneity on average path length and random walks in disassortative scale-free networks
• Random Walks on Complex Networks

Cited by in corpus (79)

• Random walks and diffusion on networks
• Geometry-controlled kinetics
• First passage time for random walks in heterogeneous networks
• A spectrum of routing strategies for brain networks
• Random walks on weighted networks
• Long-Range Navigation on Complex Networks using Lévy Random Walks
• Optimizing persistent random searches
• Characteristic times of biased random walks on complex networks
• Random walks on networks with stochastic resetting
• Extreme events on complex networks
• Determining global mean-first-passage time of random walks on Vicsek fractals using eigenvalues of Laplacian matrices
• Exact calculations of first-passage quantities on recursive networks
• Facilitated diffusion of proteins on chromatin
• Determining mean first-passage time on a class of treelike regular fractals
• Random walks in weighted networks with a perfect trap: An application of Laplacian spectra
• Mean first-passage time for random walks on undirected networks
• Mean first-passage time of surface-mediated diffusion in spherical domains
• Eigenvalues of normalized Laplacian matrices of fractal trees and dendrimers: Analytical results and applications
• Spectral dimensions of hierarchical scale-free networks with shortcuts
• Trapping in dendrimers and regular hyperbranched polymers
• Effective target arrangement in a deterministic scale-free graph
• Diffusive transport on networks with stochastic resetting to multiple nodes
• Influence of trap location on the efficiency of trapping in dendrimers and regular hyperbranched polymers
• Close or connected? Distance and connectivity effects on transport in networks
• Random walks in modular scale-free networks with multiple traps
• Mean first-passage time for maximal-entropy random walks in complex networks
• Spatial Log Periodic Oscillations of First-Passage Observables in Fractals
• Optimization and universality of Brownian search in quenched heterogeneous media
• Optimal and suboptimal networks for efficient navigation measured by mean-first passage time of random walks
• Role of fractal dimension in random walks on scale-free networks
• Random walks on complex networks with first-passage resetting
• Mean first-passage time for random walks in general graphs with a deep trap
• Scaling laws for diffusion on (trans)fractal scale-free networks
• Random walks on complex networks under node-dependent stochastic resetting
• Reactive conformations and non-Markovian cyclization kinetics of a Rouse polymer
• Impact of degree heterogeneity on the behavior of trapping in Koch networks
• A Unified Approach to Gated Reactions on Networks
• Search Optimization, Funnel Topography, and Dynamical Criticality on the String Landscape
• Accessibility Measure for Eternal Inflation: Dynamical Criticality and Higgs Metastability
• Complete spectrum of stochastic master equation for random walks on treelike fractals
• Controlling the efficiency of trapping in treelike fractals
• Scaling of mean first-passage time as efficiency measure of nodes sending information on scale-free Koch networks
• Hitting and Trapping Times on Branched Structures
• Origin of the hub spectral dimension in scale-free networks
• Influencers identification in complex networks through reaction-diffusion dynamics
• Random walks with long-range steps generated by functions of Laplacian matrices
• Manipulation of extreme events on scale-free networks
• Random walks on complex networks with multiple resetting nodes: a renewal approach
• Maximal entropy random walk improves efficiency of trapping in dendrimers
• First passage time distribution of active thermal particles in potentials
• Mixed random walks with a trap in scale-free networks including nearest-neighbor and next-nearest-neighbor jumps
• Random walks in small-world exponential treelike networks
• Discrete-time random walks and Lévy flights on arbitrary networks: when resetting becomes advantageous?
• Diffusion-annihilation proecesses in weighted scale-free networks with identical degree sequence
• Exact eigenvalue spectrum of a class of fractal scale-free networks
• Residual mean first-passage time for jump processes: theory and applications to Lévy flights and fractional Brownian motion
• Analysis of fluctuations in the first return times of random walks on regular branched networks
• Scale-variant topological information for characterizing the structure of complex networks
• Random Walk with Memory on Complex Networks
• Random walks in unweighted and weighted modular scale-free networks with a perfect trap
• Optimal scale-free network with a minimum scaling of transport efficiency for random walks with a perfect trap
• Anomalous behavior of trapping in extended dendrimers with a perfect trap
• Fast Algorithm for Relaxation Processes in Big-data Systems
• Response to targeted perturbations for random walks on networks
• Unexpected advantages of exploitation for target searches in complex networks
• Mean first-encounter times of simultaneous random walkers with resetting on networks
• Temporal-varying failures of nodes in networks
• Topology-dependent density optima for efficient simultaneous network exploration
• Fast Computation of Kemeny's Constant for Directed Graphs
• Fast solver for diffusive transport times on dynamic intracellular networks
• Cross-frequency interactions during diffusion on complex brain networks are facilitated by scale-free properties
• Mean first passage times reconstruct the slowest relaxations in potential energy landscapes of nanoclusters
• First passage times of transport on planar spatial networks and their connections to off-network planar diffusion
• Characterizing network topology using first-passage analysis
• "Spectrally gapped" random walks on networks: a Mean First Passage Time formula
• Comparative study of random walks with one-step memory on complex networks
• Heterogeneous Mean First-Passage Time Scaling in Fractal Media
• Optimal search strategies on complex networks
• Controlling the shape of small clusters with and without macroscopic fields