Mixing Time of Random Walk on Poisson Geometry Small World

Abstract

This paper focuses on the problem of modeling for small world effect on complex networks. Let's consider the supercritical Poisson continuous percolation on $d$-dimensional torus $T_n^d$ with volume $n^d$. By adding "long edges (short cuts)" randomly to the largest percolation cluster, we obtain a random graph ${\mathcal{G}}_n$. In the present paper, we first prove that the diameter of ${\mathcal{G}}_n$ grows at most polynomially fast in $\ln n$ and we call it the Poisson Geometry Small World. Secondly, we prove that the random walk on ${\mathcal{G}}_n$ possesses the rapid mixing property, namely, the random walk mixes in time at most polynomially large in $\ln n$.

23 pages

References in corpus (1)

• The structure and function of complex networks