Random walks with stochastic resetting in complex networks: A discrete-time approach
Chaos: An Interdisciplinary Journal of Nonlinear Science · 01.01.2025 · 35 (1)
DOI: 10.1063/5.0238517 ↗Kurz gefasst
Fachartikel in der Zeitschrift Chaos: An Interdisciplinary Journal of Nonlinear Science, online erschienen am 09.01.2025. Verfasst von Thomas M Michelitsch und 3 weiteren Autor:innen. Beteiligte Einrichtung: Sorbonne Université, CNRS, Institut Jean Le Rond d'Alembert, F-75005 Paris, France. Die Arbeit wurde bisher 21-mal zitiert (Crossref) und nennt 70 Literaturangaben. Gefördert von: Ministero dell'Università e della Ricerca.
Abstract (Originalsprache)
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 probability density functions, 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 nontrivial 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.
Autor:innen und Institutionen
- Sorbonne Université, CNRS, Institut Jean Le Rond d'Alembert, F-75005 Paris, France.
- Department of Mathematical Sciences, Politecnico di Torino, 10129 Torino, Italy.
- Department of Mathematics "G. Peano," University of Torino, 10123 Torino, Italy.
- Departamento de Física, Universidad Nacional de Colombia, Bogotá, Colombia.
ORCID-Profile: Thomas M Michelitsch, Giuseppe D'Onofrio, Federico Polito, Alejandro P Riascos
Förderung
- Ministero dell'Università e della Ricerca
Zitieren
APA
Michelitsch, T. M., D'Onofrio, G., Polito, F., & Riascos, A. P. (2025). Random walks with stochastic resetting in complex networks: A discrete-time approach. Chaos: An Interdisciplinary Journal of Nonlinear Science, 35(1). https://doi.org/10.1063/5.0238517
Vancouver
Michelitsch TM, D'Onofrio G, Polito F, Riascos AP. Random walks with stochastic resetting in complex networks: A discrete-time approach. Chaos: An Interdisciplinary Journal of Nonlinear Science. 2025;35(1). doi:10.1063/5.0238517
BibTeX
@article{Michelitsch2025,
author = {Michelitsch, Thomas M and D'Onofrio, Giuseppe and Polito, Federico and Riascos, Alejandro P},
title = {Random walks with stochastic resetting in complex networks: A discrete-time approach},
journal = {Chaos: An Interdisciplinary Journal of Nonlinear Science},
year = {2025},
volume = {35},
number = {1},
doi = {10.1063/5.0238517}
}
EUVIMED