betaFeedback

WorksMathematics

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 Znd\mathbb{Z}_n^d as follows: for each pair {x,y}\{x,y\} we add an edge with probability Zn/∥x−y∥dZ_n/\|x-y\|^{d} with ZnZ_n chosen so that the average number of added edges to every vertex is 11. When d≥3d\geq 3, we show that with high probability the mixing time is of order log⁡n\log n and that the random walk does not exhibit cutoff.

Introduction

Random graph models trying to mimic the structure of naturally arising networks and capture their properties, in particular the “small-world phenomenon” have been studied for a long time. An early variant was the model of Watts and Strogatz [28] introduced in 1998, where they started with a one-dimensional torus Zn\mathbb{Z}_n with pairs of vertices within a given distance connected, and then they randomly rewired some of the edges. In 2000, Kleinberg [23] considered a model where they started from a two-dimensional torus Zn2\mathbb{Z}_n^2 with pairs of vertices within a given distance also connected, and added some further random (directed) edges, with the connection probabilities decaying as a power of the distance on the torus.

In this paper, we study the mixing properties of a random walk on the ‘small-world network model’ as introduced by Dyer et al. [18] in 2020, defined as follows.

Definition 1.1. Let Gn=(Vn,En)G_n=(V_n,E_n) denote Znd\mathbb{Z}_n^d, a dd-dimensional torus with side length nn, and let G~n=(Vn,En⊔E~n)\widetilde G_n=(V_n,E_n\sqcup\widetilde E_n) be a random (multi)graph obtained as follows. For each pair {x,y}\{x,y\} of distinct vertices, let us include the edge {x,y}\{x,y\} in E~n\widetilde E_n with probability pn,x,y=Zn∥x−y∥rp_{n,x,y}=\frac{Z_n}{\lVert x-y\rVert^r}, independently, where ∥⋅∥\lVert\cdot\rVert denotes the graph distance in GnG_n, and ZnZ_n is chosen such that ∑ypn,x,y=1\sum_y p_{n,x,y}=1 for all xx. We refer to G~n\widetilde G_n as a small-world network graph. In what follows, we almost always drop the subscript nn from the notation.

//

The paper [18] focused on d=2d=2 and proved that for r<2r<2 the mixing time is Θ(log⁡n)\Theta(\log n), for r>2r>2 it is nΩ(1)n^{\Omega(1)} and for r=2r=2 it is O((log⁡n)4)O((\log n)^4). In the r=2r=2 case, it was conjectured that the mixing time is in fact Θ((log⁡n)2)\Theta((\log n)^2).

We see that for r<dr<d a constant fraction of the added edges connect two vertices that lie at a distance of order nn, whereas for r>dr>d shorter edges are strongly preferred. For r=dr=d the distance of the two endpoints of an added edge is uniform over logarithmic scales (i.e. the probability of taking values in [2k,2k+1][2^k, 2^{k+1}] is of the same order for all relevant values of kk). The above results show that there is a phase transition between these two regimes at r=d=2r=d=2. While there has been a lot of recent progress on understanding the mixing time of random walks on random graphs, in the above model, the geometric structure of the added edges poses challenges.

As pointed out in [18], the techniques of that paper could be used to prove that for r>dr>d the mixing time is nΩ(1)n^{\Omega(1)}. We conjecture that when r∈[0,d)r\in[0,d), there is cutoff around a logarithmic time for d≥3d\ge3. We believe that the techniques developed in [22, 1] would be useful in proving cutoff from a typical starting point.

In this work, we focus on the critical choice r=dr=d of the exponent, and we consider the case d≥3d\ge3. Before stating our main result, we recall the definition of mixing time and absolute relaxation time.

Definition 1.2. Let XX be a Markov chain on a finite state space VV, with a unique invariant distribution π\pi. Then for ε∈(0,1)\varepsilon\in(0,1) we define the ε\varepsilon-mixing time of XX as

