betaFeedback

WorksMathematics

Cutoff for Simple Random Walk on Preferential Attachment Graphs

Abstract

We consider simple random walk on the sequential affine preferential attachment graphs with fixed parameters m≥2m\ge2 and δ≥0δ\ge0. We prove the walk has total-variation cutoff, and for every fixed ε∈(0,1)\varepsilon\in(0,1), tmix(n)(ε)=log⁡nνd+OP ⁣(log⁡n), t_{\mathrm{mix}}^{(n)}(\varepsilon) =\frac{\log n}{νd} +O_{\mathbb P}\!\left(\sqrt{\log n}\right), where ν>0ν>0 is the walk speed and d>0d>0 is the entropy per level of harmonic measure on the Pólya–point tree, the local weak limit of the graph. Thus cutoff occurs at the entropic time. Entropic cutoff was previously established for a range of random graph models including configuration models under mild degree assumptions and on Erdős–Rényi random graphs for typical starting points. We extend the harmonic-measure approach to preferential attachment, accounting for its age-dependent structure and hubs of polynomial degree. The local weak limit, the Pólya–point tree, provides a more tractable setting for analyzing the walk. The proof combines regeneration estimates on the local limit tree, a quantitative graph–tree coupling on the mixing-time scale, and control of hub excursions. We show that shortly before the cutoff time its distribution is close in total variation distance to a measure with small L∞L^\infty distance from stationarity. When m≥2m\ge2, the spectral gap is bounded away from zero with high probability which completes the upper-bound coupling argument.

Introduction

Preferential attachment is a widely studied model of growing networks with power-law degree distributions [1, 8]. Vertices arrive successively and connect preferentially to vertices of high degree. We study the mixing time of simple random walk on these graphs. Our main result identifies the worst-case mixing time and proves cutoff: the total-variation distance to equilibrium drops from near one to near zero in a time interval negligible compared with the mixing time. The cutoff time is of order log⁡n\log n, with the leading constant determined by the speed and harmonic-measure entropy of random walk on the local limiting tree.

We consider the sequential affine model, in which each new vertex sends m≥2m \ge2 edges to older vertices, chosen sequentially with probabilities proportional to their current degrees plus δ≥0\delta\ge0. The limiting probability of degree kk is asymptotic to a positive constant times k−(3+δ/m)k^{-(3+\delta/m)} as k→∞k \to\infty, and fixed early vertices have degrees growing on the polynomial scale nm/(2m+δ)n^{m/(2m+\delta)} as the number nn of vertices increases [6 Lemmas 5.1–5.2]. Thus the parameter range includes the infinite-variance case δ=0\delta=0, while polynomial-degree hubs persist when δ>0\delta>0 and the limiting variance is finite. These hubs have much greater stationary mass than a typical vertex, since the stationary distribution is proportional to degree. Vertex ages also influence the laws of neighboring vertices and the conditional distribution of unrevealed edges.

The local weak limit around a uniformly chosen vertex is the Pólya–point tree [6]. This is a random branching tree whose offspring laws depend on auxiliary random variables which represent normalized birth times, called ages, and on whether a vertex is older or younger than its parent. Simple random walk on this tree is transient and its loop erasure is an infinite ray. The conditional law of that ray given the tree is its harmonic measure. This measure is far from uniform. The contrast with volume growth is particularly pronounced in the critical case δ=0\delta=0: neighborhoods in the Pólya–point tree grow faster than exponentially, and the diameter of the preferential attachment is O(log⁡n/log⁡log⁡n)O(\log n/\log\log n) [7]. However, for every δ≥0\delta\ge0, the harmonic measure is concentrated on a subtree with only exponential growth. We let d>0d > 0 be the entropy per level of harmonic measure and so informally, a typical ray segment of length kk, chosen according to harmonic measure, has harmonic mass exp⁡{−dk+o(k)}\exp\{-dk+o(k)\}. Also, let ν>0\nu> 0 denote the speed of the walk. The walk reaches depth about νt\nu t at time tt so its entropy therefore grows at rate νd\nu d. Setting exp⁡(νdt)≈n\exp(\nu d t) \approx n suggests the mixing scale.

