Random multi-hopper model: super-fast random walks on graphs
(2017) Journal of Complex Networks — (2017)
Files
161208631.pdf
Closed Access - Adobe PDF
- 1.22 MB
Details
- Authors
- Abstract
- 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.
- Affiliations
Citations
Estrada, E., Delvenne, J.-C., Hatano, N., Mateos, J., Metzler, R., Riascos, A. P., & Schaub, M. (2017). Random multi-hopper model: super-fast random walks on graphs. Journal of Complex Networks. Published. https://doi.org/10.1093/comnet/cnx043 (Original work published 2017)