tmix(ε):=max⁡x∈Vinf⁡{t≥0:dTV(Px(Xt=⋅),π(⋅))≤ε},t_{\mathrm{mix}}(\varepsilon):=\max_{x\in V}\inf\{t\ge0:d_{\mathrm{TV}}(\mathbb{P}_x(X_t=\cdot),\pi(\cdot))\le\varepsilon\},

where dTVd_{\mathrm{TV}} denotes the total variation distance defined as dTV(μ,ν)=12∑x∣μ(x)−ν(x)∣d_{\mathrm{TV}}(\mu,\nu)=\frac{1}{2}\sum_x|\mu(x)-\nu(x)| for two probability distributions μ,ν\mu,\nu on the same state space.

Definition 1.3. We say that a sequence (An)(A_n) of events holds with high probability (whp) if P(An)=1−o(1)\mathbb{P}(A_n)=1-o(1) as n→∞n\to\infty. In what follows, the dependence on nn will often be suppressed from the notation.

Definition 1.4. Let XX be an irreducible Markov chain with transition matrix PP. Its absolute relaxation time is defined as trelabs=11−λ∗t_{\mathrm{rel}}^{\mathrm{abs}}=\frac{1}{1-\lambda^*} where λ∗=max⁡{∣λ∣:λ≠1 is an eigenvalue of P}\lambda^*=\max\{|\lambda|:\lambda\ne1\text{ is an eigenvalue of }P\}.

Now we are ready to state the main result of our paper.

Theorem 1. Let d≥3d\ge3 and consider the small-world graph G~n\widetilde{G}_n as in Definition 1.1, with r=dr=d. There exist positive constants c′c' and C′C', and for all θ∈(0,1)\theta\in(0,1) there exist positive constants c(θ)c(\theta) and C(θ)C(\theta), such that with high probability the following hold.

For all θ∈(0,1)\theta\in(0,1) the mixing time of a simple random walk on G~n\widetilde{G}_n satisfies

c(θ)log⁡n≤tmix(θ)≤C(θ)log⁡n,c(\theta)\log n\le t_{\mathrm{mix}}(\theta)\le C(\theta)\log n,

and the absolute relaxation time of a simple random walk on G~n\widetilde{G}_n satisfies

c′log⁡n≤trelabs≤C′log⁡n.c'\log n\le t_{\mathrm{rel}}^{\mathrm{abs}}\le C'\log n.

Remark 1.5. For the lazy random walk on G~n\widetilde{G}_n, i.e. the Markov chain with transition matrix 12(I+P)\frac{1}{2}(I+P) where PP is the transition matrix of a simple random walk on G~n\widetilde{G}_n, the results of Theorem 1 also hold. We see this by combining Lemmas 1.12, 1.13 and 1.14.

Remark 1.6. In Theorem 1 we establish that with high probability the mixing time and the absolute relaxation time of the walk on G~n\widetilde{G}_n are of the same order, hence by [24 Proposition 18.4] with high probability there is no cutoff. This means that there exist c>0c>0 and ε>0\varepsilon>0 such that with high probability

tmix(ε)tmix(1−ε)≥1+c.\frac{t_{\mathrm{mix}}(\varepsilon)}{t_{\mathrm{mix}}(1-\varepsilon)}\ge1+c.

Remark 1.7. We emphasise that the constants in Theorem 1 depend on the dimension dd. We believe that tmix≲d2log⁡nt_{\mathrm{mix}}\lesssim d^2\log n.

Relation to previous work

Relation to previous work

As already mentioned earlier, the mixing properties of random walks on random graph models have been studied extensively, and often it was established that mixing happens at an entropic time, with cutoff, see for instance [8, 4, 17, 13, 14, 9, 10]. In most of these models, there is no underlying geometric structure, and the random graphs are locally tree-like. Models where the local limit of the random graph is not tree-like have been studied in [22], [1] and [17]. In [22] and [1], the random edges are added according to a uniform perfect matching.

