Anomalous biased diffusion in networks

Abstract

We study diffusion with a bias towards a target node in networks. This problem is relevant to efficient routing strategies in emerging communication networks like optical networks. Bias is represented by a probability $p$ of the packet/particle to travel at every hop towards a site which is along the shortest path to the target node. We investigate the scaling of the mean first passage time (MFPT) with the size of the network. We find by using theoretical analysis and computer simulations that for Random Regular (RR) and Erdős-Rényi (ER) networks, there exists a threshold probability, $p_{th}$, such that for $p<p_{th}$ the MFPT scales anomalously as $N^{\alpha }$, where $N$ is the number of nodes, and $\alpha$ depends on $p$. For $p>p_{th}$ the MFPT scales logarithmically with $N$. The threshold value $p_{th}$ of the bias parameter for which the regime transition occurs is found to depend only on the mean degree of the nodes. An exact solution for every value of $p$ is given for the scaling of the MFPT in RR networks. The regime transition is also observed for the second moment of the probability distribution function, the standard deviation.

13 Pages, To appear in PRE

References in corpus (10)

• Mitigation of Malicious Attacks on Networks
• Network Physiology reveals relations between network topology and physiological function
• First-passage times in complex scale-invariant media
• Scaling of degree correlations and the influence on diffusion in scale-free networks
• Trapping in complex networks
• Ring structures and mean first passage time in networks
• Localization Transition of Biased Random Walks on Random Networks
• Comment on "Localization Transition of Biased Random Walks on Random Networks"
• Fractal structure of a three dimensional Brownian motion on an attractive plane
• Random Walks on Complex Networks

Cited by in corpus (8)

• Heterogeneous continuous time random walks
• Right-side-stretched multifractal spectra indicate small-worldness in networks
• Unraveling the structure of treelike networks from first-passage times of lazy random walkers
• Biased and greedy random walks on two-dimensional lattices with quenched randomness: the "greedy" ant within a disordered environment
• Efficiency of message transmission using biased random walks in complex networks in the presence of traps
• Inferring Tree Structure with Hidden Traps from First Passage Times
• Symbolic walk in regular networks
• Mandala Networks: ultra-robust, ultra-small-world and highly sparse graphs