betaFeedback

Reading v1View latest version

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\mathbin{\mathop{\cup}}\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

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 Zn\mathbb{Z}_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 Section 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 Section 4.

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.

After this, the main remaining task is to prove that from any starting point, the walk on G~n\widetilde{G}_n likely reaches a typical neighbourhood in order log⁡n\log n steps. This poses new challenges, as we need an argument that works for any starting neighbourhood that has a positive probability of appearing in G~n\widetilde{G}_n. The main step in the proof is showing that in a time of order log⁡n\log n the walk crosses at least order log⁡log⁡n\log\log n red edges, hence spreading out sufficiently that it is likely to land at a typical neighbourhood. Since we can only make assumptions that are likely to hold in all neighbourhoods of G~n\widetilde{G}_n, we are not able to approximate the neighbourhood of the starting point with a quasi-tree and assume that all balls that the walk enters have sufficiently nice properties. Instead, we only consider the immediate neighbourhood of the trajectory of the walk and decompose it into independent components called ‘boxes’. We show that a constant proportion of these boxes have a property that ensures that the walk is likely to quickly exit them via a red edge, and even for the rest of the boxes, the walk is unlikely to spend too much time in them. The details of this argument are presented in Section 5.

Notation

Throughout the paper, we assume that r=d≥3r=d\ge3 and consider dd fixed.

Some general notation

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.
  2. [2]Zsuzsanna Baran and Anđela Šarković. Mixing time of the simple random walk on a randomly twisted hypercube. 2025.
  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.DOI
  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.DOI
  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.
  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.
  10. [10]Alessandra Bianchi, Giacomo Passuello, and Matteo Quatropani. Mixing trichotomy for random walks on directed stochastic block models. Electron. J. Probab., 31:Paper No. 27, 42, 2026.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  26. [26]Yuval Peres and Perla Sousi. Mixing times are hitting times of large sets. Journal of Theoretical Probability, 28, 07 2011.
  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
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