Random Walks on Small World Networks

Abstract

We study the mixing time of random walks on small-world networks modelled as follows: starting with the 2-dimensional periodic grid, each pair of vertices {u,v} with distance d>1 is added as a "long-range" edge with probability proportional to d^(-r), where r>=0 is a parameter of the model. Kleinberg studied a close variant of this network model and proved that the decentralised routing time is O((logn)^2) when r=2 and n^Ω(1) when r\neq 2. Here, we prove that the random walk also undergoes a phase transition at r=2, but in this case the phase transition is of a different form. We establish that the mixing time is Θ(logn) for r<2, O((logn)^4) for r=2 and n^{Ω(1)} for r>2.

Joint work with Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, and Eric Vigoda.