Limits...
Navigation by anomalous random walks on complex networks

View Article: PubMed Central - PubMed

ABSTRACT

Anomalous random walks having long-range jumps are a critical branch of dynamical processes on networks, which can model a number of search and transport processes. However, traditional measurements based on mean first passage time are not useful as they fail to characterize the cost associated with each jump. Here we introduce a new concept of mean first traverse distance (MFTD) to characterize anomalous random walks that represents the expected traverse distance taken by walkers searching from source node to target node, and we provide a procedure for calculating the MFTD between two nodes. We use Lévy walks on networks as an example, and demonstrate that the proposed approach can unravel the interplay between diffusion dynamics of Lévy walks and the underlying network structure. Moreover, applying our framework to the famous PageRank search, we show how to inform the optimality of the PageRank search. The framework for analyzing anomalous random walks on complex networks offers a useful new paradigm to understand the dynamics of anomalous diffusion processes, and provides a unified scheme to characterize search and transport processes on networks.

No MeSH data available.


The measurement logN〈L〉 in the (α, β) parameter plane of (a) the BA model, (b) the (1, 2)-flower model, (c) planar Sierpiński gasket, (d) the (4, 5)-flower model, (e) the “Dolphin” network24, and (f) the e-mail network25.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC5120342&req=5

f3: The measurement logN〈L〉 in the (α, β) parameter plane of (a) the BA model, (b) the (1, 2)-flower model, (c) planar Sierpiński gasket, (d) the (4, 5)-flower model, (e) the “Dolphin” network24, and (f) the e-mail network25.

Mentions: Clearly, from Eq. (7), the cost exponent β plays an important role in controlling the search efficiency for Lévy walks. In order to explore how the optimal search efficiency of a Lévy walk changes with respect to the cost exponent β, we investigate the interplay between β and α for various networks including three synthetic models (the Barabási-Albert (BA) model23, the planar Sierpiński gasket20, and the (u, v)-flower model21) and two real networks (the “Dolphin” network24 and an e-mail network25). Here, for a fair comparison, we calculate the measurement logN〈L〉 in the (α, β) plane for eliminating the size effect of networks. Generally, regions with smaller logN〈L〉 indicate an efficient way of search and transport based on Lévy walks. Figure 3 shows contour maps of logN〈L〉 in the (α, β) plane computed for these selected networks. Interestingly, we find that distinct network structures lead to different patterns in the corresponding (α, β) plane. Specifically, the (α, β) planes generated from networks having the “small-world” characteristics (such as the BA model and the (1, 2)-flower model), demonstrate an “estuary” pattern — implying that Lévy walks are not the optimal way to search when β > 0.4. In contrast, typical fractal networks without the “small-world” property (for example, the planar Sierpiński gasket and the (4, 5)-flower model), result in a striking “flame” in the (α, β) planes, suggesting that there exists an optimal tuning exponent α, which minimizes the traverse distance for a broad range of cost exponents β. However, none of these patterns match the ones found in the Dolphin network and the e-mail network, whose (α, β) planes show “rippled” features, meaning that the optimal exponent α gradually increases with the cost exponent β. The (α, β) plane uncovers the relationship between network structure and the behavior of Lévy walks, which provides information to design more effective search strategies and transport mechanisms in different environments. Note that, for convenience, we choose the cost exponent in the range [0, 1.2] as this can highlight the effect of network structure on the transportation of the Lévy walks. Of course, the cost exponent can take other values outside this range. However, based on the Eq. (7), we find that the profiles of the Lévy walk present a clearly decreasing tendency independent of network structure for the large cost exponent β. In this situation, the Lévy walk is less efficient than the random walk for information diffusion and transportation. For this reason, we do not include the trivial results of the large cost exponents here.


Navigation by anomalous random walks on complex networks
The measurement logN〈L〉 in the (α, β) parameter plane of (a) the BA model, (b) the (1, 2)-flower model, (c) planar Sierpiński gasket, (d) the (4, 5)-flower model, (e) the “Dolphin” network24, and (f) the e-mail network25.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC5120342&req=5

f3: The measurement logN〈L〉 in the (α, β) parameter plane of (a) the BA model, (b) the (1, 2)-flower model, (c) planar Sierpiński gasket, (d) the (4, 5)-flower model, (e) the “Dolphin” network24, and (f) the e-mail network25.
Mentions: Clearly, from Eq. (7), the cost exponent β plays an important role in controlling the search efficiency for Lévy walks. In order to explore how the optimal search efficiency of a Lévy walk changes with respect to the cost exponent β, we investigate the interplay between β and α for various networks including three synthetic models (the Barabási-Albert (BA) model23, the planar Sierpiński gasket20, and the (u, v)-flower model21) and two real networks (the “Dolphin” network24 and an e-mail network25). Here, for a fair comparison, we calculate the measurement logN〈L〉 in the (α, β) plane for eliminating the size effect of networks. Generally, regions with smaller logN〈L〉 indicate an efficient way of search and transport based on Lévy walks. Figure 3 shows contour maps of logN〈L〉 in the (α, β) plane computed for these selected networks. Interestingly, we find that distinct network structures lead to different patterns in the corresponding (α, β) plane. Specifically, the (α, β) planes generated from networks having the “small-world” characteristics (such as the BA model and the (1, 2)-flower model), demonstrate an “estuary” pattern — implying that Lévy walks are not the optimal way to search when β > 0.4. In contrast, typical fractal networks without the “small-world” property (for example, the planar Sierpiński gasket and the (4, 5)-flower model), result in a striking “flame” in the (α, β) planes, suggesting that there exists an optimal tuning exponent α, which minimizes the traverse distance for a broad range of cost exponents β. However, none of these patterns match the ones found in the Dolphin network and the e-mail network, whose (α, β) planes show “rippled” features, meaning that the optimal exponent α gradually increases with the cost exponent β. The (α, β) plane uncovers the relationship between network structure and the behavior of Lévy walks, which provides information to design more effective search strategies and transport mechanisms in different environments. Note that, for convenience, we choose the cost exponent in the range [0, 1.2] as this can highlight the effect of network structure on the transportation of the Lévy walks. Of course, the cost exponent can take other values outside this range. However, based on the Eq. (7), we find that the profiles of the Lévy walk present a clearly decreasing tendency independent of network structure for the large cost exponent β. In this situation, the Lévy walk is less efficient than the random walk for information diffusion and transportation. For this reason, we do not include the trivial results of the large cost exponents here.

View Article: PubMed Central - PubMed

ABSTRACT

Anomalous random walks having long-range jumps are a critical branch of dynamical processes on networks, which can model a number of search and transport processes. However, traditional measurements based on mean first passage time are not useful as they fail to characterize the cost associated with each jump. Here we introduce a new concept of mean first traverse distance (MFTD) to characterize anomalous random walks that represents the expected traverse distance taken by walkers searching from source node to target node, and we provide a procedure for calculating the MFTD between two nodes. We use Lévy walks on networks as an example, and demonstrate that the proposed approach can unravel the interplay between diffusion dynamics of Lévy walks and the underlying network structure. Moreover, applying our framework to the famous PageRank search, we show how to inform the optimality of the PageRank search. The framework for analyzing anomalous random walks on complex networks offers a useful new paradigm to understand the dynamics of anomalous diffusion processes, and provides a unified scheme to characterize search and transport processes on networks.

No MeSH data available.