Biased random walks on complex networks: the role of local navigation rules
arXiv:0709.2231 · doi:10.1103/PhysRevE.80.016107
Abstract
We study the biased random walk process in random uncorrelated networks with arbitrary degree distributions. In our model, the bias is defined by the preferential transition probability, which, in recent years, has been commonly used to study efficiency of different routing protocols in communication networks. We derive exact expressions for the stationary occupation probability, and for the mean transit time between two nodes. The effect of the cyclic search on transit times is also explored. Results presented in this paper give the basis for theoretical treatment of the transport-related problems on complex networks, including quantitative estimation of the critical value of the packet generation rate.
5 pages (Phys. Rev style), 3 Figures
References in corpus (4)
Cited by in corpus (45)
- Critical phenomena in complex networks
- Random walks and diffusion on networks
- Memory in network flows and its effects on spreading dynamics and community detection
- A spectrum of routing strategies for brain networks
- Maximal-entropy random walks in complex networks with limited information
- Random walks on weighted networks
- Information filtering via preferential diffusion
- Characteristic times of biased random walks on complex networks
- Flow graphs: interweaving dynamics and structure
- Mean-field diffusive dynamics on weighted networks
- Random walks in weighted networks with a perfect trap: An application of Laplacian spectra
- Efficient exploration of multiplex networks
- Extreme events and event size fluctuations in biased random walks on networks
- Asymptotic analysis of first passage time in complex networks
- Scaling of human behavior during portal browsing
- Mean first-passage time for maximal-entropy random walks in complex networks
- Optimal and suboptimal networks for efficient navigation measured by mean-first passage time of random walks
- A minimal model for congestion phenomena on complex networks
- Random walks in time-varying networks with memory
- EvoLearner: Learning Description Logics with Evolutionary Algorithms
- Biased diffusion on Japanese inter-firm trading network: Estimation of sales from network structure
- Mean encounter times for multiple random walkers on networks
- Anomalous biased diffusion in networks
- Random walks with stochastic resetting in complex networks: a discrete time approach
- Multitarget search on complex networks: A logarithmic growth of global mean random cover time
- From random walks on networks to nonlinear diffusion
- Exact eigenvalue spectrum of a class of fractal scale-free networks
- Diffusion-annihilation proecesses in weighted scale-free networks with identical degree sequence
- Smart random walkers: the cost of knowing the path
- Random Walk with Memory on Complex Networks
- Biased random walkers and extreme events on the edges of complex networks
- Optimal exploration of random walks with local bias on networks
- Theoretical approach and impact of correlations on the critical packet generation rate in traffic dynamics on complex networks
- Self-segregation in heterogeneous metapopulation landscapes
- A measure of dissimilarity between diffusive processes on networks
- Multiple predator based capture process on complex networks
- Random walk with priorities in communication-like networks
- Liouville Fock state lattices and potential simulators
- Mean field approximation for biased diffusion on Japanese inter-firm trading network
- The Pendulum Arrangement: Maximizing the Escape Time of Heterogeneous Random Walks
- Sampling a Network to Find Nodes of Interest
- "Spectrally gapped" random walks on networks: a Mean First Passage Time formula
- Evanescent random walker on networks: Hitting times, budget renewal, and survival dynamics
- Core-biased random walks in complex networks
- Comparative study of random walks with one-step memory on complex networks