Random Walks on Small World Networks

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\ge 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((\log n{)}^2)$ when $r=2$ and $n^{\mathrm{\Omega }(1)}$ when $r\mathrm{\ne }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 $\mathrm{\Theta }(\log n)$ for $r<2$, $O((\log n)^4)$for$r=2$and$n^{\Omega(1)}$for$r>2$.