Sood, Grassberger (2007)

Authors: Vishal Sood and Peter Grassberger
Published in: Physical Review Letters 99, 098701 (August 31, 2007)
More: PDF | arXiv

Properties of random walks on regular lattices have been studied for a long time. Recurrence transience of a random walk depends on the structure of the underlying graph, which tells us that if the graph grows outwards from the starting node of the random walk, faster than a 3D lattice, the walks will be transient. Such graphs include Galton-Watson trees with branching ratio larger than 1. Thus we formulate a biased random walk on a general graph, in order to study the effect of its topology on the properties of a random walk. Our biased walk is a generalization of the lambda-biased walk studied in probability theory literature in the recent years. We show that a critical bias strength exists, above which the random walks are recurrent, and for small bias transient. We show simulation results on Erdos-Renyi random graphs and verify the derived critical bias strength. We discuss applications to message traffic on the internet and localization of wave-packets in quantum mechanics.

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 a critical point in the sense that quantities like the return probability P(t) show power laws, 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.

@article{sood2007ltb,
title={{Localization Transition of Biased Random Walks on Random Networks}},
author={Sood, V. and Grassberger, P.},
journal={Physical Review Letters},
volume={99},
number={9},
pages={98701},
year={2007},
publisher={APS}
}