Long-range navigation on complex networks using Lévy random walks

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.

Figure 1

${\tau }_i$ vs $k_i$ for a scale-free network with $N=5000$ nodes, using three values of the exponent $\alpha$. The inset depicts $P_i^{\infty }$ vs $k_i$, and the solid line indicates the limiting case $\alpha =0$.

Figure 2

The time $\tau$ vs $\alpha$ for different networks with $N=5000$. (top) The results for a 1D lattice, a 2D square lattice ($50\times 100$), and a random tree (network without loops); we used periodic boundary conditions in both lattices. (bottom) The results for a SF network and an ER network at the percolation threshold.

Figure 3

Monte Carlo simulation of the number of distinct visited sites $N_v$ vs time in a network with $N=5000$. (a) A 1D lattice, (b) a random tree, and (c) a scale-free network. Each curve is obtained from the average of 1000 realizations of the random walker.