This paper is about the mixing time of a simple random walk on the so-called scale-free percolation random graph (SFP). This random graph \(G_{N}\) on which the random walk will take place is defined as follows: one takes vertex set \(\{1,2,\ldots N\}\) thought of as ordered round a circle. One assigns to each vertex \(i\) independently of all other vertices a weight \(W_{i}\), where \(W_{i}\) has a Pareto distribution with parameter \(\tau>1\), that is \(\mathbb{P}(W_{i}\geq t)=t^{-(\tau-1)}\) for \(t>1\) and is 1 otherwise. Note that this is a heavy-tailed distribution. We then say that two vertices \(x\) and \(y\) are adjacent with probability \(1-\exp(W_{x}W_{y}\left \| x-y \right \|^{-\alpha} )\). Here, the distance between \(x\) and \(y\), \(\left \| x-y \right\|\) is the torus distance between them i.e. \(\min \{\vert x-y\vert, N-\vert x-y\vert \}\). To ensure connectedness we also insist each vertex is adjacent to the one following it on the circle. There are thus two key parameters: \(\tau\) indicating how heavy-tailed the weights of the vertices are, and \(\alpha\) controlling how important the torus distance between the two vertices is to their chance of being adjacent. We put \(\gamma=\alpha (\tau-1)\), one can show that the degrees of vertices have a heavy-tailed distribution with parameter \(\gamma\). The simple random walk is a lazy one (to avoid periodicity issues): so the one-step transition matrix has \(P(x,x)=1/2\), if \(x\) and \(y\) are adjacent in the SFP we have \(P(x,y)=1/(2D_{x})\) where \(D_{x}\) is the degree of \(x\), and if \(x\) and \(y\) are not adjacent \(P(x,y)=0\). As usual we are interested in the mixing time \(t_{mix}(G_{N})=\inf \{n\in \mathbb{N}: d(n) < \frac{1}{4}\}\) where \(d(n)=\sup_{x\in \{1,2,\ldots N\}} \left \| P^{n}(x,\cdot)-\pi(\cdot) \right \|_{TV}\) where as usual the total variation distance \(\left \| \nu-\mu\right \|_{TV}\) between distirbutions \(\nu\) and \(\mu\) is \(\frac{1}{2}\sum_{x\in [n]}\vert \nu(x)-\mu(x)\vert\). Important background to the results in this paper is [\textit{I. Benjamini} et al., Comb. Probab. Comput. 17, No. 4, 487--494 (2008; Zbl 1157.60084)] where the analogous problem is studied on the long-range percolation graph, which is the case where all weights \(W_{i}\) are equal to one (in essence, the case \(\tau=\infty\)). In that paper there is a striking phase transition around \(\alpha=2\): for \(1<\alpha<2\) we have mixing time (up to polylogarithmic factors) \(N^{\alpha-1}\) but for \(\alpha>2\) the mixing time (up to polylogarithmic factors) is \(N^{2}\). The authors show an almost complete phase diagram for both parameters \(\alpha\) and \(\tau\). To give some flavour of the results, and noting that results are only stated up to correcting factors, for example is it shown that in the first significant case when \(\gamma<1\) we have \(t_{\mathrm{mix}}(G_{N})\) is bounded above by a power of \(\log(N)\). In the second, perhaps most interesting, regime \(1<\gamma<2\) and \(\tau<2\), \(t_{\mathrm{mix}}(G_{N})\) is of order \(N^{\gamma-1}\) and the proof depends on a bootstrapping procedure to relate it to a model with \(\gamma<1\). Here, the presence of hubs (vertices of very high degree) can speed out the mixing. The third case is \(\alpha \in (1,2)\) and \(\tau>2\) where the authors can only show that \(t_{\mathrm{mix}}(G_{N})\) is of order at least \(N^{\alpha-1}\) though they conjecture that a similar upper bound holds up to polylogarithmic factors and give some supporting evidence. The fourth case is \(\alpha>2\) and \(\gamma>2\) when \(t_{\mathrm{mix}}(G_{N})\) is of order \(N^{2}\). A substantial range of techniques have to be used to cover all the various results proven.
- Bootstrap percolation on geometric inhomogeneous random graphs
- Clustering and the hyperbolic geometry of complex networks
- Cutoff phenomena for random walks on random regular graphs
- Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs
- Geometric inhomogeneous random graphs
- Graph distances in scale-free percolation: the logarithmic case
- scientific article; zbMATH DE number 43570 (Why is no real title available?)
- Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
- Large degrees in scale-free inhomogeneous random graphs
- Large deviations of sums of independent random variables
- Long-Range Percolation Mixing Time
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- Notes on random walks in the Cauchy domain of attraction
- On a conditionally Poissonian graph process
- Random hyperbolic graphs: degree sequence and clustering (extended abstract)
- Random walks on small world networks
- Random walks on the random graph
- Recurrence versus transience for weight-dependent random connection models
- Rumors spread slowly in a small-world spatial network
- Scale-free percolation
- Scale-free percolation in continuous space: quenched degree and clustering coefficient
- Scale-free percolation in continuum space
- Simple random walk on long range percolation clusters. I: Heat kernel bounds
- Spatial preferential attachment networks: power laws and clustering coefficients
- Spectral gap of random hyperbolic graphs and related parameters
- Structures in supercritical scale-free percolation
- The age-dependent random connection model
- The diameter of long-range percolation clusters on finite cycles
- Ultra-small scale-free geometric networks
This page was built for publication: Scale-free percolation mixing time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6145597)
