Localization Transition of Biased Random Walks on Random Networks

Abstract

We study random walks on large random graphs that are biased towards a randomly chosen but fixed target node. We show that a critical bias strength b_c exists such that most walks find the target within a finite time when b>b_c. For b<b_c, a finite fraction of walks drifts off to infinity before hitting the target. The phase transition at b=b_c is second order, but finite size behavior is complex and does not obey the usual finite size scaling ansatz. By extending rigorous results for biased walks on Galton-Watson trees, we give the exact analytical value for b_c and verify it by large scale simulations.

4 pages, includes 4 figures

References in corpus (5)

• Emergence of scaling in random networks
• Resilience of the Internet to random breakdowns
• Scale-Free Networks are Ultrasmall
• Self-Assembly of Information in Networks
• Transition to Localization of Biased Walkers in a Randomly Absorbing Enviroment

Cited by in corpus (14)

• Critical phenomena in complex networks
• Biased random walks on complex networks: the role of local navigation rules
• Network dynamics of innovation processes
• Laplacian spectra of complex networks and random walks on them: Are scale-free architectures really important?
• Extreme events and event size fluctuations in biased random walks on networks
• Localizations on Complex Networks
• Heterogeneous continuous time random walks
• Comment on "Localization Transition of Biased Random Walks on Random Networks"
• Anomalous biased diffusion in networks
• Inter-arrival times of message propagation on directed networks
• Smart random walkers: the cost of knowing the path
• Clustering-induced localization of quantum walks on networks
• Path Counting on Tree-like Graphs with a Single Entropic Trap: Critical Behavior and Finite Size Effects
• An integrated model of traffic, geography and economy in the Internet