Pith. sign in

REVIEW 2 major objections 3 minor 40 references

Logarithmic typical distances in preferential attachment models

T0 review · 2 major / 3 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Typical distances in preferential attachment models equal $\log_\nu n$ to first order, with $\nu$ an explicit spectral-radius constant; the paper proves this sharp law in the $\delta>0$ regime.

desk verdict The proof is substantial and likely fixable, but the constant ν in Theorem 1.1 disagrees with the spectral-radius identity used in Section 4.2 by a factor of two on the square-root term. read the letter →

arxiv 2502.07961 v2 pith:FNAIDXH2 submitted 2025-02-11 math.PR

Remco van der Hofstad , Haodong Zhu This is my paper · ORCID
classification math.PR MSC 05C8060J80
keywords preferentialattachmenttypicaldistancelogarithmicgrowthspectralradiusPólyaurnsecond-momentmethodlocalweakconvergencesmall-worldnetworks
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Preferential attachment models in which each new vertex sends $m\ge 2$ edges, with positive fitness parameter $\delta$, are small-world networks: the distance between two uniformly chosen vertices grows like a constant times $\log n$. This paper identifies the constant exactly. It proves that the graph distance between two uniformly chosen vertices $o_1$ and $o_2$, divided by $\log_\nu n$, converges in probability to 1, where $\nu = \frac{2m(m+\delta)+\sqrt{m(m-1)(m+\delta)(m+1+\delta)}}{\delta}$. Consequently, for every $\varepsilon>0$ and with probability tending to 1, the distance lies between $(1-\varepsilon)\log_\nu n$ and $(1+\varepsilon)\log_\nu n$. The theorem confirms that typical distances are governed precisely by the exponential growth rate of the local limit's neighborhoods, namely by the spectral radius of the offspring operator.

What carries the argument

The offspring operator $T_\kappa$ is the integral operator on $L^2([0,1]\times\{O,Y\})$ with kernel $\kappa((x,s),(y,t))$ given by constants times $(x\vee y)^{-\chi}(x\wedge y)^{-(1-\chi)}$ when the direction of the edge matches the labels $s,t$, where $\chi=(m+\delta)/(2m+\delta)$. Its iterates count expected numbers of descendants in the Pólya point tree, and its spectral radius is $\nu$. The proof's workhorse is a truncated kernel $\kappa^\circ_\zeta$ supported on ages in $[3\zeta,1-\zeta]$; Proposition 4.1 shows the inner products $\langle 1, T_{\kappa^\circ_\zeta}^k 1\rangle$ grow like $(\nu-o(1))^k$ for small $\zeta$, via an isometry that turns the inner product into a random-walk probability and a martingale and optional-stopping argument. This transfer from the non-self-adjoint operator to a random walk is what makes the sharp constant accessible.

What would settle it

Numerically compute the spectral radius of the age-truncated offspring operator $T_{\kappa^\circ_\zeta}$ for $m=2$, $\delta=1$ as $\zeta\downarrow 0$. The paper predicts convergence to $\nu=12+2\sqrt{6}\approx 16.899$. A limiting value different from this, or a large-$n$ simulation of $PA^{(2,1)}_n$ whose median distance is not within $o(1)$ of $\log_{16.899} n$, would refute the claimed constant.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1.1: for every $m\ge 2$ and $\delta>0$, if $o_1$ and $o_2$ are independent uniform vertices of $PA_n^{(m,\delta)}(d)$, then $\mathrm{dist}(o_1,o_2)/\log_\nu n\to 1$ in probability. The lower bound forbids paths of length at most $(1-\varepsilon)\log_\nu n$ through a first-moment sum over all such paths; the upper bound shows that, with high probability, there is a path of length at most $(1+\varepsilon)\log_\nu n$ connecting the two uniformly chosen vertices, obtained by a conditional second-moment estimate on the number of $k_\nu^\star$-step paths between the boundaries of the two $r$-neighborhoods. Every path probability is written as a product over edges, then transformed into products and inner products of the integral kernel $\kappa$ of the offspring operator. The sharp constant $\nu$ is the spectral radius of that operator, and the proof is completed by showing that age-truncated versions of the operator have spectral radii converging to $\nu$.

Load-bearing premise

The exact value of $\nu$ is imported from a separate theorem about the spectral radius of the offspring operator; if that value were wrong, the logarithmic growth rate might still hold but the asymptotic constant claimed here would be off by a fixed factor.

Editorial extensions

