Discrete-time random walks and Lévy flights on arbitrary networks: when resetting becomes advantageous?

Abstract

The spectral theory of random walks on networks of arbitrary topology can be readily extended to study random walks and Lévy flights subject to resetting on these structures. When a discrete-time process is stochastically brought back from time to time to its starting node, the mean search time needed to reach another node of the network may be significantly decreased. In other cases, however, resetting is detrimental to search. Using the eigenvalues and eigenvectors of the transition matrix defining the process without resetting, we derive a general criterion for finite networks that establishes when there exists a non-zero resetting probability that minimizes the mean first passage time at a target node. Right at optimality, the coefficient of variation of the first passage time is not unity, unlike in continuous time processes with instantaneous resetting, but above 1 and depends on the minimal mean first passage time. The approach is general and applicable to the study of different discrete-time ergodic Markov processes such as Lévy flights, where the long-range dynamics is introduced in terms of the fractional Laplacian of the graph. We apply these results to the study of optimal transport on rings and Cayley trees.

20 pages, 6 figures

References in corpus (12)

• First Passage Under Restart
• First order transition for the optimal search time of Lévy flights with resetting
• Optimal mean first-passage time for a Brownian searcher subjected to resetting: experimental and theoretical results
• Stochastic Search with Poisson and Deterministic Resetting
• Monotonous continuous-time random walks with drift and stochastic reset events
• Long-Range Navigation on Complex Networks using Lévy Random Walks
• Fractional dynamics on networks: Emergence of anomalous diffusion and Lévy flights
• First passage under restart for discrete space and time: application to one dimensional confined lattice random walks
• Diffusive transport on networks with stochastic resetting to multiple nodes
• Comparison of two models of tethered motion
• First passage of a diffusing particle under stochastic resetting in bounded domains with spherical symmetry
• Random Walks on Complex Networks

Cited by in corpus (3)

• Random walks on complex networks under time-dependent stochastic resetting
• Effects of mortality on stochastic search processes with resetting
• A measure of dissimilarity between diffusive processes on networks