Random walks on complex networks with first-passage resetting

Abstract

We study discrete-time random walks on arbitrary networks with first-passage resetting processes. To the end, a set of nodes are chosen as observable nodes, and the walker is reset instantaneously to a given resetting node whenever it hits either of observable nodes. We derive exact expressions of the stationary occupation probability, the average number of resets in the long time, and the mean first-passage time between arbitrary two non-observable nodes. We show that all the quantities can be expressed in terms of the fundamental matrix $\text{Z}=(\text{I}-\text{Q}{)}^{-1}$, where $\text{I}$ is the identity matrix and $\text{Q}$ is the transition matrix between non-observable nodes. Finally, we use ring networks, 2d square lattices, barbell networks, and Cayley trees to demonstrate the advantage of first-passage resetting in global search on such networks.

arXiv commentAccepted by Physical Review E

References in corpus (42)

• Community detection in graphs
• Maps of random walks on complex networks reveal community structure
• Epidemic processes in complex networks
• Vital nodes identification in complex networks
• Human Mobility: Models and Applications
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• Diffusion with Stochastic Resetting
• Voter Model on Heterogeneous Graphs
• Random walks and diffusion on networks
• Stochastic Resetting and Applications
• Persistence and First-Passage Properties in Non-equilibrium Systems
• Diffusion with Optimal Resetting
• First Passage Under Restart
• Experimental realization of diffusion with stochastic resetting
• Diffusion under time-dependent resetting
• Optimal mean first-passage time for a Brownian searcher subjected to resetting: experimental and theoretical results
• Diffusion with resetting in arbitrary spatial dimension
• Global mean first-passage times of random walks on complex networks
• Natural human mobility patterns and spatial spread of infectious diseases
• Fluctuating interfaces subject to stochastic resetting
• The Michaelis-Menten reaction scheme as a unified approach towards the optimal restart problem
• WKB theory of large deviations in stochastic populations
• First passage time for random walks in heterogeneous networks
• Google matrix analysis of directed networks
• Stochastic thermodynamics of resetting
• Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
• Exact solution for mean first-passage time on a pseudofractal scale-free web
• Random walks on weighted networks
• Work fluctuations and Jarzynski equality in stochastic resetting
• Optimization in First-Passage Resetting
• Random walks on networks with stochastic resetting
• Integral Fluctuation Theorems for Stochastic Resetting Systems
• Symmetric Exclusion Process under Stochastic Resetting
• Ising model with stochastic resetting
• Epidemic extinction and control in heterogeneous networks
• Mean first-passage time for random walks on undirected networks
• Diffusive transport on networks with stochastic resetting to multiple nodes
• Impact of hierarchical modular structure on ranking of individual nodes in directed networks
• From classical to quantum walks with stochastic resetting on networks
• Optimization and Growth in First-Passage Resetting
• Exploring complex networks by means of adaptive walkers
• Random Walks on Complex Networks

Cited by in corpus (19)

• The inspection paradox in stochastic resetting
• Universal framework for record ages under restart
• Emergent quantum correlations and collective behavior in non-interacting quantum systems subject to stochastic resetting
• Ornstein-Uhlenbeck process and generalizations: particle's dynamics under comb constraints and stochastic resetting
• Random walks on complex networks under node-dependent stochastic resetting
• First passage of a diffusing particle under stochastic resetting in bounded domains with spherical symmetry
• Resetting mediated navigation of active Brownian searcher in a homogeneous topography
• Random walks on complex networks under time-dependent stochastic resetting
• Random walks on complex networks with multiple resetting nodes: a renewal approach
• Random walks with stochastic resetting in complex networks: a discrete time approach
• Kuramoto model subject to subsystem resetting: How resetting a part of the system may synchronize the whole of it
• Search with stochastic home-returns can expedite classical first passage under resetting
• Entropy rate of random walks on complex networks under stochastic resetting
• First passage in discrete-time absorbing Markov chains under stochastic resetting
• Drift-diffusive resetting search process with stochastic returns: speed-up beyond optimal instantaneous return
• Kinetic reconstruction of free energies as a function of multiple order parameters
• Density-dependent stochastic resetting: a large deviations framework for achieving target distributions over networks
• Evanescent random walker on networks: Hitting times, budget renewal, and survival dynamics
• On the initial value of PageRank