Random walks with stochastic resetting in complex networks: a discrete time approach

Abstract

We consider a discrete-time Markovian random walk with resets on a connected undirected network. The resets, in which the walker is relocated to randomly chosen nodes, are governed by an independent discrete-time renewal process. Some nodes of the network are target nodes, and we focus on the statistics of first hitting of these nodes. In the non-Markov case of the renewal process, we consider both light- and fat-tailed inter-reset distributions. We derive the propagator matrix in terms of discrete backward recurrence time PDFs and in the light-tailed case we show the existence of a non-equilibrium steady state. In order to tackle the non-Markov scenario, we derive a defective propagator matrix which describes an auxiliary walk characterized by killing the walker as soon as it hits target nodes. This propagator provides the information on the mean first passage statistics to the target nodes. We establish sufficient conditions for ergodicity of the walk under resetting. Furthermore, we discuss a generic resetting mechanism for which the walk is non-ergodic. Finally, we analyze inter-reset time distributions with infinite mean where we focus on the Sibuya case. We apply these results to study the mean first passage times for Markovian and non-Markovian (Sibuya) renewal resetting protocols in realizations of Watts-Strogatz and Barabási-Albert random graphs. We show non trivial behavior of the dependence of the mean first passage time on the proportions of the relocation nodes, target nodes and of the resetting rates. It turns out that, in the large-world case of the Watts-Strogatz graph, the efficiency of a random searcher particularly benefits from the presence of resets.

References in corpus (24)

• Stochastic Resetting and Applications
• First Passage Under Restart
• First order transition for the optimal search time of Lévy flights with resetting
• Random walks with preferential relocations to places visited in the past and their application to biology
• Stochastic resetting: A (very) brief review
• Long-Range Navigation on Complex Networks using Lévy Random Walks
• Random walks on networks with stochastic resetting
• First-passage and first-hitting times of Levy flights and Levy walks
• Stochastic resetting by a random amplitude
• Diffusive transport on networks with stochastic resetting to multiple nodes
• Optimal non-Markovian search strategies with n-step memory
• Random walks on complex networks with first-passage resetting
• Discrete space-time resetting model: Application to first-passage and transmission statistics
• Reducing mean first passage times with intermittent confining potentials: a realization of resetting processes
• Random walks on complex networks under time-dependent stochastic resetting
• General approach to stochastic resetting
• First passage time and information of a one-dimensional Brownian particle with stochastic resetting to random positions
• On recurrence of random walks with long-range steps generated by fractional Laplacian matrices on regular networks and simple cubic lattices
• Diffusion with two resetting points
• On Discrete Time Prabhakar-Generalized Fractional Poisson Processes and Related Stochastic Dynamics
• Lévy flights and Lévy walks under stochastic resetting
• Resetting by rescaling: exact results for a diffusing particle in one-dimension
• Squirrels can remember little: A random walk with jump reversals induced by a discrete-time renewal process
• An advection-diffusion process with proportional resetting

Cited by in corpus (4)

• First-passage properties of the jump process with a drift. Two exactly solvable cases
• Mean first-encounter times of simultaneous random walkers with resetting on networks
• First-passage properties of the jump process with a drift. The general case
• Evanescent random walker on networks: Hitting times, budget renewal, and survival dynamics