Figure 1. An illustrative preferential attachment variant. Vertex area is proportional to degree (hence stationary mass); color indicates birth order, from purple (early) to orange (late).

Let GnG_n be the preferential attachment graph defined formally in Definition 2.1. Let PnP_n be its simple random walk transition matrix and πn(v)=deg⁡(v)/(2m(n−1))\pi_n(v) = \deg(v)/(2m(n-1)) its stationary distribution. For an integer t≥0t \ge0 and ε∈(0,1)\varepsilon\in(0,1), write

dn(t)=max⁡x∈V(Gn)∥Pnt(x,⋅)−πn∥TV,tmix(n)(ε)=min⁡{t≥0:dn(t)≤ε},d_n(t) = \max_{x \in V(G_n)} \|P_n^t(x,\cdot)-\pi_n\|_{\mathrm{TV}}, \qquad t_{\mathrm{mix}}^{(n)}(\varepsilon) = \min\{t \ge0 : d_n(t) \le\varepsilon\},

and set dn(t)=dn(⌊t⌋)d_n(t)=d_n(\lfloor t\rfloor) for real t≥0t \ge0. We say that the walks exhibit cutoff at tn∗t_n^* with window wn=o(tn∗)w_n=o(t_n^*) if, for every ε∈(0,1)\varepsilon\in(0,1),

lim⁡γ→∞lim inf⁡n→∞P(dn(tn∗−γwn)≥1−ε)=1,lim⁡γ→∞lim inf⁡n→∞P(dn(tn∗+γwn)≤ε)=1.(1)\lim_{\gamma\to\infty}\liminf_{n \to\infty}\mathbb{P}\left(d_n(t_n^*-\gamma w_n)\ge1-\varepsilon\right)=1,\qquad\lim_{\gamma\to\infty}\liminf_{n \to\infty}\mathbb{P}\left(d_n(t_n^*+\gamma w_n)\le\varepsilon\right)=1. \tag*{(1)}

Here P\mathbb{P} denotes the graph law.

Theorem 1.1 (Cutoff for SRW on preferential attachment). Fix m≥2m \ge2 and δ≥0\delta\ge0, and let GnG_n be the preferential attachment graph of Definition 2.1. Let ν∈(0,1]\nu\in(0,1] and d∈(0,∞)d \in(0,\infty) be the speed and the entropy per level of harmonic measure of simple random walk on the Pólya–point tree, defined in (24) and (33), and set tn∗:=log⁡n/(νd)t_n^* := \log n/(\nu d). Simple random walk on GnG_n exhibits cutoff at tn∗t_n^* with a window of order at most log⁡n\sqrt{\log n}. Equivalently, for every fixed ε∈(0,1)\varepsilon\in(0,1),

tmix(n)(ε)=log⁡nνd+OP(log⁡n).t_{\mathrm{mix}}^{(n)}(\varepsilon)=\frac{\log n}{\nu d}+O_{\mathbb{P}}(\sqrt{\log n}).

The lower bound in Proposition 6.1 already holds for a uniformly chosen starting vertex, whereas the upper bound is uniform over all starting vertices, including the hubs. Thus typical and worst starting vertices have the same leading mixing time. The fluctuation estimates are used to obtain a cutoff window of order at most log⁡n\sqrt{\log n}.

Related results

On random regular graphs of fixed degree at least three, simple random walk exhibits cutoff when the distance traveled on the limiting regular tree reaches the typical distance between graph vertices [17]. Conditional on its distance from the root, the tree walk is uniform on that level. For nonregular trees, the distribution of mass within a level also matters. Indeed, conditional on survival, harmonic measure on a supercritical Galton–Watson tree with a nonconstant offspring distribution of finite mean has dimension strictly smaller than that of the tree boundary [18]. The harmonic-measure dimension, together with the walk speed, determines the cutoff location from a typical vertex of the supercritical Erdős–Rényi giant and of configuration models under suitable degree assumptions [5]. A similar harmonic-measure approach is used in [16] to describe the cutoff time by the speed and entropy of random walk for graphs with an added random matching, through an auxiliary quasi-tree.