If this is right

  • For every $\varepsilon>0$, the probability that two uniform vertices are joined by a path of length below $(1-\varepsilon)\log_\nu n$ tends to zero, so the spectral radius governs the lower cutoff for distances.
  • The probability that they fail to be joined by a path of length at most $(1+\varepsilon)\log_\nu n$ also tends to zero, so the typical distance is asymptotically deterministic: $\mathrm{dist}(o_1,o_2)\sim \log_\nu n$.
  • The same sharp constant applies to the model variants $PA_n^{(m,\delta)}(a)$, $(b)$ and $(c)$, which the paper transfers by the collapsing construction.
  • In the $\delta>0$ regime the exponent $\nu$ is finite and larger than 1, placing these models in the small-world class where neighborhoods expand like $\nu^k$ rather than the ultra-small class where distances grow like $\log\log n$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Inference: one natural extension, which the paper states as an open conjecture rather than a proved result, is that the diameter for $\delta>0$ is also $\log_\nu n + O(\log n)$; the proof here supplies the typical-distance engine but not the extremal control over the few slowly growing vertices.
  • Inference: the random-walk and martingale route to the truncated spectral radius is likely to be reusable in related models with random out-degree or additive fitness whose local limits have non-self-adjoint offspring operators; the corresponding sharp constant would again be a spectral radius.
  • Inference: because the proof truncates ages at a growing cutoff, a direct numerical check is available: for small truncations the finite-matrix spectral radii should already be close to $\nu$, offering a finite-$n$ test of the constant before full simulation.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The paper proves that in the preferential attachment model PA_n^{(m,δ)}(d) with out-degree m≥2 and fitness δ>0, the graph distance between two uniformly chosen vertices is asymptotically log_ν n in probability, where ν is an explicit constant depending on m and δ. The proof combines a Pólya urn representation with a path-counting technique: a first-moment argument gives the lower bound on typical distances, a conditional second-moment argument gives the upper bound, and a probabilistic, martingale-based proof establishes convergence of the spectral radius of a truncated offspring operator. The paper also extends the main theorem to variants PA_n^{(m,δ)}(a) and PA_n^{(m,δ)}(b) via a collapsing procedure.

Significance. If the result is correct, it resolves a conjecture of the first author and gives the sharp logarithmic order of typical distances in the δ>0 regime of preferential attachment, an open problem since the upper and lower bounds of Dommers–van der Hofstad–Hooghiemstra. The proof strategy is substantial: the path-counting framework is adapted to a model that is not independent, and the convergence of the spectral radius of the non-self-adjoint truncated offspring operator is handled by an isometry and martingale argument rather than by compact perturbation theory. The paper is also transparent about its dependence on the external spectral-radius computation in [24], and the main proof contains no fitted parameters. These strengths are, however, conditional on the internal consistency of the constant ν, which is the main point of concern in this report.

major comments (2)
  1. [Section 4.2, paragraph before Eq. (4.19)]
  2. [Appendix E.2, Eq. (E.9)]
minor comments (3)
  1. [Section 1.3, Eq. (1.2)]
  2. [Section 2.5, item 6]
  3. [Section 4.2, after Eq. (4.30)]

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the sharp constant is imported from an independent prior spectral-radius theorem, and the internal proof chain does not use the target result.

full rationale

The derivation chain is not circular. The lower bound in Proposition 2.5 is proved in Section 3 by first-moment path counting using the Pólya urn representation, reducing to the bound n times the k-th power of the operator norm of T_kappa, with the operator norm equal to the spectral radius imported from Proposition 2.13. That import is a theorem from [24] by Hazra, van der Hofstad and Ray computing the spectral radius of the offspring operator; it does not assume Theorem 1.1 and is therefore independent support rather than circular self-citation. The upper bound in Theorem 1.1 is built on Propositions 2.11 and 2.12, whose proofs use the truncated spectral-radius convergence of Section 4 and path-counting comparisons; none of these arguments invokes Theorem 1.1 as an input. Lemma 2.9 is proved in Appendix A using Proposition 2.5, but Proposition 2.5 is established independently in Section 3 without relying on Lemma 2.9, so there is no cyclic dependence between the lower and upper bounds. The other self-citations, such as [23] for local convergence and [26] for prior path bounds, are parameter-free prior theorems with stated assumptions that do not include the typical-distance result being proved. I note, without treating it as circularity, an internal algebraic inconsistency: the rewrite in Section 4.2, nu = 2/(2chi-1)(c_OO + sqrt(c_OY c_YO)), evaluates to [2m(m+delta) + 2 sqrt(m(m-1)(m+delta)(m+1+delta))]/delta, which differs from the stated formula (1.2), where the square-root term is not doubled unless m=1. This is a correctness issue in how the imported spectral-radius result is used, not an equivalence-by-construction of inputs and conclusions.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central claim has no fitted free parameters. Model inputs m and δ are fixed; truncation parameters b, ζ, η, M, r and constants Θ and cζ are analytical devices with controlled limits, not fitted numbers. The paper relies on external prior results for the Pólya urn representation, local convergence, and the spectral radius formula for Tκ. These are cited theorems rather than circular assumptions. No new physical or probabilistic entity is postulated; the modified kernel ^kappa in (5.16) and the truncated operator T_{κ◦_ζ} are technical tools, not invented entities.

