Biased random walks in complex networks: the role of local navigation rules.

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 the 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 provide the basis for a theoretical treatment of transport-related problems in complex networks, including quantitative estimation of the critical value of the packet generation rate.

• Publication year

  2007

• Venue

  Physical review. E, Statistical, nonlinear, and soft matter physics

• Publication date

  2007-09-14

• Fields of study

  Mathematics, Physics, Computer Science, Medicine

• Identifiers
  DOI 10.1103/PhysRevE.80.016107arXiv 0709.2231PMID 19658774
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Localization transition of biased random walks on random networks.

  2007cited by this paper
• Traffic of particles in complex networks.

  2006cited by this paper
• Traffic dynamics based on local routing protocol on a scale-free network.

  2006cited by this paper
• Networks with given two-point correlations: hidden correlations from degree correlations.

  2005cited by this paper
• Navigating networks with limited information.

  2004cited by this paper
• Exploring complex networks by walking on them.

  2004cited by this paper
• Random walks on complex networks.

  2003cited by this paper
• Random Graphs as Models of Networks

  2002cited by this paper
• Diffusion and Reactions in Fractals and Disordered Systems

  2002cited by this paper
• Brownian Motion: Fluctuations, Dynamics, and Applications

  2002cited by this paper
• A guide to first-passage processes

  2001cited by this paper
• Diffusion and Reactions in Fractals and Disordered Systems: References

  2000cited by this paper

• Walking Through Complex Spatial Patterns of Climate and Conflict-Induced Displacements

  2025cites this paper
• Computational Geometry with Probabilistically Noisy Primitive Operations

  2025cites this paper
• Biased random walks on networks with stochastic resetting.

  2025cites this paper
• Network classification through random walks

  2025cites this paper
• Evanescent random walker on networks: Hitting times, budget renewal, and survival dynamics.

  2025cites this paper
• Random walks with stochastic resetting in complex networks: A discrete-time approach.

  2024cites this paper
• Local Navigation for an Industrial Warehouse Robot

  2024cites this paper
• Impact of local navigation rules on biased random walks in multiplex Markov chains

  2024cites this paper
• Random search processes on complex networks: from a static target to a moving object

  2024cites this paper
• BloomWalk and CuckooWalk: Fast Random Walks Utilizing Probabilistic Data Structure

  2024cites this paper
• Cascading failure model and resilience-based sequential recovery strategy for complex networks

  2024cites this paper
• Comparative study of random walks with one-step memory on complex networks

  2024cites this paper
• Signal propagation in complex networks

  2023cites this paper
• Random Walks on Networks with Centrality-Based Stochastic Resetting

  2023cites this paper
• A first passage under resetting approach to income dynamics

  2023cites this paper
• Traffic-Driven Explosive Synchronization with Adaptive Local Routing in Complex Networks

  2023cites this paper
• Random Walks Performed by Topologically-Specific Agents on Complex Networks

  2023cites this paper
• The Fate of the American Dream: A First Passage Under Resetting Approach to Income Dynamics

  2022cites this paper
• From random walks on networks to nonlinear diffusion.

  2022cites this paper
• The Nature of Complex Networks

  2022cites this paper
• "Spectrally gapped" random walks on networks: a Mean First Passage Time formula

  2021cites this paper
• Random walks on weighted networks: a survey of local and non-local dynamics

  2021influential citation
• A new link prediction in multiplex networks using topologically biased random walks

  2021cites this paper
• Potential-driven random walks on interconnected systems.

  2021cites this paper
• A convex principle of search time for a multi-biased random walk on complex networks

  2021cites this paper
• Trajectories through temporal networks

  2021cites this paper
• Lowest-degree preference random walks on complex networks

  2021cites this paper
• Self-segregation in heterogeneous metapopulation landscapes.

  2021cites this paper
• Biased random walkers and extreme events on the edges of complex networks.

  2021cites this paper
• EvoLearner: Learning Description Logics with Evolutionary Algorithms

  2021cites this paper
• The Pendulum Arrangement: Maximizing the Escape Time of Heterogeneous Random Walks

  2020cites this paper
• Static and dynamic properties of selected stochastic processes on complex networks

  2020influential citation
• First-passage times to quantify and compare structural correlations and heterogeneity in complex systems

  2020cites this paper
• Quantifying ethnic segregation in cities through random walks

  2020cites this paper
• Mean encounter times for multiple random walkers on networks.

  2020cites this paper
• Random walks in time-varying networks with memory.

  2020cites this paper
• Predator-prey games on complex networks

  2019cites this paper
• Random walk with memory on complex networks.

  2019cites this paper
• Traffic-driven epidemic spreading and its control strategies

  2019cites this paper
• Mean first passage time on a family of weighted directed hierarchical scale-free networks

  2019cites this paper
• Impact of structural balance on Self-Avoiding Pruning Walk

  2019cites this paper