In the model of the present paper, we do not add edges uniformly at random, but the probabilities depend on the length of the edges. This distinguishes this model from the previous ones, as the added edges also have a geometric structure. This model also poses a number of additional challenges. A major source of difficulty is that the number of added edges emanating from a given vertex is neither bounded nor necessarily positive. The graph G~n\widetilde{G}_n has, with high probability, regions with no added edges from them (‘deserts’) and also ones with many vertices with very large degrees (‘hubs’). Because of this, one cannot directly apply the techniques developed in [8] and [22]. In the next section, we explain how we overcome these issues.

The model of long-range percolation, where two vertices xx and yy are connected by an edge with probability 1−exp⁡(−β∥x−y∥−s)1-\exp(-\beta\lVert x-y\rVert^{-s}) for s,β>0s,\beta>0, has a long history. We point out that s=ds=d and β=Θ(1/log⁡N)\beta=\Theta(1/\log N) corresponds to the model we study in this paper. There is a large body of work focusing on the diameter in the finite setting [15, 12], the chemical distance [6, 11] and heat kernel bounds in the infinite setting [16]. We finally mention that [7] focused on the one-dimensional case and established that with high probability the mixing time is at least c(s,β)Ns−1c(s,\beta)N^{s-1} and at most (log⁡N)C(s,β)Ns−1(\log N)^{C(s,\beta)}N^{s-1}. When β≍1\beta\asymp1, from the perspective of chemical distance, the behaviour of long range percolation exhibits drastic change at s=2ds=2d. However, our normalisation, i.e. the choice of ZnZ_n, leads to a different behaviour, where the point at which the mixing time changes is around s=ds=d.

Overview of the proof

In this section, we give an overview of the main ideas of the proof.

As it was often the case in previous works, our first step is to try to locally approximate our random graph G~n\widetilde{G}_n with an auxiliary infinite graph, with a structure that makes the study of a random walk on it more amenable. Unlike many of the previously considered models (Erdős-Rényi graph, configuration model, etc), the graph G~n\widetilde{G}_n is clearly not locally tree-like (since it has the edges of the torus Znd\mathbb{Z}_n^d), so the approximating structure cannot be a tree. This problem was already overcome in [22] by constructing a random tree-like structure TT, called a ‘quasi-tree’, where the added random edges play the role of the edges of the tree (‘long-range edges’) and smaller neighbourhoods of the underlying graph are viewed as vertices of the tree (‘balls’). The tree-like structure of the quasi-tree TT makes the study of the long-term evolution of a walk on it more tractable, and one can prove concentration results about its speed and entropy. Then these results are transferred to the original graph by coupling its local neighbourhoods (chosen to cover the region where the walk is likely to visit by a given time) to agree with those of TT.

Inspired by this, a natural approach would be to try to construct an analogous quasi-tree with the added random edges of G~n\widetilde{G}_n serving as the long-range edges. The difficulty in our case is that in G~n\widetilde{G}_n added edges are more likely to be short (joining vertices that are close in the graph distance of the underlying torus) and form cycles, hence, the neighbourhoods of G~n\widetilde{G}_n cannot be coupled to agree with those of the quasi-tree.

We overcome this problem by treating the ‘short’ and the ‘long’ added edges in G~n\widetilde{G}_n differently, and only using the long ones as the ‘long-range edges’ of the quasi-tree. (The threshold between short and long edges is chosen such that, on average, a constant proportion of the edges belong in each category.) There is a part of our argument where it is helpful to consider a sparse set of random edges (of vanishing density) that are added uniformly at random, so we also reserve a small number of the added edges for this purpose. So overall we partition the added edges into three different categories: we ‘colour’ a small number of them blue, and among the remaining ones, we colour the short ones green and the long ones red. The precise way of colouring is explained in Section 1.3.2.