Entropic methods based on trajectory weights have also been developed for non-backtracking walks on configuration models [4], random walks on directed configuration models [9, 11], and more general sparse random Markov chains [10]. On the forward tree approximations used in these arguments, the probability of reaching a vertex is the product of the original walk’s one-step transition probabilities along its ancestral path. In our undirected setting, returning excursions make harmonic weights depend on escape probabilities in the descendant subtrees.

Passing from a typical starting vertex to the worst one requires additional control of exceptional neighborhoods. Worst-start cutoff was established for configuration models with minimum degree at least three, a finite second degree moment, and a degree-tail condition giving a sufficiently small subpolynomial maximum degree [3]. Their proof uses the degree assumptions to control small neighborhoods around every vertex, then applies tree couplings and concentration estimates to the walk beyond these neighborhoods. In preferential attachment, polynomial-degree hubs violate the neighborhood-size bounds used in this argument. Moreover, uniform pairing of half-edges is replaced by attachment probabilities that depend on ages and previous revelations. The case m=2m = 2 also falls outside the minimum-degree-three hypothesis and requires using the structure imposed by attachment.

For preferential attachment, earlier work establishes several geometric estimates relevant to mixing. Constant conductance was proved for a standard degree-proportional model [19]. A logarithmic mixing bound for the lazy walk is used in the cover-time analysis [13], while large-set expansion for the present model was proved in [15]. We establish an absolute spectral gap with high probability, uniformly over δ≥0\delta\ge0, showing that there are no eigenvalues too close to −1-1.

Shortest-path asymptotics provide a complementary comparison. For the loop-allowing model at δ=0\delta= 0, the diameter is asymptotic to log⁡n/log⁡log⁡n\log n / \log\log n [7]. In the sequential model with δ>0\delta> 0, typical distances are logarithmic, with leading constant determined by the growth rate of the local limit [20]. For every δ≥0\delta\ge0, the mixing time in Theorem 1.1 is logarithmic, with leading constant determined by the walk speed and harmonic-measure entropy.

Proof ideas

We follow the harmonic-measure approach of [5], beginning with quantitative estimates on the limiting tree. For fixed m≥2m \ge2 and δ≥0\delta\ge0, let XX be simple random walk on the Pólya-point tree T\mathcal{T} with uniform root age, started at its root ρ\rho. Write ∣Xt∣|X_t| for its distance from the root at time tt, and let ξ=(ρ,ξ1,…)\xi= (\rho,\xi_1,\ldots) be its limiting ray. For v∈Tv \in\mathcal{T}, define its harmonic information by

W(v):=−log⁡PρT(v∈ξ),Wk:=W(ξk).W(v) := -\log\mathbb{P}^{\mathcal{T}}_\rho(v \in\xi), \qquad W_k := W(\xi_k).

where PρT\mathbb{P}^{\mathcal{T}}_\rho denotes the walk law conditional on T\mathcal{T}. Thus e−Wke^{-W_k} is the harmonic mass of rays sharing the first kk edges of ξ\xi. Theorems 3.8 and 3.13 give

max⁡0≤s≤t∣∣Xs∣−νs∣=OP(t),Wk−dk=OP(k)\max_{0 \le s \le t} \left| |X_s| - \nu s \right| = O_{\mathbb{P}}(\sqrt{t}), \qquad W_k - dk = O_{\mathbb{P}}(\sqrt{k})

under the joint law of the tree and the walk. Consequently, W∣Xt∣=ν dt+OP(t)W_{|X_t|}=\nu\,\mathrm{d}t+O_{\mathrm{P}}(\sqrt{t}), providing the fluctuation scale used in the mixing argument.

To handle the dependence on age, we construct a regeneration structure with a fixed law for the age and type of the new root. This yields the distance estimate. Harmonic weights still depend on the tree beyond the next regeneration point. Approximating escape probabilities at finite depth controls this dependence and gives the covariance bounds needed for the entropy estimate.

To transfer estimates from the Pólya–Point Tree to GnG_n we need to construct a coupling between the graphs. We do not attempt to couple the entire ball of radius 1dlog⁡n\frac{1}{d}\log n in GnG_n with the Pólya–Point Tree as the number of vertices in the tree would be much larger than nn. Instead, we couple a truncated portion of the tree of depth 1−o(1)dlog⁡n\frac{1-o(1)}{d}\log n that with high probability supports almost all of the harmonic measure. We truncate the tree at points where it encounters either high degree vertices, very old vertices or along rays whose probability is too low. We show that few enough vertices are revealed along the way so that the Pólya urn representation of [6] continues to accurately describe the subsequent attachment probabilities.

