Fractional dynamics on networks: Emergence of anomalous diffusion and Lévy flights

We introduce a formalism of fractional diffusion on networks based on a fractional Laplacian matrix that can be constructed directly from the eigenvalues and eigenvectors of the Laplacian matrix. This fractional approach allows random walks with long-range dynamics providing a general framework for anomalous diffusion and navigation, and inducing dynamically the small-world property on any network. We obtained exact results for the stationary probability distribution, the average fractional return probability, and a global time, showing that the efficiency to navigate the network is greater if we use a fractional random walk in comparison to a normal random walk. For the case of a ring, we obtain exact analytical results showing that the fractional transition and return probabilities follow a long-range power-law decay, leading to the emergence of Lévy flights on networks. Our general fractional diffusion formalism applies to regular, random, and complex networks and can be implemented from the spectral properties of the Laplacian matrix, providing an important tool to analyze anomalous diffusion on networks.

Figure 1

A random walker performing long-range transitions on a network can move directly from node $i$ to node $j$ with a transition probability given by $w_{i\to j}^{\left(\gamma \right)}$ (the index $\gamma$ refers to a fractional dynamics described in the text). The nodes are three degrees apart, that is, the geodesic distance is three, as indicated by the dashed line. The geodesic distance is the integer number of steps of the shortest path connecting two nodes. Using this long-range dynamics one can contact directly long-distance nodes without the intervention of intermediate nodes and without altering the topology of the network.

Figure 2

Monte Carlo simulation of a discrete-time random walker on a network. We choose for clarity a tree, with $N=100$ nodes, but the qualitative results stand for any network. The discrete time $t$ denotes the number of steps of the random walker as it moves from one node to the next node on the network. This discrete random process is governed by a master equation with a transition probability matrix that gives the probability of moving from node to node. The dynamics starts at $t=0$ from an arbitrary node. We show three discrete times $t=25,50,100$ for three values of the parameter $\gamma =1,0.75,0.5$. Here, we depict one representative realization of a random walker as it navigates from one node to another randomly. The case $\gamma =1$ corresponds to normal random walk leading to normal diffusion. In this case, the random walker can move only locally to nearest neighbors and, as can be seen in the figure, the walker revisits very frequently the same nodes and therefore the exploration of the network is redundant and not very efficient. The cases with $\gamma =0.75,0.5$ correspond to a fractional random walk leading to anomalous diffusion. In this case, the random walker can navigate in a long-range fashion from one node to another arbitrarily distant node. This allows to explore more efficiently the network since the walker does not tend to revisit the same nodes; on the contrary, it tends to explore and navigates distant new regions each time. All this can be seen in the figure for different times, and allow us to make a comparison between a random walker using regular dynamics and fractional dynamics.

Figure 3

Average fractional return probability $p_0^{\left(\gamma \right)}\left(t\right)$ as a function of time for different networks with $N=5000$ nodes and calculated using Eq. (19). (a) A ring, (b) a tree, and (c) a scale-free (SF) network of the Barabási-Albert type [49]. We used different values of $\gamma$ as indicated in the insets.

Figure 4

Average time $\overline{T}$ vs. $\gamma$ calculated from Eq. (23) for different types of networks with $N=5000$ nodes. (a) Large-world networks: ring (1D lattice), the regular network with degree $k=4$ obtained by the Watts-Strogatz (WS) model with rewiring probability $p=0$ [50], a tree, a 2D lattice with dimension $50\times 100$ and periodic boundary conditions. (b) Small-world networks: the WS network used in (a) with rewiring probability $p=0.7$, a scale-free (SF) network of the Barabási-Albert type [49], and Erdős-Rényi (ER) network with $p=logN/N$ [51].