Pith.

Probability · arXiv:2412.13975 v1 · submitted 18 Dec 2024 · 23 references

The number of descendants in a preferential attachment graph

Svante Janson, Tiffany Y. Y. Lo

The paper says

“We study the number X(n) of vertices that can be reached from the last added vertex n via a directed path (the descendants) in the standard preferential attachment graph.”

more of the abstract

In this model, vertices are sequentially added, each born with outdegree m ≥ 2; the endpoint of each outgoing edge is chosen among previously added vertices with probability proportional to the current degree of the vertex plus some number ρ. We show that X(n)/nν converges in distribution as n → ∞, where ν depends on both m and ρ, and the limiting distribution is given by a product of a constant factor and the (1−ν)-th power of a Gamma(m/(m-1),1) variable. The proof uses a Pólya urn representation of preferential attachment graphs, and the arguments of Janson (2024) where the same problem was studied in uniform attachment graphs. Further results, including convergence of all moments and analogues for the version with possible self-loops are provided.

from the abstract

Pith says

Machine review · deepseek-v4-flash · 11 Aug 2026 · what was read was not recorded · not checked by a person

It can be wrong. Challenge this review or reply to it.

Holds up, with conditions. Genuine new result on descendant counts in preferential attachment, carefully proved with one load-bearing but likely fixable gap: the Pólya urn representation for ρ<0. This line is wrong

2 major objections · 4 minor

How often objections from reviews like this one are right: not yet measured

Are you an author? What you can do.

Not checked: figures, code, what the 23 references say.

The paper says, at Section 2, before Definition 2.1, and Theorem 2.4

The review did not quote this passage.

Pith says: Objection 1 of 2 · major

The representation PA(n,m,ρ) = PU(n,m,ρ) is stated for every real ρ > -m and cited to [3, Theorem 2.1], but the paper itself notes in Section 1 that [3] assumes ρ ≥ 0 in the present notation; the justification offered in Section 2 is only the sentence that the model and theorem are 'easy variations' of [3, Section 2.2].

more of objection 1

No proof of the finite-dimensional equality for ρ ∈ (-m,0) is given or cited. This is load-bearing: Lemmas 3.1, 3.4 and 3.7, the reverse-supermartingale/Martingale decompositions in Sections 4 and 10, the Yule coupling, and the ODE identification in Section 8 all operate inside the PU representation, so Theorem 1.2 is not established for negative ρ unless the equality holds there. I checked that the urn parameters a = m+ρ and b = (2i-3)m+(i-1)ρ are indeed positive for all i ≥ 2 when ρ > -m, so the extension is very plausible; nevertheless, the authors should either include the short exchangeability/induction argument establishing PA(n,m,ρ) = PU(n,m,ρ) for the full range, or cite a source that covers ρ > -m.

The paper says, at Section 12, Theorem 12.2

The review did not quote this passage.

Pith says: Objection 2 of 2 · major

Theorem 12.2 promises Theorems 1.2 and 1.3 for the self-loop model in full generality (m ≥ 2, ρ > -m), but the proof is explicitly a sketch: after deriving the new moment bounds (12.3)–(12.7), the text states that it concentrates on the m=2, ρ=0 case and leaves the general case (with modifications as in Section 10) to the reader, and …

more of objection 2

… several steps — the injectivity of the coupling map Ψ, the tightness bound (12.24), and the ODE step — are only indicated. This is not load-bearing for the main theorem, but as written it is a theorem whose stated generality is not supported by the proof; either write out the general case or narrow the statement to the scope actually proved.

4 minor objections

The paper says, at Remark 3.2, Eq. (3.12)

Pith says: minor objection 1 of 4

The display reads 2Γ(3/2) = 4√π, but Γ(3/2) = √π/2, so 2Γ(3/2) = √π; the intended identity is presumably 2/Γ(3/2) = 4/√π, which is the value used in the subsequent asymptotics of EΦ_k. Please correct.