Establishing the mixing bound from a typical starting point then follows from two consequences of the coupling. For the lower bound, a walk from a uniformly chosen vertex is localized on a set of o(n)o(n) vertices with total degree o(n)o(n), which has a vanishing stationary mass. For the upper bound, we show that, near the cutoff time, the law of the walk is arbitrarily close in total variation to a probability measure with density relative to πn\pi_n at most exp⁡{O(log⁡n)}\exp\{O(\sqrt{\log n})\}. The final step uses the uniform absolute spectral gap of Proposition 2.6 which says that for each fixed m≥2m\ge2, there is c=c(m)>0c=c(m)>0 such that the spectral gap is at least c(m)c(m). Then, because of the spectral gap, after a further O(log⁡n)O(\sqrt{\log n}) steps, the L2L^2 distance from stationarity will be o(1)o(1) which completes the proof.

Proving the result for arbitrary starting vertices requires a separate argument. In [3], they extended the method of [5] from typical starting points to prove cutoff in a configuration model with minimum degree 3 and degree distribution with exponential tails. They showed that after O(log⁡log⁡n)O(\log\log n) steps, the walk is spread out enough so that with high probability it is at a vertex that serves as a typical starting point. In our setting, we allow a burn-in time of O((log⁡log⁡n)2)O((\log\log n)^2), treating visits to high-degree vertices separately to control the amount of the graph revealed. This additional time is negligible compared with the log⁡n\sqrt{\log n} cutoff window.

When the walk hits a high degree vertex (greater than log⁡Cn\log^C n) in the burn-in phase, it makes with high probability a bounded expected number of excursions before escaping down one of its subtrees. Since the degree could be as large as n\sqrt{n}, revealing all these subtrees would reveal too many vertices. Instead, we sample ⌈(log⁡n)2⌉\lceil(\log n)^2\rceil incident slots and show that with probability 1−o(n−1)1-o(n^{-1}), almost all subtrees will be typical and give the estimates we need. Hence, with high probability it will escape down a typical subtree and we can apply the argument for mixing from a typical starting point.

Several questions remain. The lower bound from a uniformly chosen vertex does not determine whether individual hubs mix earlier: their many possible initial departures may accelerate initial mixing. The optimal window and any limiting cutoff profile also remain to be determined. The regime −m<δ<0-m<\delta<0, corresponding to degree exponent between two and three, is outside our scope. In particular, the regularity estimates in Lemma 2.5 are proved only for δ≥0\delta\ge0.

§ 2 gives the model, urn estimates and spectral bound. § 3 develops the tree-walk estimates, and § 4 constructs the comparison with the finite graph. § 5 treats arbitrary starting vertices. § 6 proves the lower bound and combines the estimates to establish Theorem 1.1.

Preferential Attachment and the Pólya–Point Tree

The finite preferential attachment graph

Preferential attachment is a growth rule in which vertices with larger current degree are more likely to receive new edges.

Definition 2.1 (Sequential preferential attachment). Fix m≥2m\ge2 and δ≥0\delta\ge0.

The graph G2G_2 consists of vertices 1,21,2 joined by mm parallel edges. For each k≥3k \ge3, form GkG_k from Gk−1G_{k-1} by adding vertex kk and then adding mm edges from kk to older vertices, one at a time. For i=1,…,mi=1,\ldots,m, let Fk,i−1\mathcal{F}_{k,i-1} be the history just before the ii-th edge is added, and let dk,i−1(v)d_{k,i-1}(v) be the degree of v<kv<k at that time. The older endpoint Jk,iJ_{k,i} is chosen according to

P(Jk,i=v∣Fk,i−1)=dk,i−1(v)+δ2m(k−2)+δ(k−1)+(i−1),v<k.(2)\mathbb{P}(J_{k,i}=v\mid\mathcal{F}_{k,i-1})=\frac{d_{k,i-1}(v)+\delta}{2m(k-2)+\delta(k-1)+(i-1)},\qquad v<k. \tag*{(2)}

