Random multi-hopper model: super-fast random walks on graphs
From MaRDI portal
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.
Recommendations
- Fast graphs for the random walker
- Random walks on dense graphs and graphons
- scientific article; zbMATH DE number 4197088
- Random walks on graphs: ideas, techniques and results
- Random Walks on Randomly Evolving Graphs
- Multiple random walks in random regular graphs
- Random walks on complete multipartite graphs
- Random walks on dynamic graphs: mixing times, hitting times, and return probabilities
Cited in
(16)- Path Laplacian operators and superdiffusive processes on graphs. II. two-dimensional lattice
- First-passage problem for stochastic differential equations with combined parametric Gaussian and Lévy white noises via path integral method
- Efficient approach to time-dependent super-diffusive Lévy random walks on finite 2D-tori using circulant analogues
- Compatibility, embedding and regularization of non-local random walks on graphs
- Long-range connections and mixed diffusion in fractional networks
- Extending the Adapted PageRank Algorithm centrality model for urban street networks using non-local random walks
- Exact results for the first-passage properties in a class of fractal networks
- Nonlocal pagerank
- Fractional dynamics on circulant multiplex networks: optimal coupling and long-range navigation for continuous-time random walks
- Long-range connections, real-world networks and rates of diffusion
- Hitting times for second-order random walks
- Mean first-encounter times of simultaneous random walkers with resetting on networks
- Markov chain approach to anomalous diffusion on Newman-Watts networks
- Anomalous diffusion and fluctuations in complex systems and networks
- Impact of one-way streets on diffusive transport
- Walk based Laplacians for modeling diffusion on complex networks
This page was built for publication: Random multi-hopper model: super-fast random walks on graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3388888)