The paper says, at Section 10.2, after the statement of the Yule-process analogue

Pith says: minor objection 2 of 4

The definition 'δn = 3 log^m n / n1^{1/3}' is ambiguous about the exponent of log n; in the m=2 case it is (log n)^2, and the general argument only needs some fixed power of log n. Please state the precise exponent used.

show 2 more

The paper says, at Section 11, Eq. (11.13)

Pith says: minor objection 3 of 4

The estimate E|ζ - Eζ|^p ≤ C_p((Nq)^{p/2} + Nq) for ζ ~ Bin(N,q) is used without reference; a citation (for example to Burkholder's inequality [7] or a standard textbook) or a one-line proof would be helpful.

The paper says, at Section 10.5, Eq. (10.50)

Pith says: minor objection 4 of 4

The chain 'b − a = (m+ρ)/(m+ρ+1) + 1/α = (m+ρ)/(m(m+ρ+1)) + 1' is correct only after substituting 1/α = 1−ν and the definition of ν; a short gloss would help the reader verify the bookkeeping.

What would settle it

Re-derive the negative-ρ extension by checking the one-step transition identity: for any finite history of the graph up to a given edge, compare the PA probability that the next edge hits a fixed old vertex i with the probability obtained from the PU construction integrated over B_i; this should coincide with the Pólya-urn transition with initial parameters (a,b)=(m+ρ,(2i-3)m+(i-1)ρ). If the identity holds for every finite history, Theorem 2.4 is valid for negative ρ; if any step uses ρ≥0 in an essential way, the representation fails. A useful small case is m=2, ρ=-1, n=4: enumerate all ordered edge outcomes under PA and PU and check exact agreement.

from the skeptic's reading

How the review went

4 readings by deepseek-v4-flash · 11 Aug 2026

  1. Reader holds up, with conditions confidence moderate
  2. Skeptic agrees 3 min 13 s · 47,594 tokens read, 21,513 written
  3. Editor wrote the verdict above 26 s · 48,348 tokens read, 2,954 written
  4. Referee major revision: 2 major objections, 4 minor 4 min 43 s · 47,807 tokens read, 36,957 written

Not run on this paper: the simulated authors' defence.

Pith did not check this review's objections against the paper.

The review in full

The review in brief, machine-written

Here's my take on Janson–Lo. The main theorem is real: for the standard PA graph, the descendant count grows like nν with ν depending on m and ρ, and the limit distribution is a gamma power. This genuinely extends Janson's uniform attachment result; the exponent and constant are new and derived, not fitted. The proof is a serious piece of work: the martingale estimates, the Yule coupling, and the ODE limit are all coherent, and the moment convergence is handled properly. I believe the math is correct for ρ≥0, the case where the urn representation is cited from Berger–Borgs–Chayes–Saberi.

The soft spot is exactly what the stress-test flags. Theorem 2.4 asserts PA(m,ρ)=PU(m,ρ) for all ρ>−m, but the cited source proves the representation only for ρ≥0. The paper waves at this with 'easy variation' and nothing else. The urn parameters are positive for negative ρ, so the extension is very plausible, but it's not established. And every subsequent estimate—the beta moment bounds, the Sn,k concentration, the martingale decompositions—runs through PU. So the negative-ρ half of the main theorem rests on an unproved equivalence. A referee should ask for a proof or a correct citation; my guess is it will be supplied without too much pain.

Section 10 (general m,ρ) and Section 12 (self-loops) are sketches. That's acceptable for a paper of this type, but they do list the main modifications rather than proving every step. I'd want the Section 10 estimates (10.10)–(10.12) checked carefully, since they carry the general case.

The citation and attribution pattern is honest: they build on [13] and [3] and say so. No fitting, no circularity. The paper would be a good fit for a probability journal. I'd send it to a referee, and I'd make sure the referee checks the negative-ρ urn issue and the sketch sections. Verdict: accept after minor-to-moderate revision, assuming the urn gap is closed.

The strongest objection

The central theorem is proved entirely inside the Pólya-urn representation PU(n,m,ρ). Theorem 2.4 is quoted from [3] as holding for all ρ>-m, but the paper itself notes that [3] assumes ρ≥0; the only justification is the sentence before Definition 2.1 that the extension is an 'easy variation'. For ρ∈(-m,0), the urn parameters remain positive: a=m+ρ>0 and b=(2i-3)m+(i-1)ρ>0 for every i≥2, so the exchangeable-urn argument is very likely to go through. However, the actual finite-dimensional equality PA(n,m,ρ)=PU(n,m,ρ) is not proved or cited for negative ρ. Every subsequent estimate—the beta-variable moment bounds in Lemma 3.1, the Sn,k concentration lemma 3.4, the martingale decompositions in Sections 4 and 10, and the final ODE limit theorem—starts from the PU representation. Thus if the representation failed for some negative ρ, Theorem 1.2 would not be established for that ρ. This is a completeness/correctness risk rather than a detected contradiction, and it is exactly the load-bearing point.

The reader's weakest assumption identifies exactly the same load-bearing point: the Pólya-urn representation for ρ∈(-m,0) is asserted rather than proved. My independent reading confirms that this representation is the foundation of the proof; the theorems on descendant counts, moment convergence, and the self-loop analogue all flow from it. The extension is likely correct because the relevant beta parameters stay positive and the de Finetti/Pólya-urn mechanism is well defined for positive real initial ball counts. Nevertheless, the paper does not supply the finite-dimensional equivalence for negative ρ, and the self-loop discussion shows that negative ρ can create negative weights in variants, so positivity is not automatic. I did not find a concrete error in the beta-moment algebra, the martingale estimates, or the ODE solution in Appendix A; those parts appear coherent. The verdict should remain conditional on the missing or cited proof of the negative-ρ representation, so no change to the reader's verdict is needed.

The referee's report

If correct, the main theorem is a clean and nontrivial extension of the uniform-attachment result of Janson (2024): it identifies a ρ-dependent growth exponent ν and the full limit law of n^{-ν}X^(n). Three strengths deserve emphasis. (i) The derivation is parameter-free: the Γ-ratio constant and the power of ξ1 in (1.4) emerge from the urn parameters and the ODE (10.37) with the boundary condition ~B(∞) = ξ; there is no fitting or calibration. (ii) Sections 4–9 form a complete and careful proof for m=2, ρ=0, including the Yule-process coupling (Theorem 5.2) and the tightness arguments for the compensator and the descendant-count martingale; every lemma in this core part is proved in line. (iii) Moment convergence (Theorem 1.3) is obtained from explicit uniform moment bounds rather than abstract integrability arguments, and the self-loop variant (Theorem 12.2) is a useful bonus. The formula is a falsifiable quantitative prediction and reduces formally to the uniform case as ρ → ∞. The single load-bearing caveat is the status of Theorem 2.4 for negative ρ; because the urn parameters stay positive for all ρ > -m, the gap is very likely repairable, but it must be closed.

Pith's reading of the paper (a machine's summary, not the authors')

The paper asks how many vertices can be reached from the last-added vertex n by following directed edges in the standard preferential attachment graph, where each new vertex attaches m edges with probability proportional to degree plus ρ. It proves that this descendant count, normalized by n^ν with ν=(m−1)(m+ρ)/(m(m+ρ+1)), converges in distribution to a constant times the (1−ν)-th power of a Gamma(m/(m−1),1) variable. The exponent ν is strictly between 0 and 1 and shrinks as ρ becomes more negative, so the growth is a genuine power law with a parameter-dependent exponent. The result also gives convergence of all moments, and the same limit law holds for the variant with self-loops, so the qualitative behavior is the same across model details.

What carries the argument. The central object is the Pólya urn representation of preferential attachment: the weight of a vertex, degree plus ρ, evolves like the number of red balls in a classical Pólya urn, encoded by independent Beta(m+ρ,(2j−3)m+(j−1)ρ) variables B_j; conditional on these, each outgoing edge of vertex k lands at i with probability B_i ∏_{j=i+1}^{k−1}(1−B_j). This representation lets the authors build the descendant subgraph by a coin-tossing recursion, couple its early part to a time-changed Yule process, and reduce the limit to solving a first-order differential equation. The key algebraic identity is the martingale decomposition W_k=Φ_kY_k with Φ_k=∏_{j=1}^{k}(1+(m−1)B_j), which converts the descendant-count recursion into tractable moment estimates.

Core claim. Fix m≥2 and ρ>−m. The paper proves that $X^{{(n)}}$/n^ν converges in distribution, with ν=(m−1)(m+ρ)/(m(m+ρ+1)), to $$ \frac{\Gamma\!\left(\frac{(m-1)(m+\rho)}{m(m+\rho+1)}\right)\Gamma\!\left(\frac{m+\rho}{m(m+\rho+1)}+1\right)} {\Gamma\!\left(\frac{m+\rho}{m+\rho+1}\right)} \left(\frac{(m+\rho+1)(m-1)}{2m+\rho}\,\xi_1\right)^{1-\nu}, $$ where $\xi_1\sim \mathrm{Gamma}(m/(m-1),1)$. Thus the number of descendants of the last-added vertex grows like a power $n^\nu$ multiplied by a random factor that is itself a deterministic constant times the $(1-\nu)$-th power of a Gamma variable. The same argument yields convergence of all moments to explicit Gamma ratios, and the same limit for the self-loop version of the model.

The premise it rests on. The load-bearing premise is that the Beta-variable Pólya-urn construction in Theorem 2.4, which the cited literature establishes for ρ≥0, also gives exactly the preferential attachment distribution for every ρ∈(−m,0); the paper states this as an easy variation without supplying the proof.

If the paper is right (Pith's inferences, not the authors')

For m=2 and ρ=0, the limit simplifies to X(n)/n^{1/3} → 1.45833 ξ_1^{2/3}, and the asymptotic mean is 2.19416 n^{1/3}.

As ρ→∞, ν→(m−1)/m and the limit in (1.4) reduces to the uniform-attachment result, matching the heuristic that large ρ drowns out degree bias.

All positive moments converge: for every p>0, E[(X^{(n)}/n^ν)^p] tends to a closed Gamma ratio given in (1.5).

The self-loop variant of preferential attachment has the same descendant limit, so the result is not sensitive to whether loops are allowed.

For m=1 the picture changes: X(n)/log n converges in probability to (1+ρ)/(2+ρ), so the power-law behavior is special to m≥2.

Not in the paper: the same Pólya-urn recursion should yield the asymptotic size of the descendant subgraph's edge count and total degree, since these are linear functionals of the Y_k recursion.

Not in the paper: because ν→0 as ρ↓−m, the descendant count at fixed m should grow more slowly than any power near the boundary; the paper leaves this sub-polynomial regime open.

Not in the paper: the martingale bounds in Section 11 are strong enough to suggest a central limit theorem for the logarithm of X(n) about ν log n, with variance (1−ν)^2 Var(log ξ_1); no such CLT is stated.

Check this review

Pith stored no record of this review's passes and took no fingerprint of it. Reviews made by code from 13 Nov 2026 on carry both.

How often reviews like this one are right

Reviews like this one: written by deepseek-v4-flash, where what was read was not recorded.

How often objections from reviews like this one are right: not yet measured

Every value above, in the review's public record (JSON)

Reviews by people

This review was written by a machine. No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.

Request a human review

How Pith checks papers · The full audit of this paper

The paper

Abstract

We study the number X(n) of vertices that can be reached from the last added vertex n via a directed path (the descendants) in the standard preferential attachment graph. In this model, vertices are sequentially added, each born with outdegree m ≥ 2; the endpoint of each outgoing edge is chosen among previously added vertices with probability proportional to the current degree of the vertex plus some number ρ. We show that X(n)/nν converges in distribution as n → ∞, where ν depends on both m and ρ, and the limiting distribution is given by a product of a constant factor and the (1−ν)-th power of a Gamma(m/(m-1),1) variable. The proof uses a Pólya urn representation of preferential attachment graphs, and the arguments of Janson (2024) where the same problem was studied in uniform attachment graphs. Further results, including convergence of all moments and analogues for the version with possible self-loops are provided.

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.

abstract compiled · 2026-09-23

The authors' main claim, as the classifier picked it out 1.00

“We show that $X^{(n)}/n^\nu$ converges in distribution as $n\to\infty$, where $\nu$ depends on both $m$ and $\rho$, and the limiting distribution is given by a product of a constant factor and the $(1-\nu)$-th power of a Gamma(m/(m-1),1) variable.”

How the main claim is stated: asserted 1.00

What the abstract itself states, as probabilities: claims first 0.04 · states limitation 0.07 · human participants 0.01 · controlled comparison 0.03 · randomized assignment 0.01 · states quantitative result 0.94 · compares with prior results 0.65 · mentions code or data availability 0.02

The abstract, sentence by sentence

This table labels the abstract only (arXiv listing abstract v1). The number is the probability the classifier gave the label.

SentenceRoleThe authors' own workStates the main conclusionStrength
We study the number $X^{(n)}$ of vertices that can be reached from the last added vertex $n$ via a directed path (the descendants) in the standard preferential attachment graph. contribution 0.87 0.77 0.04 asserted 0.59
In this model, vertices are sequentially added, each born with outdegree $m\ge 2$; the endpoint of each outgoing edge is chosen among previously added vertices with probability proportional to the current degree of the vertex plus some number $\rho$. background 0.51 0.07 0.02 asserted 0.97
We show that $X^{(n)}/n^\nu$ converges in distribution as $n\to\infty$, where $\nu$ depends on both $m$ and $\rho$, and the limiting distribution is given by a product of a constant factor and the $(1-\nu)$-th power of a Gamma(m/(m-1),1) variable. result 1.00 0.96 0.94 asserted 1.00
The proof uses a P\'olya urn representation of preferential attachment graphs, and the arguments of Janson (2024) where the same problem was studied in uniform attachment graphs. method 1.00 0.32 0.02 asserted 0.96
Further results, including convergence of all moments and analogues for the version with possible self-loops are provided. contribution 0.54 0.90 0.04 asserted 0.96

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00

What was examined, and what was not

Sources read

  • arXiv listing abstract v1

Not examined

  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers

Levels run

  • P abstract

Not run

  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

How the labels were made

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 4,518 input tokens.

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON

References (23)
  1. [13] Svante Janson: The number of descendants in a random dir ected acyclic graph. Random Structures Algorithms 64 (2024), no. 3, pp. 768–803 on Pith
  2. [3] Noam Berger, Christian Borgs, Jennifer T. Chayes, and Am in Saberi: Asymptotic behavior and distributional limits of preferential attachment graphs. Ann. Probab. 42 (2014), no. 1, pp. 1–40 on Pith
  3. [1] Krishna B. Athreya and Peter E. Ney: Branching Processes. Springer-Verlag, Berlin, 1972 on Pith
  4. [2] Albert-L´ aszl´ o Barab´ asi and Reka Albert: Emergence of scaling in random networks. Science 286 (1999), no. 5439, pp. 509–512 on Pith
  5. [4] Patrick Billingsley: Convergence of Probability Measures . Wiley, New York, 1968 on Pith
  6. [5] B´ ela Bollob´ as and Oliver Riordan: The diameter of a sca le-free random graph. Combinatorica 24 (2004), no. 1, pp. 5–34 on Pith
  7. [6] B´ ela Bollob´ as, Oliver Riordan, Joel Spencer, and G´ abor Tusn´ ady: The degree sequence of a scale-free random graph process. Random Structures Algorithms 18 (2001), no. 3, pp. 279–290 on Pith
  8. [7] Donald L. Burkholder: Distribution function inequalit ies for martingales. Ann. Probab. 1 (1973), no. 1, pp. 19—42 on Pith
  9. [8] Robert P. Dobrow and Robert T. Smythe: Poisson approxima tions for functionals of random trees. Random Structures Algorithms 9 (1996), no. 1-2, 79–92 on Pith
  10. [9] Philippe Flajolet, Xavier Gourdon, and Philippe Dumas: Mellin transforms and asymptotics: har- monic sums. Theoret. Comput. Sci. , 144 (1995), no. 1-2, pp. 3–58 on Pith
  11. [10] Allan Gut: Probability: A Graduate Course , 2nd ed., Springer, New York, 2013 on Pith
  12. [11] Remco van der Hofstad: Random Graphs and Complex Networks, Vol. 1 , Cambridge Univ. Press, Cambridge, 2017 on Pith
  13. [12] Remco van der Hofstad: Random Graphs and Complex Networks, Vol. 2 , Cambridge Univ. Press, Cambridge, 2024 on Pith
  14. [14] Olav Kallenberg: Foundations of Modern Probability. 2nd ed., Springer, New York, 2002 on Pith
  15. [15] Donald E. Knuth: The Art of Computer Programming , Section 7.2.2.3. Preliminary draft, 29 January on Pith
  16. [16] Markus Kuba and Stephan Wagner: On the distribution of d epths in increasing trees. Electron. J. Combin. 17 (2010), no. 1, Research Paper 137, 9 pp on Pith
  17. [17] Tiffany Y. Y. Lo: Local weak limit of preferential attach ment random trees with additive fitness. Advances in Applied Probability 56 (2024), no. 3, pp. 785–824 on Pith
  18. [18] Tam´ as F. M´ ori: The maximum degree of the B´ arab´ asi-Albert random tree. Combinatorics, Probability and Computing 14 (2005), no. 3, pp. 339–348 on Pith
  19. [19] NIST Handbook of Mathematical Functions . Edited by Frank W. J. Olver, Daniel W. Lozier, Ronald F. Boisvert and Charles W. Clark. Cambridge Univ. Press, 201 0. Also available as NIST Digital Library of Mathematical Functions , http://dlmf.nist.gov/ on Pith
  20. [20] Alois Panholzer and Helmut Prodinger: Level of nodes in increasing trees revisited. Random Structures Algorithms 31 (2007), no. 2, 203–226 on Pith
show 3 more
  1. [21] Erol Pek¨ oz, Adrian R¨ ollin and Nathan Ross: Joint degr ee distributions of preferential attachment random graphs. Advances in Applied Probability 49 (2017), no. 2, pp. 368–387 on Pith
  2. [22] Ward Whitt: Weak convergence of probability measures o n the function space C[0, ∞ ). Annals of Mathematical Statistics 41 (1970), no. 3, pp. 939–944. Department of Mathematics, Uppsala University, PO Box 480, SE-751 06 Uppsala, Swe- den Email address : svante.janson@math.uu.s... on Pith
  3. [2023] (To appear in Volume 4, Fascicle 7.) on Pith
Cited by 1 Pith paper

Reviewed papers on Pith that cite this one. The full citation record

  1. Tracing dependency networks explains how origins shape downstream vulnerability physics.soc-ph · Nov 2026

Challenges and discussion

Disagree with the review, or know something it missed? Leave a comment, or challenge this review formally: a challenge becomes a permanent entry in this paper's record, and its decision is published here.

No comments yet.

Sign in to comment