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 (1)

• Self-Assembly of Information in Networks

Cited by in corpus (4)

• Critical phenomena in complex networks
• Laplacian spectra of complex networks and random walks on them: Are scale-free architectures really important?
• Comment on "Localization Transition of Biased Random Walks on Random Networks"
• An integrated model of traffic, geography and economy in the Internet