We study a random walk on a random quasi-tree TT, and we would like to establish a concentration of its speed and entropy by using the tree-like structure of TT. Many of our techniques need assumptions that are satisfied for ‘typical’ neighbourhoods in G~n\widetilde{G}_n, but as mentioned earlier, the graph G~n\widetilde{G}_n can have neighbourhoods with more extreme properties, for example, very few added edges or very high degrees. Our estimates for the walk on TT, including the proof of the essential property that it is transient, are only established in the case that it does not encounter this sort of atypical neighbourhood.

After understanding the behaviour of a walk on the quasi-tree (which is done in § 3), we turn our focus back to the walk on G~n\widetilde{G}_n. Similarly to [1] we would like to bound its mixing time by constructing a random time when the distribution of the walk is close to stationary (and then using a comparison between mixing and hitting times from [3]). To construct this random time, we first wait for the walk to reach a ‘typical’ neighbourhood in G~n\widetilde{G}_n, then we wait for it to cross two blue edges (according to the colouring mentioned above), and finally we run it for O(log⁡n)O(\log n) more steps so it can also reach vertices that do not have a blue edge emanating from them.

We use a method inspired by [1] (based on the ideas of [5]) to show that starting from a typical neighbourhood of G~n\widetilde{G}_n, by the second time the walk crosses a blue edge, its distribution is close to uniform on the vertices that have a blue edge. To approximate the transition probability between two vertices xx and yy at this random time, we consider independent walks from xx and yy and estimate the probability that they meet by approximating the neighbourhoods of xx and yy with independent random quasi-trees and studying the walks on those. This argument is found in § 5.

The ideas presented above are used in a subsequent work [2] establishing the mixing time of the random walk on a twisted hypercube, which is a graph G(n)G^{(n)} recursively obtained by taking two independent copies of G(n−1)G^{(n-1)} and adding an edge between each matched pair in an independent uniformly random perfect matching of their vertices, where G(0)G^{(0)} is just a single vertex. In some sense, this model is a mean-field analogue of the small-world network analysed here, as it also satisfies that the number of added edges (which are all edges in this case) is uniform over logarithmic scales. The twisted hypercube model is substantially less technical to analyse, as this graph is nn-regular, and as one can pick for blue edges just the edges of the perfect matching that was added in the last iteration, and therefore this subsequent work might be helpful for understanding the main ideas behind some proofs presented here.

