Random walk on the small-world network model in 3 or more dimensions

Abstract

We study the mixing time of a simple random walk on the small-world network defined by adding edges to ${\mathbb{Z}}_n^d$ as follows: for each pair $\{x,y\}$ we add an edge with probability $Z_n/\Vert x-y{\Vert }^d$ with $Z_n$ chosen so that the average number of added edges to every vertex is $1$. When $d\ge 3$, we show that with high probability the mixing time is of order~$\log n$ and that the random walk does not exhibit cutoff.