Extreme first passage times for random walks on networks

Abstract

Many biological, social, and communication systems can be modeled by ``searchers'' moving through a complex network. For example, intracellular cargo is transported on tubular networks, news and rumors spread through online social networks, and the rapid global spread of infectious diseases occurs through passengers traveling on the airport network. To understand the timescale of search/transport/spread, one commonly studies the first passage time (FPT) of a single searcher (or ``spreader'') to a target. However, in many scenarios the relevant timescale is not the FPT of a single searcher to a target, but rather the FPT of the fastest searcher to a target out of many searchers. For example, many processes in cell biology are triggered by the first molecule to find a target out of many, and the time it takes an infectious disease to reach a particular city depends on the first infected traveler to arrive out of potentially many infected travelers. Such fastest FPTs are called extreme FPTs. In this paper, we study extreme FPTs for a general class of continuous-time random walks on networks (which includes continuous-time Markov chains). In the limit of many searchers, we find explicit formulas for the probability distribution and all the moments of the $k$th fastest FPT. These rigorous formulas depend only on network parameters along a certain geodesic path(s) from the starting location to the target since the fastest searchers take a direct route to the target. Furthermore, our results allow one to estimate if a particular system is in a regime characterized by fast extreme FPTs. We also prove similar results for mortal searchers on a network that are conditioned to find the target before a fast inactivation time. We illustrate our results with numerical simulations and uncover potential pitfalls of modeling diffusive or subdiffusive processes involving extreme statistics.

arXiv comment33 pages, 4 figures

References in corpus (28)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Epidemic processes in complex networks
• Random walks and diffusion on networks
• First-passage times in complex scale-invariant media
• Optimal Paths in Disordered Complex Networks
• Effective Distances for Epidemics Spreading on Complex Networks
• Global disease spread: statistics and estimation of arrival times
• Mortality, Redundancy, and Diversity in Stochastic Search
• Reaction-subdiffusion and reaction-superdiffusion equations for evanescent particles performing continuous time random walks
• Diffusive escape through a narrow opening: new insights into a classic problem
• Exploration and Trapping of Mortal Random Walkers
• Universal Formula for Extreme First Passage Statistics of Diffusion
• Distribution of extreme first passage times of diffusion
• From single-particle stochastic kinetics to macroscopic reaction rates: fastest first-passage time of $N$ random walkers
• Asymptotics of extreme statistics of escape time in 1,2 and 3-dimensional diffusions
• Duality Between Relaxation and First Passage in Reversible Markov Dynamics: Rugged Energy Landscapes Disentangled
• Extreme value statistics of ergodic Markov processes from first passage times in the large deviation limit
• A probabilistic approach to extreme statistics of Brownian escape times in dimensions 1, 2, and 3
• Arrival Time Statistics in Global Disease Spread
• Competition between slow and fast regimes for extreme first passage times of diffusion
• Order statistics for d-dimensional diffusion processes
• Survival probability of an immobile target in a sea of evanescent diffusive or subdiffusive traps: a fractional equation approach
• Evanescent continuous time random walks
• The number statistics and optimal history of non-equilibrium steady states of mortal diffusing particles
• Extreme statistics of anomalous subdiffusion following a fractional Fokker-Planck equation: Subdiffusion is faster than normal diffusion
• First Invader Dynamics in Diffusion-Controlled Absorption
• Random Walks on Complex Networks

Cited by in corpus (5)

• Extreme hitting probabilities for diffusion
• Fast rare events in exit times distributions of jump processes
• Controlling Uncertainty of Empirical First-Passage Times in the Small-Sample Regime
• Arrival time for the fastest among $N$ switching stochastic particles
• Modeling and asymptotic analysis of the concentration difference in a nanoregion between an influx and outflux diffusion across narrow windows