References

  1. [1]Zsuzsanna Baran, Jonathan Hermon, Anďela Šarković, and Perla Sousi. Phase transition for random walks on graphs with added weighted random matching. Probability Theory and Related Fields, 2024.DOI
  2. [2]Zsuzsanna Baran and Anďela Šarković. Mixing time of the lazy and simple random walk on a randomly twisted hypercube. 2025.arxiv.org/abs/2610.21976
  3. [3]Riddhipratim Basu, Jonathan Hermon, and Yuval Peres. Characterization of cutoff for reversible Markov chains. The Annals of Probability, 45(3):1448 – 1487, 2017.
  4. [4]Anna Ben-Hamou and Justin Salez. Cutoff for nonbacktracking random walks on sparse random graphs. The Annals of Probability, 45(3):1752–1770, 2017.
  5. [5]Anna Ben-Hamou and Justin Salez. Cutoff for nonbacktracking random walks on sparse random graphs. The Annals of Probability, 45(3):1752–1770, 2017.
  6. [6]Itai Benjamini and Noam Berger. The diameter of long-range percolation clusters on finite cycles. Random Structures Algorithms, 19(2):102–111, 2001.
  7. [7]Itai Benjamini, Noam Berger, and Ariel Yadin. Long-range percolation mixing time. Combin. Probab. Comput., 17(4):487–494, 2008.arxiv.org/abs/math/0703872
  8. [8]Nathanaël Berestycki, Eyal Lubetzky, Yuval Peres, and Allan Sly. Random walks on the random graph. The Annals of Probability, 46(1):456 – 490, 2018.
  9. [9]Alessandra Bianchi and Giacomo Passuello. Mixing cutoff for simple random walks on the Chung-Lu digraph. Random Structures Algorithms, 66(1):Paper No. e21277, 20, 2025.arxiv.org/abs/2402.15356
  10. [10]Alessandra Bianchi, Giacomo Passuello, and Matteo Quattropani. Mixing trichotomy for random walks on directed stochastic block models. Electron. J. Probab., 31:Paper No. 27, 42, 2026.arxiv.org/abs/2504.06851
  11. [11]Marek Biskup and Andrew Krieger. Arithmetic oscillations of the chemical distance in long-range percolation on Z^d. Ann. Appl. Probab., 34(3):2986–3017, 2024.
  12. [12]Marek Biskup and Jeffrey Lin. Sharp asymptotic for the chemical distance in long-range percolation. Random Structures Algorithms, 55(3):560–583, 2019.DOI
  13. [13]Charles Bordenave, Pietro Caputo, and Justin Salez. Random walk on sparse random digraphs. Probab. Theory Related Fields, 170(3-4):933–960, 2018.arxiv.org/abs/1508.06600
  14. [14]Charles Bordenave, Pietro Caputo, and Justin Salez. Cutoff at the “entropic time” for sparse Markov chains. Probab. Theory Related Fields, 173(1-2):261–292, 2019.arxiv.org/abs/1611.01079
  15. [15]Don Coppersmith, David Gamarnik, and Maxim Sviridenko. The diameter of a long-range percolation graph. In Mathematics and computer science, II (Versailles, 2002), Trends Math., pages 147–159. Birkhäuser, Basel, 2002.
  16. [16]Nicholas Crawford and Allan Sly. Simple random walk on long range percolation clusters I: heat kernel bounds. Probab. Theory Related Fields, 154(3-4):753–786, 2012.DOI
  17. [17]Bastien Dubail. Cutoff for mixtures of permuted Markov chains: reversible case. 2024.arxiv.org/abs/2401.03937
  18. [18]Martin E. Dyer, Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum, and Eric Vigoda. Random walks on small world networks. ACM Transactions on Algorithms, 2020.
  19. [19]Alan Frieze and Michał Karoński. Introduction to Random Graphs. 2015.DOI
  20. [20]Jonathan Hermon. A technical report on hitting times, mixing and cutoff. ALEA Lat. Am. J. Probab. Math. Stat., 15(1):101–120, 2018.arxiv.org/abs/1501.01869
  21. [21]Jonathan Hermon, Ben Langer, and Jens Malmquist. On quantitative near-bipartiteness: mixing, parity breaking, max-cut and eigenvalue gap. In preparation.
  22. [22]Jonathan Hermon, Allan Sly, and Perla Sousi. Universality of cutoff for graphs with an added random matching. The Annals of Probability, 50(1):203 – 240, 2022.arxiv.org/abs/2008.08564
  23. [23]Jon Kleinberg. The small-world phenomenon: an algorithmic perspective. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC ’00, page 163–170, New York, NY, USA, 2000. Association for Computing Machinery.
  24. [24]David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov chains and mixing times. American Mathematical Society, 2006.
  25. [25]Russell Lyons and Yuval Peres. Probability on Trees and Networks. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2017.DOI
  26. [26]Yuval Peres and Perla Sousi. Mixing times are hitting times of large sets. Journal of Theoretical Probability, 28, 07 2011.arxiv.org/abs/1108.0133
  27. [27]Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
  28. [28]Duncan J. Watts and Steven H. Strogatz. Collective dynamics of ‘small-world’ networks. Nature, 1998.

Paper details

vlnc:W_yzjctrys
Version
v2 · latest
Published
Added
License
CC BY 4.0
Usage

views · 15

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents