Long-Range Navigation on Complex Networks using Lévy Random Walks

Abstract

We introduce a strategy of navigation in undirected networks, including regular, random, and complex networks, that is inspired by Lévy random walks, generalizing previous navigation rules. We obtained exact expressions for the stationary probability distribution, the occupation probability, the mean first passage time, and the average time to reach a node on the network. We found that the long-range navigation using the Lévy random walk strategy, compared with the normal random walk strategy, is more efficient at reducing the time to cover the network. The dynamical effect of using the Lévy walk strategy is to transform a large-world network into a small world. Our exact results provide a general framework that connects two important fields: Lévy navigation strategies and dynamics on complex networks.

6 pages, 3 figures

References in corpus (20)

• Emergence of scaling in random networks
• Understanding individual human mobility patterns
• Synchronization in complex networks
• Temporal Networks
• The scaling laws of human travel
• A universal model for mobility and migration patterns
• Modeling the scaling properties of human mobility
• Intermittent search strategies
• Navigability of Complex Networks
• Information diffusion epidemics in social networks
• Global mean first-passage times of random walks on complex networks
• Designing optimal transport networks
• Natural human mobility patterns and spatial spread of infectious diseases
• Understanding mobility in a social petri dish
• Mean first-passage time for random walks on undirected networks
• Efficient search by optimized intermittent random walks
• Asymptotic behavior of the Kleinberg model
• Evolution of optimal Lévy-flight strategies in human mental searches
• Rationality, irrationality and escalating behavior in lowest unique bid auctions
• Understanding the complexity of the Lévy-walk nature of human mobility with a multi-scale cost/benefit model

Cited by in corpus (32)

• Lévy flights in human behavior and cognition
• The topography of the environment alters the optimal search strategy for active particles
• Random walks on networks with stochastic resetting
• Fractional dynamics on networks: Emergence of anomalous diffusion and Lévy flights
• Random walks in weighted networks with a perfect trap: An application of Laplacian spectra
• Diffusive transport on networks with stochastic resetting to multiple nodes
• Random Multi-Hopper Model. Super-Fast Random Walks on Graphs
• Levy random walks on multiplex networks
• Fractional random walk lattice dynamics
• Nonlocal biased random walks and fractional transport on directed networks
• Mean encounter times for multiple random walkers on networks
• On recurrence of random walks with long-range steps generated by fractional Laplacian matrices on regular networks and simple cubic lattices
• Random walks with long-range steps generated by functions of Laplacian matrices
• Aging in transport processes on networks with stochastic cumulative damage
• Random walks with stochastic resetting in complex networks: a discrete time approach
• Nonlocal PageRank
• A fractional generalization of the classical lattice dynamics approach
• Discrete-time random walks and Lévy flights on arbitrary networks: when resetting becomes advantageous?
• Random walks on networks with preferential cumulative damage: Generation of bias and aging
• Compatibility, embedding and regularization of non-local random walks on graphs
• Random Walk with Memory on Complex Networks
• Evolution of transport under cumulative damage in metro systems
• Optimal exploration of random walks with local bias on networks
• Fractional dynamics on circulant multiplex networks: optimal coupling and long-range navigation for continuous-time random walks
• Efficient network exploration by means of resetting self-avoiding random walkers
• Mean first-encounter times of simultaneous random walkers with resetting on networks
• A measure of dissimilarity between diffusive processes on networks
• Non-equilibrium random walks on multiplex networks
• LFGCN: Levitating over Graphs with Levy Flights
• Network navigation using Page Rank random walks
• Walk based Laplacians for Modeling Diffusion on Complex Networks
• An Information-Theoretic Law Governing Human Multi-Task Navigation Decisions