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.

10 pages & 3 figures; Supp. Mat.: 11 pages & 15 figures

References in corpus (9)

• Critical phenomena in complex networks
• Searching for superspreaders of information in real-world social media
• Universal survival probability for a $d$-dimensional run-and-tumble particle
• Long-Range Navigation on Complex Networks using Lévy Random Walks
• Abrupt transition due to non-local cascade propagation in multiplex systems
• Kinetic-growth self-avoiding walks on small-world networks
• 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