Random multi-hopper model
- We develop a mathematical model considering a random walker with long-range hops on arbitrary graphs. The random multi-hopper can jump to any node of the graph from an initial position, with a probability that decays as a function of the shortest-path distance between the two nodes in the graph. We consider here two decaying functions in the form of Laplace and Mellin transforms of the shortest-path distances. We prove that when the parameters of these transforms approach zero asymptotically, the hitting time in the multi-hopper approaches the minimum possible value for a normal random walker. We show by computational experiments that the multi-hopper explores a graph with clusters or skewed degree distributions more efficiently than a normal random walker. We provide computational evidences of the advantages of the random multi-hopper model with respect to the normal random walk by studying deterministic, random and real-world networks.
Verfasserangaben: | Ernesto EstradaORCiD, Jean-Charles Delvenne, Naomichi HatanoORCiD, Jose L. Mateos, Ralf MetzlerORCiDGND, Alejandro P. Riascos, Michael T. Schaub |
---|---|
DOI: | https://doi.org/10.1093/comnet/cnx043 |
ISSN: | 2051-1310 |
ISSN: | 2051-1329 |
Titel des übergeordneten Werks (Englisch): | Journal of Complex Networks |
Untertitel (Englisch): | super-fast random walks on graphs |
Verlag: | Oxford Univ. Press |
Verlagsort: | Oxford |
Publikationstyp: | Wissenschaftlicher Artikel |
Sprache: | Englisch |
Datum der Erstveröffentlichung: | 03.10.2018 |
Erscheinungsjahr: | 2018 |
Datum der Freischaltung: | 12.11.2021 |
Band: | 6 |
Ausgabe: | 3 |
Seitenanzahl: | 22 |
Erste Seite: | 382 |
Letzte Seite: | 403 |
Fördernde Institution: | the Marie Sklodowska-Curie grantEuropean Union (EU) [702410]; Concerted Research Action (ARC) programme - Federation Wallonia-Brussels [ARC 14/19-060]; DFGGerman Research Foundation (DFG) [ME 1535/6-1] |
Organisationseinheiten: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Physik und Astronomie |
DDC-Klassifikation: | 5 Naturwissenschaften und Mathematik / 53 Physik / 530 Physik |