Random Multi-Hopper Model. Super-Fast Random Walks on Graphs

Abstract

We develop a model for a random walker with long-range hops on general graphs. This random multi-hopper jumps from a node to any other node in the graph with a probability that decays as a function of the shortest-path distance between the two nodes. We consider here two decaying functions in the form of the Laplace and Mellin transforms of the shortest-path distances. Remarkably, when the parameters of these transforms approach zero asymptotically, the multi-hopper's hitting times between any two nodes in the graph converge to their minimum possible value, given by the hitting times of a normal random walker on a complete graph. Stated differently, for small parameter values the multi-hopper explores a general graph as fast as possible when compared to a random walker on a full graph. Using computational experiments we show that compared to the normal random walker, the multi-hopper indeed explores graphs with clusters or skewed degree distributions more efficiently for a large parameter range. We provide further computational evidence of the speed-up attained by the random multi-hopper model with respect to the normal random walker by studying deterministic, random and real-world networks.

22 pages, 9 figures

References in corpus (3)

• Benchmark graphs for testing community detection algorithms
• Long-Range Navigation on Complex Networks using Lévy Random Walks
• Random Walks on Complex Networks

Cited by in corpus (18)

• Random walks on networks with stochastic resetting
• Diffusive transport on networks with stochastic resetting to multiple nodes
• Nonlocal network dynamics via fractional graph Laplacians
• Exact results for the first-passage properties in a class of fractal networks
• Nonlocal biased random walks and fractional transport on directed networks
• Mean encounter times for multiple random walkers on networks
• Nonlocal PageRank
• Simplicial cascades are orchestrated by the multidimensional geometry of neuronal complexes
• Compatibility, embedding and regularization of non-local random walks on graphs
• Fractional dynamics on circulant multiplex networks: optimal coupling and long-range navigation for continuous-time random walks
• Nonlocal diffusion of variable order on complex networks
• Efficient network exploration by means of resetting self-avoiding random walkers
• Mean first-encounter times of simultaneous random walkers with resetting on networks
• Indirect Influence on Network Diffusion
• Long-range connections and mixed diffusion in fractional networks
• Long-range connections, real-world networks and rates of diffusion
• Markov chain approach to anomalous diffusion on Newman-Watts networks
• Walk based Laplacians for Modeling Diffusion on Complex Networks