assumptions (6)
  • domain assumption The Pólya urn graph PUn with independent beta weights ψj and parameters α = m + δ, β_j = (2j−3)m + δ(j−1) has the same distribution as PA^{(m,δ)}_n(d).
    Invoked at the start of Section 2.1 via [26, Theorem 5.10]. All path probability computations in Sections 3 through 6 use this representation, so a failure of this equivalence would invalidate the estimates.
  • domain assumption Marked local weak convergence of (PAn, o) to the Pólya point tree PPT^{(m,δ)} holds, including convergence in probability for neighborhoods of two uniform vertices.
    Used in Appendix A to prove Lemma 2.9, which shows that good neighborhood pairs and good weights have probability close to 1. The result is cited from [23, Theorem 1.5] and equation (A.1).
  • domain assumption The spectral radius and operator norm of the integral operator Tκ on L2([0,1]×{O,Y}) are both equal to ν = [2m(m+δ)+sqrt(m(m−1)(m+δ)(m+1+δ))]/δ.
    Proposition 2.13 imports [24, Theorem 2.5 and Remark 5.1]. The constant ν appears in Theorem 1.1 and in every first- and second-moment threshold in the proof.
  • standard math Beta moments satisfy E[ψ^p(1−ψ)^q] = (α+p−1)_p (β+q−1)_q / (α+β+p+q−1)_{p+q}.
    Equation (3.3), cited from [26, Lemma 5.14], is used repeatedly to evaluate path probabilities after integrating out the beta weights.
  • standard math The optional stopping theorem and the finiteness of the stopping times ξi and γi for the martingale Mℓ hold.
    Section 4.2 uses [19, Theorem 4.3.1] and [32, Theorem 3.22] to lower bound the probability that the martingale stays inside an interval for k steps.
  • standard math For the non-self-adjoint Hille-Tamarkin operator T^2_{κ◦_ζ}, there exists a strictly positive eigenfunction uζ with eigenvalue r(T^2_{κ◦_ζ}).
    Appendix B uses [40, Theorem 43.8] to prove convergence of the truncated spectral radius to ν.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Logarithmic typical distances in preferential attachment models." pith.science (2026). https://pith.science/paper/FNAIDXH2

@misc{pith2026250207961,
  author       = {Pith},
  title        = {Pith review of: Logarithmic typical distances in preferential attachment models},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FNAIDXH2}},
  note         = {Machine review of arXiv:2502.07961}
}
abstract

We prove that the typical distances in a preferential attachment model with out-degree $m\geq 2$ and strictly positive fitness parameter are close to $\log_\nu{n}$, where $\nu$ is the exponential growth parameter of the local limit of the preferential attachment model. The proof relies on a path-counting technique, the first- and second-moment methods, as well as a novel proof of the convergence of the spectral radius of the offspring operator under a certain truncation.

Figures

Figures reproduced from arXiv: 2502.07961 by the authors.