• Locating People of Interest in Social Networks

  2019cites this paper
• Universal principles governing multiple random searchers on complex networks: The logarithmic growth pattern and the harmonic law.

  2018cites this paper
• Predicting search time when hunting for multiple moving targets: A recursive harmonic law.

  2018cites this paper
• Diffusion-localization transition caused by nonlinear transport on complex networks

  2018cites this paper
• A spectrum of routing strategies for brain networks

  2018cites this paper
• Sampling dark networks to locate people of interest

  2018cites this paper
• Core-biased random walks in networks

  2018cites this paper
• Patient treatment prediction by continuous time random walk inside complex system

  2018cites this paper
• Multitarget search on complex networks: A logarithmic growth of global mean random cover time.

  2017cites this paper
• Local Diffusion Versus Random Relocation in Random Walks

  2017cites this paper
• Sampling a Network to Find Nodes of Interest

  2017cites this paper
• Exploring activity-driven network with biased walks

  2017cites this paper
• Persistent Random Search on Complex Networks

  2017cites this paper
• Optimizing Network Discovery with Clever Walks

  2017cites this paper
• Mean First Passage Time of Preferential Random Walks on Complex Networks with Applications

  2017influential citation
• Shortest paths to success: Network indicators of performance in innovation ecosystems

  2017cites this paper
• Topologically biased random walk for diffusions on multiplex networks

  2017cites this paper
• Seeing Red: Locating People of Interest in Networks

  2017cites this paper
• The structure and dynamics of multiplex networks

  2017cites this paper
• Multitarget search on complex networks : A logarithmic growth of global mean random search time

  2017cites this paper
• Core-biased random walks in complex networks

  2017cites this paper
• Algorithms and Models for Network Data and Link Analysis

  2016cites this paper
• A formal model based on Game Theory for the analysis of cooperation in distributed service discovery

  2016cites this paper
• Predicting Cyclone Induced Flood: A Comprehensive Case Study

  2016cites this paper
• Capturing the interplay of dynamics and networks through parameterizations of Laplacian operators

  2016cites this paper
• Multiple-predators-based capture process on complex networks

  2016influential citation
• Random walks and diffusion on networks

  2016cites this paper
• Network exploration using true self-avoiding walks.

  2016cites this paper
• Steering the Random Surfer on Directed Webgraphs

  2016cites this paper
• First Arrival Time for Natural Disasters Modelled as Biased Networks

  2016cites this paper
• Natural Disasters, When Will They Reach Me?

  2016cites this paper
• Effective information spreading based on local information in correlated networks

  2016cites this paper
• Coupling entropy of co-processing model on social networks

  2015cites this paper
• Random surfers on a web encyclopedia

  2015cites this paper
• Effects of random rewiring on the degree correlation of scale-free networks

  2015cites this paper
• Biased random walks on multiplex networks

  2015cites this paper
• Efficient exploration of multiplex networks

  2015cites this paper
• Extraction of conjugate main-stream structures from a complex network flow.

  2015cites this paper
• Resource Constrained Randomized Coverage Strategies for Unstructured Networks

  2015cites this paper
• Internet: Topology and Modeling

  2015cites this paper
• Mean first return time for random walks on weighted networks

  2015cites this paper
• Efficiency-Controllable Random Walks on a Class of Recursive Scale-Free Trees with a Deep Trap

  2015cites this paper
• WITHDRAWN: Biased random walk in time-varying network

  2015cites this paper
• Analysis of Strategies to Promote Cooperation in Distributed Service Discovery

  2014cites this paper
• Suppressing traffic-driven epidemic spreading by use of the efficient routing protocol

  2014cites this paper
• Effect of Mixing Assortativity on Extreme Events in Complex Networks

  2014cites this paper
• Full eigenvalues of the Markov matrix for scale-free polymer networks.

  2014cites this paper
• Information entropy of diffusion processes on complex networks

  2014cites this paper
• Probing and shaping the information transfer of noise-perturbed complex networks via Markov Chain analysis

  2014cites this paper
• Mean first-passage time for maximal-entropy random walks in complex networks

  2014cites this paper
• Trapping time of weighted-dependent walks depending on the weight factor

  2014cites this paper
• Estimating Mean First Passage Time of Biased Random Walks with Short Relaxation Time on Complex Networks

  2014cites this paper
• Networks with Memory

  2013cites this paper
• Stochastic resonance for information flows on hierarchical networks

  2013cites this paper
• Métodos de física estadística en el procesamiento de imágenes: caminantes aleatorios, difusión y modelo de potts.

  2013influential citation
• Heterogeneity and subjectivity in binary-state opinion formation systems

  2013cites this paper
• Comparison of multiple random walks strategies for searching networks

  2013cites this paper
• Effects of target routing model on the occurrence of extreme events in complex networks

  2013cites this paper
• Random walks in weighted networks with a perfect trap: an application of Laplacian spectra.

  2013cites this paper