Endpoints chosen by different edges may coincide, so GnG_n is an undirected loopless multigraph. Degrees count edge multiplicity, and simple random walk chooses an incident edge uniformly.

Set α:=δ/(2m+δ)∈[0,1)\alpha:=\delta/(2m+\delta)\in[0,1) and u:=α/(1−α)=δ/(2m)u:=\alpha/(1-\alpha)=\delta/(2m). Thus α=0\alpha=0 is pure degree-proportional attachment, whereas the older endpoint tends to the uniform law as α↑1\alpha\uparrow1. The affine attractiveness is 2mu2mu. We also use the derived parameters

References

  1. [1]Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286(5439):509–512, 1999.
  2. [2]Frank Bauer and Jürgen Jost. Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplace operator. Communications in Analysis and Geometry, 21(4):787–845, 2013.
  3. [3]Anna Ben-Hamou, Eyal Lubetzky, and Yuval Peres. Comparing mixing times on sparse random graphs. Annales de l’Institut Henri Poincaré Probabilités et Statistiques, 55(2):1116–1130, 2019.
  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]Nathanael Berestycki, Eyal Lubetzky, Yuval Peres, and Allan Sly. Random walks on the random graph. The Annals of Probability, 46(1):456–490, 2018.
  6. [6]Noam Berger, Christian Borgs, Jennifer T. Chayes, and Amin Saberi. Asymptotic behavior and distributional limits of preferential attachment graphs. The Annals of Probability, 42(1):1–40, 2014.
  7. [7]Béla Bollobás and Oliver Riordan. The diameter of a scale-free random graph. Combinatorica, 24(1):5–34, 2004.
  8. [8]Béla Bollobás, Oliver Riordan, Joel Spencer, and Gábor Tusnády. The degree sequence of a scale-free random graph process. Random Structures & Algorithms, 18(3):279–290, 2001.
  9. [9]Charles Bordenave, Pietro Caputo, and Justin Salez. Random walk on sparse random digraphs. Probability Theory and Related Fields, 170(3-4):933–960, 2018.arxiv.org/abs/1508.06600
  10. [10]Charles Bordenave, Pietro Caputo, and Justin Salez. Cutoff at the “entropic time” for sparse Markov chains. Probability Theory and Related Fields, 173(1-2):261–292, 2019.arxiv.org/abs/1611.01079
  11. [11]Xing Shi Cai, Pietro Caputo, Guillem Perarnau, and Matteo Quattropani. Rankings in directed configuration models with heavy tailed in-degrees. The Annals of Applied Probability, 33(6B):5613–5667, 2023.arxiv.org/abs/2104.08389
  12. [12]Fan R. K. Chung. Spectral Graph Theory, volume 92 of CBMS Regional Conference Series in Mathematics. American Mathematical Society, Providence, RI, 1997.
  13. [13]Colin Cooper and Alan Frieze. The cover time of the preferential attachment graph. Journal of Combinatorial Theory, Series B, 97(2):269–290, 2007.DOI
  14. [15]Rajat Subhra Hazra, Remco van der Hofstad, and Rounak Ray. Percolation on preferential attachment models. arXiv preprint arXiv:2312.14085, 2023.arxiv.org/abs/2312.14085
  15. [16]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
  16. [17]Eyal Lubetzky and Allan Sly. Cutoff phenomena for random walks on random regular graphs. Duke Mathematical Journal, 153(3):475–510, 2010.DOI
  17. [18]Russell Lyons, Robin Pemantle, and Yuval Peres. Ergodic theory on Galton–Watson trees: Speed of random walk and dimension of harmonic measure. Ergodic Theory and Dynamical Systems, 15(3):593–619, 1995.DOI
  18. [19]Milena Mihail, Christos Papadimitriou, and Amin Saberi. On certain connectivity properties of the internet topology. Journal of Computer and System Sciences, 72(2):239–251, 2006.
  19. [20]Remco van der Hofstad and Haodong Zhu. Logarithmic typical distances in preferential attachment models. The Annals of Applied Probability, 2025. To appear; arXiv:2502.07961.arxiv.org/abs/2502.07961

Paper details

vlnc:W_2zeg9kby
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

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

  • Mathematics

generative AI tools

View statement
Looking for related papers…
Contents