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