Efficient network exploration by means of resetting self-avoiding random walkers

Abstract

The self-avoiding random walk (SARW) is a stochastic process whose state variable avoids returning to previously visited states. This non-Markovian feature has turned SARWs a powerful tool for modelling a plethora of relevant aspects in network science, such as network navigability, robustness and resilience. We analytically characterize self-avoiding random walkers that evolve on complex networks and whose memory suffers stochastic resetting, that is, at each step, with a certain probability, they forget their previous trajectory and start free diffusion anew. Several out-of-equilibrium properties are addressed, such as the time-dependent position of the walker, the time-dependent degree distribution of the non-visited network and the first-passage time distribution, and its moments, to target nodes. We examine these metrics for different resetting parameters and network topologies, both synthetic and empirical, and find a good agreement with simulations in all cases. We also explore the role of resetting on network exploration and report a non-monotonic behavior of the cover time: frequent memory resets induce a global minimum in the cover time, significantly outperforming the well-known case of the pure random walk, while reset events that are too spaced apart become detrimental for the network discovery. Our results provide new insights into the profound interplay between topology and dynamics in complex networks, and shed light on the fundamental properties of SARWs in nontrivial environments.

arXiv comment10 pages & 3 figures; Supp. Mat.: 11 pages & 15 figures

References in corpus (32)

• Epidemic processes in complex networks
• Random graphs with arbitrary degree distributions and their applications
• Critical phenomena in complex networks
• Networks beyond pairwise interactions: structure and dynamics
• Self-similar community structure in organisations
• Influence maximization in complex networks through optimal percolation
• Random walks and diffusion on networks
• Stochastic Resetting and Applications
• The Statistical Physics of Real-World Networks
• Searching for superspreaders of information in real-world social media
• Small vulnerable sets determine large network cascades in power grids
• Cut-offs and finite size effects in scale-free networks
• Steady state, relaxation and first-passage properties of a run-and-tumble particle in one-dimension
• Random walks on graphs: ideas, techniques and results
• Exploring complex networks by walking on them
• Non-backtracking random walks mix faster
• Universal survival probability for a $d$-dimensional run-and-tumble particle
• Long-Range Navigation on Complex Networks using Lévy Random Walks
• Random Multi-Hopper Model. Super-Fast Random Walks on Graphs
• First-passage distributions for the one-dimensional Fokker-Planck equation
• Walks on Apollonian networks
• Self-avoiding walks and connective constants in small-world networks
• The distribution of path lengths of self avoiding walks on Erdős-Rényi networks
• Abrupt transition due to non-local cascade propagation in multiplex systems
• Self-avoiding walk, spin systems, and renormalization
• Kinetic growth walks on complex networks
• Nonlocal PageRank
• Kinetic-growth self-avoiding walks on small-world networks
• Analytical results for the distribution of cover times of random walks on random regular graphs
• Self-avoiding walks and connective constants in clustered scale-free networks
• Non-Markovian random walks characterize network robustness to nonlocal cascades
• On the existence of critical exponents for self-avoiding walks