TY  - JOUR
A1  - Estrada, Ernesto
A1  - Delvenne, Jean-Charles
A1  - Hatano, Naomichi
A1  - Mateos, Jose L.
A1  - Metzler, Ralf
A1  - Riascos, Alejandro P.
A1  - Schaub, Michael T.
T1  - Random multi-hopper model
BT  - super-fast random walks on graphs
JF  - Journal of Complex Networks
N2  - 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.
Y1  - 2018
U6  - https://doi.org/10.1093/comnet/cnx043
SN  - 2051-1310
SN  - 2051-1329
VL  - 6
IS  - 3
SP  - 382
EP  - 403
PB  - Oxford Univ. Press
CY  - Oxford
ER  -