Figure 1
Figure 1. A sample of the path decomposition with decomposition size [PITH_FULL_IMAGE:figures/full_fig_p048_1.png] view at source ↗
Figure 2
Figure 2. Two cases for the path decomposition of ⃗ρ e arise when decomposition size u = 1 and ρ(1)0 ∈ ⃗π, where this categorization depends on whether ρ(1)ℓ is in ⃗π. The case where ρ(1)0 ̸∈ ⃗π and ρ(1)ℓ ∈ ⃗π is simply the reverse of the first graph. ▷ if ℓ = k − j, which corresponds to the first plot in [PITH_FULL_IMAGE:figures/full_fig_p053_2.png] view at source ↗
Figure 3
Figure 3. A sample of the decomposition Each path ⃗π ∈ Pk a1,a2 can be decomposed into a self-avoiding path and several self-loops (see [PITH_FULL_IMAGE:figures/full_fig_p066_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 38 canonical work pages

  1. [24]

    S., VAN DER HOFSTAD , R

    H AZRA , R. S., VAN DER HOFSTAD , R. and RAY, R. (2023). Percolation on preferential attachment models. arXiv:2312.14085 [math.PR]

    arXiv 2023

  2. [17]

    and H OOGHIEMSTRA , G

    D OMMERS , S., VAN DER HOFSTAD , R. and H OOGHIEMSTRA , G. (2010). Diameters in preferential attach- ment models. J. Stat. Phys. 139 72–107. MR2602984

    work page 2010

  3. [26]

    VAN DER HOFSTAD , R. (2024). Random graphs and complex networks. Volume 2 . Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press

    work page 2024

  4. [1]

    A DAMIC , L. A. and H UBERMAN , B. A. (2000). Power-Law Distribution of the World Wide Web. Science 287 2115-2115

    work page 2000

  5. [2]

    and S TEELE , J

    A LDOUS , D. and S TEELE , J. M. (2004). The objective method: probabilistic combinatorial optimization and local weak convergence. InProbability on discrete structures. Encyclopaedia Math. Sci. 110 1–72. Springer. MR2023650

    work page 2004

  6. [3]

    and S CHRAMM , O

    B ENJAMINI , I. and S CHRAMM , O. (2001). Recurrence of distributional limits of finite planar graphs. Elec- tron. J. Probab.6 no. 23, 13. MR1873300

    work page 2001

  7. [4]

    and S ABERI , A

    B ERGER , N., B ORGS , C., C HAYES , J. and S ABERI , A. (2014). Asymptotic behavior and distributional limits of preferential attachment graphs. Ann. Probab. 42 1–40. MR3161480

    work page 2014

  8. [5]

    B ERGER , N., B ORGS , C., C HAYES , J. T. and S ABERI , A. (2005). On the spread of viruses on the inter- net. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms 301–310. ACM, New York. MR2298278

    work page 2005

Show all 40 references
  1. [6]

    and R IORDAN , O

    B OLLOBÁS , B., J ANSON , S. and R IORDAN , O. (2007). The phase transition in inhomogeneous random graphs. Random Structures Algorithms 31 3–122. MR2337396

    2007

  2. [7]

    and R IORDAN , O

    B OLLOBÁS , B. and R IORDAN , O. (2004). The diameter of a scale-free random graph. Combinatorica 24 5–34. MR2057681

    2004

  3. [8]

    and VAN DER HOFSTAD , R

    C ARAVENNA , F., GARAVAGLIA , A. and VAN DER HOFSTAD , R. (2019). Diameter in ultra-small scale-free random graphs. Random Structures Algorithms 54 444–498. MR3938775

    2019

  4. [9]

    and L U, L

    C HUNG , F. and L U, L. (2003). The average distance in a random graph with given expected degrees. Internet Math. 1 91–113. MR2076728

    2003

  5. [10]

    C SÁRDI , G. (2006). Dynamics of citation networks. In Artificial Neural Networks – ICANN 2006. Lecture Notes in Computer Science 4131 698–709. Springer

    2006

  6. [11]

    F., Å KE SVENSSON and LILJEROS , F

    DE BLASIO , B. F., Å KE SVENSSON and LILJEROS , F. (2007). Preferential attachment in sexual networks. Proceedings of the National Academy of Sciences 104 10762-10767

    2007

  7. [12]

    and H OOGHIEMSTRA , G

    D EIJFEN , M., VAN DEN ESKER , H., VAN DER HOFSTAD , R. and H OOGHIEMSTRA , G. (2009). A prefer- ential attachment model with random initial degrees. Ark. Mat. 47 41–72. MR2480915

    2009

  8. [13]

    and MÖRTERS , P

    D EREICH , S., M ÖNCH , C. and MÖRTERS , P. (2012). Typical distances in ultrasmall random networks.Adv. Appl. Probab. 44 583–601. MR2977409

    2012

  9. [14]

    and M ÖRTERS , P

    D EREICH , S. and M ÖRTERS , P. (2009). Random networks with sublinear preferential attachment: degree evolutions. Electron. J. Probab.14 no. 43, 1222–1267. MR2511283

    2009

  10. [15]

    and M ÖRTERS , P

    D EREICH , S. and M ÖRTERS , P. (2011). Random networks with concave preferential attachment rule. Jahresber. Dtsch. Math.-Ver.113 21–40. MR2760002

    2011

  11. [16]

    and M ÖRTERS , P

    D EREICH , S. and M ÖRTERS , P. (2013). Random networks with sublinear preferential attachment: the giant component. Ann. Probab. 41 329–384. MR3059201

    2013

  12. [18]

    D UDLEY , R. M. (2002). Real analysis and probability . Cambridge Studies in Advanced Mathematics 74. Cambridge University Press, Cambridge Revised reprint of the 1989 original. MR1932358 72

    2002

  13. [19]

    D URRETT , R. (2019). Probability: theory and examples 49. Cambridge university press

    2019

  14. [20]

    and H OOGHIEMSTRA , G

    VAN DER ESKER , H., VAN DER HOFSTAD , R. and H OOGHIEMSTRA , G. (2008). Universality for the dis- tance in finite variance random graphs. J. Statist. Phys. 133 169–202. MR2438903

    2008

  15. [21]

    and R AMACHANDRAN , V

    F ERNHOLZ , D. and R AMACHANDRAN , V. (2007). The diameter of sparse random graphs. Random Struc- tures Algorithms 31 482–516. MR2362640

    2007

  16. [22]

    and VAN DER VAART, A

    G AO, F. and VAN DER VAART, A. (2017). On the asymptotic normality of estimating the affine preferential attachment network models with random initial degrees. Stochastic Process. Appl. 127 3754–3775. MR3707244

    2017

  17. [23]

    and R AY, R

    G ARAVAGLIA , A., H AZRA , R., VAN DER HOFSTAD , R. and R AY, R. (2022). Universality of the local limit in preferential attachment models. arXiv:2212.05551 [math.PR]

    2022

  18. [25]

    Corrigenda Random Graphs and Complex Networks

    VAN DER HOFSTAD , R. Corrigenda Random Graphs and Complex Networks. V olume Two. https://rhofstad. win.tue.nl/CorrigendaNotesRGCNII.pdf

  19. [27]

    and VAN MIEGHEM , P

    VAN DER HOFSTAD , R., H OOGHIEMSTRA , G. and VAN MIEGHEM , P. (2005). Distances in random graphs with finite variance degrees. Random Structures Algorithms 27 76–123. MR2150017

    2005

  20. [28]

    and Z NAMENSKI , D

    VAN DER HOFSTAD , R., H OOGHIEMSTRA , G. and Z NAMENSKI , D. (2007). Distances in random graphs with finite mean and infinite variance degrees. Electron. J. Probab. 12 703–766 (electronic). MR2318408

    2007

  21. [29]

    J ONES , J. H. and H ANDCOCK , M. S. (2003). An assessment of preferential attachment as a mechanism for human sexual network formation. Proc. Royal Soc. B: Biol. Sciences 270 1123–1128

    2003

  22. [30]

    J ONES , J. H. and H ANDCOCK , M. S. (2003). Sexual contacts and epidemic thresholds. Nature 423 605— 606

    2003

  23. [31]

    J ORDAN , J. (2018). Preferential attachment graphs with co-existing types of different fitnesses. J. Appl. Probab. 55 1211–1227. MR3899937

    2018

  24. [32]

    and S HREVE , S

    K ARATZAS , I. and S HREVE , S. E. (1991). Brownian motion and stochastic calculus, second ed. Graduate Texts in Mathematics 113. Springer-Verlag, New York. MR1121940

    1991

  25. [33]

    and M OSER , C

    K UNEGIS , J., B LATTNER , M. and M OSER , C. (2013). Preferential attachment in online networks: mea- surement and explanations. In Proceedings of the 5th Annual ACM Web Science Conference. WebSci ’13 205–214. Association for Computing Machinery, New York, NY , USA

    2013

  26. [34]

    L O, T. Y. Y. (2021). Weak local limit of preferential attachment random trees with additive fitness. arXiv:2103.00900 [math.PR]

    2021 arXiv

  27. [35]

    and O RTGIESE , M

    L ODEWIJKS , B. and O RTGIESE , M. (2020). A phase transition for preferential attachment models with additive fitness. Electron. J. Probab.25 Paper No. 146, 54. MR4193887

    2020

  28. [36]

    N EWMAN , M. (2018). Networks. Oxford University Press

    2018

  29. [37]

    P ITTEL , B. (1994). Note on the heights of random recursive trees and random m-ary search trees. Random Structures Algorithms 5 337–347. MR1262983

    1994

  30. [38]

    and Y U, D

    W ANG , M., Y U, G. and Y U, D. (2008). Measuring the preferential attachment mechanism in citation networks. Physica A: Statist. Mech. Appli. 387 4692 - 4698

    2008

  31. [39]

    W ATTS, D. J. (2003). Six degrees. The science of a connected age. W. W. Norton & Co. MR2041642

    2003

  32. [40]

    Z AANEN , A. (1997). Introduction to operator theory in Riesz spaces. Springer-Verlag, Berlin. MR1631533

    1997

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.