Pith. sign in

REVIEW 4 minor 37 references

Subcritical percolation and network archaeology on random recursive tree substrate networks

T0 review · 0 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read This paper proves that even when a random recursive tree is obscured by an Erdős–Rényi shortcut layer that creates cycles, the original root can be enclosed in a confidence set whose size depends on the error tolerance but not on the networ

desk verdict A careful, genuinely self-contained paper whose structural result is new but whose root-finding endpoint is already known; the authors say so, the proof holds up, and it deserves a serious referee. read the letter →

arxiv 2607.21428 v1 pith:ZC6754II submitted 2026-07-23 math.PR

Shankar Bhamidi , Akshay Sakanaveeti This is my paper · ORCID
classification math.PR MSC 05C8060K3560C05
keywords randomrecursivetreenetworkarchaeologyrootfindingbondpercolationJordancentralityinhomogeneousgraphsubcriticalregimeconfidencesets
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

Network archaeology asks whether a single unlabeled snapshot of a growing network still contains enough information to locate the first vertex. For trees, Jordan (centroid) centrality gives deterministic-size confidence sets, but cycles destroy the clean tree decomposition. This paper shows the signal survives a sparse Erdős–Rényi shortcut layer over a random recursive tree substrate. The device is auxiliary subcritical percolation: thinning the observed graph splits it into heavy-tailed tree-blobs wired by a subcritical rank-one random graph, so the largest components look like one large blob decorated by small shortcut pieces. Jordan centrality inside the largest percolated components then yields a root confidence set of size bounded by constants depending only on the error tolerance and model parameters, not on the network size.

What carries the argument

Auxiliary subcritical bond percolation on the observed graph, followed by a blob-and-shortcut renormalization. The retained recursive-tree edges form Yule–Simon blobs with sizes of order n^q and susceptibility (1−2q)^(−1); conditional on these blob sizes, the retained shortcut edges contract to a rank-one inhomogeneous random graph with effective offspring mean ρ(q,λ)=qλ/(1−2q). Subcriticality ρ<1 (equivalently q<1/(λ+2)) makes the largest full components equal to leading blobs amplified by (1−ρ)^(−1) plus o_P(n^q), and the root blob's rank among blobs is tight. Inside the root component, the root blob is a uniform attachment tree skeleton with singly attached shortcut decorations, so a weig

What would settle it

Simulate the model with, say, λ=1 and q=0.3 for increasing n, and measure the rank of the root blob among all percolated components along with the Jordan-based budget needed to contain the root. If for any fixed K the probability that the root blob ranks above K fails to stay high, or if the required budget grows with n, the deterministic-size claim is false; the paper predicts that the required (K, L) stabilizes as n grows.

Watch

Extended reading notes

Core claim

The central discovery is that the cyclic observed graph G_n = T_n ∪ H_n admits the same root-finding guarantee as the tree alone. With retention parameter q < min{1/(λ+2), 1/3}, the retained tree edges partition the latent recursive tree into blobs whose sizes follow a Yule–Simon law; conditional on blob sizes, retained shortcuts form a rank-one inhomogeneous random graph. Because the effective branching factor ρ(q,λ)=qλ/(1−2q) is below 1, the shortcut layer is subcritical: the K largest full percolated components are exactly the components seeded by the K largest blobs, and the root blob sits among them with tight rank. Inside the root component the root blob is a uniform attachment tree ca

Load-bearing premise

The shortcut layer after percolation must be subcritical: the effective branching factor ρ(q,λ)=qλ/(1−2q) must stay below 1, and additionally q<1/3 so the size-biased blob law has finite second moment; if either fails, the decorated-skeleton analysis collapses.

Editorial extensions

If this is right

  • A single unlabeled snapshot of a sparse cyclic network can be rooted with a confidence set of size bounded independently of the network size.
  • The structural theorem gives a precise subcritical component picture: largest percolated components are leading blobs amplified by a deterministic factor (1−ρ)^(−1), analogous to subcritical power-law random graphs.
  • Tree-based centrality arguments transfer to cyclic networks through percolation coarse-graining, rather than through posterior sampling or high-degree filtering.
  • The required budgets K and L depend only on ε, q, and λ, so the guarantee is uniform across network sizes.
  • The proof isolates the recursive-tree inputs, suggesting the same percolate-and-decorate pipeline can be rerun for other attachment mechanisms once the blob law, susceptibility, and root estimate are known.

Reading between the lines

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

  • If the sketched extension to preferential attachment substrates holds, auxiliary subcritical percolation could become a general reduction from cyclic network archaeology to tree root-finding, with each substrate contributing its own blob law and susceptibility.
  • The authors flag q<1/3 as a technical, likely non-sharp restriction; if it can be removed, the admissible root-finding range would widen to the full subcritical window and the budget constants could improve.
  • The auxiliary parameter q creates an algorithmic tradeoff between subcriticality and fragmentation; optimizing q and the resulting budgets is an open problem the paper leaves for future work.
  • A natural stress test is to replace the homogeneous shortcut layer with a community-structured or heavier-tailed shortcut graph; observing whether the rank-one subcritical mechanism is essential would delimit the method's scope.
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

0 major / 4 minor

Summary. The paper treats network archaeology for the unlabeled cyclic observed graph G_n = T_n ∪ H_n, where T_n is a random recursive tree and H_n is an independent Erdős–Rényi shortcut layer with edge probability λ/n. The main tool is auxiliary subcritical bond percolation. Retaining edges with probability p < 1/(λ+2), the retained tree edges form heavy-tailed Yule–Simon blobs, while retained shortcuts contract to a subcritical rank-one inhomogeneous random graph with susceptibility ρ(p,λ)=pλ/(1−2p). Theorem 3.1 shows that, to first order, the largest full percolation components are the largest backbone blobs amplified by (1−ρ)^{-1}. Theorem 3.2 then proves that for auxiliary retention probability q < min{1/(λ+2), 1/3}, the root-finding rule H_{K,L}, which takes the K largest q-percolated components and the L best graph-Jordan vertices inside each, contains vertex 1 with probability tending to 1−ε, with K,L depending only on ε,q,λ. The proof chain includes Yule-embedding blob asymptotics, a subcritical rank-one comparison theorem, a decorated-skeleton reduction of the root component, a robust weighted-Jordan theorem for uniform attachment trees, and a deterministic transfer from weighted to ordinary Jordan centrality. The restriction q<1/3 is explicitly acknowledged as not sharp and is used only to keep the third empirical blob moment O_P(1).

Significance. If the result holds, it extends deterministic-size root-confidence-set theory from growing trees to sparse graphs with cycles, and does so through a genuinely new percolative coarse graining rather than posterior sampling or high-degree filtering. The paper is unusually self-contained: the Yule-process blob limits, the subcritical shortcut exploration, the conditional rank-one comparison, and the decorated-skeleton Jordan transfer are all proved in detail. Theorem 3.1's subcritical component picture is of independent interest. The main limitation, q<1/3, is clearly flagged as non-sharp and does not appear to conceal a gap. The relation to the very recent [DLM26] result is disclosed and discussed honestly; the percolation method and the structural theorem distinguish the contribution.

minor comments (4)
  1. [Section 5.4.1, Lemma 5.11] The weighted Jordan comparison lemma is proved in detail but is never cited in the subsequent proof: Lemma 5.12 proceeds by direct branch-size estimates rather than invoking this lemma. Either cite Lemma 5.11 where it is used or remove it to avoid a dangling statement.
  2. [Global / typesetting] Several OCR-style artifacts appear in the text, e.g. 'PERCOLA TION' and 'SUBSTRA TE' in the running header and 'o P' in place of o_P in some displays. Figure 4 refers to 'teal' and 'orange' regions; if the figure is printed in grayscale, the description should be made color-independent.
  3. [Section 5.4.2, Lemma 5.14] The reduction from external-component moments to full q-percolated component moments is correct, but the sentence 'deleting the root blob and incident shortcut edges only partitions components and removes vertices' is terse. One additional sentence explaining that for r≥1 the r-th power masses of the pieces are dominated by the original component's r-th power would improve readability.
  4. [Section 5.4.3, Proposition 5.18] Lemma 5.12 is stated for a fixed tree size m, while Proposition 5.18 applies it at the random size |B_root^n|. The explanation in the text is sufficient, but a formal random-size corollary of Lemma 5.12 with the same uniform constants would make the application cleaner.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof chain is self-contained and self-citations are not load-bearing.

full rationale

The paper's main derivation is carried out from the model assumptions plus standard Yule-process and branching-process facts, and it does not reduce to its own conclusions. Theorem 3.1 is proved in-paper via the Yule embedding (Lemmas 5.1–5.3 and Proposition 5.4), the rank-one shortcut-graph analysis (Lemmas 5.6–5.10, Theorem 5.8), and the subcritical component comparison. Theorem 3.2 is then derived from Theorem 3.1 and the decorated-skeleton argument (Lemmas 5.13–5.17 and Proposition 5.18), with Lemma 5.12 proving the needed weighted-Jordan root estimate directly rather than importing it from prior work. The auxiliary percolation parameter q is part of the algorithm, not a fitted quantity, and no 'predicted' quantity is defined in terms of the output. The only cited results that could in principle be self-referential are background mentions such as [BB22] and [BH23]; these are not used as load-bearing uniqueness theorems or as justifications for the central estimates, and the paper explicitly proves the recursive-tree percolation inputs rather than invoking a black-box theorem. The q<1/3 restriction is an acknowledged moment condition, not a circular repackaging of the desired conclusion. The paper is self-contained against the relevant external benchmarks, so no circular step is present.

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

The paper introduces no new physical entities. The blobs, contracted shortcut graph, and decorated skeleton are analytical constructions of the proof, not postulated objects requiring independent evidence. The only hand-chosen quantity is the auxiliary percolation parameter q, which is not fitted to data and is allowed to vary in an explicit range.

free parameters (1)
  • q (auxiliary percolation retention probability) = any q in (0, min{1/(λ+2), 1/3})
    Chosen by the algorithm/proof rather than fitted to data. K and L depend on q, but the theorem holds for every admissible q. The q<1/3 bound is a finite-second-moment convenience explicitly stated as not sharp.
assumptions (6)
  • domain assumption The latent substrate T_n is a random recursive tree and H_n is an independent Erdős–Rényi shortcut graph with edge probability λ/n; the observer sees only the unlabeled isomorphism class.
    Model definition in Section 2; all theorems are statements about this generative model.
  • domain assumption Bernoulli bond percolation on G_n retains tree edges and shortcut edges independently with the same probability p or q.
    Section 2.1; independence is inherited from the model but is an explicit modeling choice for the auxiliary randomness.
  • standard math The random recursive tree can be embedded in a Yule process stopped at the first hitting time of size n.
    Section 5.1; standard equivalence used to derive the blob-size asymptotics.
  • standard math Retained tree edges under percolation correspond to type families in the Yule mutation representation.
    Section 5.1; standard thinning property of Yule birth processes, used in Lemmas 5.1–5.4.
  • standard math Shortcut exploration among blobs can be dominated by a subcritical Poisson multitype branching process on the rank-one weight sequence.
    Lemmas 5.6–5.8 and 5.14; uses standard Poisson coupling and monotonicity arguments.
  • standard math In a uniform attachment tree, the root's first two child branches grow linearly with positive asymptotic fraction almost surely.
    Lemma 5.12; follows from the Yule embedding and is used to show the root is separated from the total weighted mass.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Subcritical percolation and network archaeology on random recursive tree substrate networks." pith.science (2026). https://pith.science/paper/ZC6754II

@misc{pith2026260721428,
  author       = {Pith},
  title        = {Pith review of: Subcritical percolation and network archaeology on random recursive tree substrate networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZC6754II}},
  note         = {Machine review of arXiv:2607.21428}
}
read the original abstract

We study a network-archaeology problem for a dynamic graph whose latent substrate is a random recursive tree and whose observed topology is enriched by an independent homogeneous Erd\H{o}s-R\'enyi shortcut layer. From a single unlabeled snapshot, the goal is to construct a confidence set of deterministic size for the first vertex. Since shortcut edges create cycles, the usual tree-based arguments using Jordan centrality do not apply directly. Our method uses auxiliary subcritical bond percolation to expose a tree-like renormalized structure: retained recursive-tree clusters form heavy-tailed blobs, retained shortcuts connect these blobs through a subcritical rank-one random graph, and large components are leading backbone blobs decorated by subcritical shortcut pieces. Applying Jordan centrality inside the largest auxiliary percolation components then gives a deterministic-size root confidence set for the cyclic observed network.

Figures

Figures reproduced from arXiv: 2607.21428 by the authors.

Figure 1
Figure 1. Schematic overview of the root-finding strategy. Left: the observed graph; the solid and dashed edge styles indicate the latent tree and shortcut layers, a distinction unavailable to the algorithm. Middle: after auxiliary q￾percolation, the analysis decomposes the retained graph into tree blobs joined by retained shortcut edges. Right: the resulting components are ranked by size, and Jordan centrality is applied wit… view at source ↗
Figure 2
Figure 2. The model. Left: the latent random recursive tree Tn, rooted at vertex 1. Right: the observed graph Gn = Tn ∪ Hn, where Hn ∼ ER(n, λ/n) is the independent shortcut layer (dashed). In the unlabeled snapshot G◦ n , tree edges and shortcut edges are indistinguishable; the colors and vertex labels shown here are not available to the observer [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. From the observed graph to the subcritical blob picture. Top: the observed graph Gn = Tn ∪ Hn and its q-percolation G (q) n , in which each edge is retained independently with probability q (deleted edges dotted). Bottom left: the backbone blobs, the connected clusters of retained tree edges, ranked by mass Wn,1 ⩾ Wn,2 ⩾ · · · with ties broken by smallest vertex label; the blob containing vertex 1 is the root blob B… view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: Structural and root-finding parameter ranges for the random recur￾sive tree substrate. The teal curve pc(λ) = 1/(λ + 2) is the rank-one critical curve ρ(p, λ) = 1: below it the shortcut layer is subcritical. Root finding uses the smaller auxiliary range q < min{pc(λ), …
Figure 5
Figure 5. Figure 5: The Yule mutation clock. Families born before a fixed time T have explicit n p -scale limits at τn, while the largest family born after T is negligible after taking T → ∞. Bond percolation on the genealogy can be represented by mutations at births: with proba￾bility p,…
Figure 6
Figure 6. Figure 6: Shortcut exploration from one large blob. In the subcritical regime, successive shortcut generations have masses approximately W, ρW, ρ2W, . . ., giv￾ing the amplification factor (1 − ρ) −1 . Lemma 5.6 (Subcritical exploration from one large blob). Assume p < pc(λ). Le…
Figure 7
Figure 7. Figure 7: Withholding step in Lemma 5.10. To test whether Bn,i can share a full shortcut component with another top blob, all other top blobs are withheld and the component of Bn,i is explored only through lower-ranked blobs. The explored cloud has mass R (K) n,i = OP(n p ); any…
Figure 8
Figure 8. Figure 8: The root component as a decorated skeleton. The root blob is a uniform attachment tree; shortcut pieces attach singly to its vertices. The right panel contracts each decoration Du into the vertex weight Xu = |Du|, giving the weighted skeleton used for the Jordan compar…
Figure 9
Figure 9. Figure 9: The decorated skeleton, in the example of [PITH_FULL_IMAGE:figures/full_fig_p033_9.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

37 extracted references · 23 linked inside Pith

  1. [1]

    Optimal root recovery for uniform attachment trees and

    Addario-Berry, Louigi and Fontaine, Catherine and Khanfir, Robin and Langevin, Louis-Roy and T. Optimal root recovery for uniform attachment trees and. arXiv preprint arXiv:2411.18614 , year =. doi:10.48550/arXiv.2411.18614 , note =. 2411.18614 , archivePrefix =

    arXiv doi:10.48550/arxiv.2411.18614

  2. [2]

    Leaf stripping on uniform attachment trees , journal =

    Addario-Berry, Louigi and Brandenberger, Anna and Briend, Simon and Broutin, Nicolas and Lugosi, G. Leaf stripping on uniform attachment trees , journal =. 2025 , doi =. 2410.06481 , archivePrefix =

    arXiv 2025

  3. [3]

    The Annals of Applied Probability , volume =

    Banerjee, Sayan and Bhamidi, Shankar , title =. The Annals of Applied Probability , volume =. 2022 , doi =

    2022

  4. [4]

    Probability Theory and Related Fields , volume =

    Banerjee, Sayan and Bhamidi, Shankar , title =. Probability Theory and Related Fields , volume =. 2021 , doi =. 2004.13785 , archivePrefix =

    arXiv 2021

  5. [5]

    Electronic Journal of Probability , volume =

    Banerjee, Sayan and Huang, Xiangying , title =. Electronic Journal of Probability , volume =. 2023 , doi =

    2023

  6. [6]

    Random Structures & Algorithms , volume =

    Baur, Erich , title =. Random Structures & Algorithms , volume =. 2016 , eprint =

    2016

  7. [7]

    Electronic Journal of Probability , volume =

    Bertoin, Jean , title =. Electronic Journal of Probability , volume =. 2014 , doi =. 1305.4762 , archivePrefix =

    arXiv 2014

  8. [8]

    The phase transition in inhomogeneous random graphs , journal =

    Bollob. The phase transition in inhomogeneous random graphs , journal =. 2007 , doi =

    2007

Show all 37 references
  1. [9]

    Bubeck, S. Finding. Random Structures & Algorithms , volume =. 2017 , doi =. 1411.3317 , archivePrefix =

    2017 arXiv

  2. [10]

    From trees to seeds: on the inference of the seed from large trees in the uniform attachment model , journal =

    Bubeck, S. From trees to seeds: on the inference of the seed from large trees in the uniform attachment model , journal =. 2017 , doi =. 1409.7685 , archivePrefix =

    2017 arXiv

  3. [11]

    Archaeology of random recursive dags and

    Briend, Simon and Calvillo, Francisco and Lugosi, G. Archaeology of random recursive dags and. Combinatorics, Probability and Computing , volume =. 2023 , doi =. 2207.14601 , archivePrefix =

    2023 arXiv

  4. [12]

    Random Structures & Algorithms , volume =

    Brandenberger, Anna and Marcussen, Cassandra and Mossel, Elchanan and Sudan, Madhu , title =. Random Structures & Algorithms , volume =. 2026 , doi =. 2411.14336 , archivePrefix =

    2026 arXiv

  5. [13]

    Estimating the history of a random recursive tree , journal =

    Briend, Simon and Giraud, Christophe and Lugosi, G. Estimating the history of a random recursive tree , journal =. 2025 , doi =. 2403.09755 , archivePrefix =

    2025 arXiv

  6. [14]

    A study of centrality measures in random recursive trees , journal =

    Coll Josifov, Richard and Devroye, Luc and Lugosi, G. A study of centrality measures in random recursive trees , journal =. 2026 , eprint =

    2026

  7. [15]

    History estimation in random recursive trees: Pointwise approach via iterated

    B. History estimation in random recursive trees: Pointwise approach via iterated. arXiv preprint arXiv:2606.24465 , year =. 2606.24465 , archivePrefix =

    arXiv

  8. [16]

    Journal of the Royal Statistical Society Series B: Statistical Methodology , volume =

    Crane, Harry and Xu, Min , title =. Journal of the Royal Statistical Society Series B: Statistical Methodology , volume =. 2024 , doi =. 2107.00153 , archivePrefix =

    2024 arXiv

  9. [17]

    Journal of the Royal Statistical Society Series B: Statistical Methodology , volume =

    Crane, Harry and Xu, Min , title =. Journal of the Royal Statistical Society Series B: Statistical Methodology , volume =. 2021 , doi =. 2005.08794 , archivePrefix =

    2021 arXiv

  10. [18]

    Probability Theory and Related Fields , volume =

    Contat, Alice and Curien, Nicolas and Lacroix, Perrine and Lasalle, Etienne and Rivoirard, Vincent , title =. Probability Theory and Related Fields , volume =. 2024 , doi =. 2303.04752 , archivePrefix =

    2024 arXiv

  11. [19]

    Internet Mathematics , volume =

    Reddad, Tommy and Devroye, Luc , title =. Internet Mathematics , volume =. 2019 , doi =. 1810.00969 , archivePrefix =

    2019 arXiv

  12. [20]

    Devroye, Luc and Lugosi, G. Finding. arXiv preprint arXiv:2607.18201 , year =. 2607.18201 , archivePrefix =

    arXiv

  13. [21]

    2009 , doi =

    Drmota, Michael , title =. 2009 , doi =

    2009

  14. [22]

    Acta Mathematica Sinica, English Series , volume =

    Gu, Chenlin and Yuan, Linglong , title =. Acta Mathematica Sinica, English Series , volume =. 2026 , doi =. 2408.12515 , archivePrefix =

    2026 arXiv

  15. [23]

    The Annals of Applied Probability , volume =

    Janson, Svante , title =. The Annals of Applied Probability , volume =. 2008 , doi =. 0708.4404 , archivePrefix =

    2008 arXiv

  16. [24]

    1975 , isbn =

    Jagers, Peter , title =. 1975 , isbn =

    1975

  17. [25]

    Advances in Applied Probability , volume =

    Jagers, Peter and Nerman, Olle , title =. Advances in Applied Probability , volume =. 1984 , doi =

    1984

  18. [26]

    Moments of general time dependent branching processes with applications , journal =

    M. Moments of general time dependent branching processes with applications , journal =. 2019 , doi =

    2019

  19. [27]

    Zeitschrift f

    Nerman, Olle , title =. Zeitschrift f. 1981 , doi =

    1981

  20. [28]

    Random trees and general branching processes , journal =

    Rudas, Anna and T. Random trees and general branching processes , journal =. 2007 , doi =

    2007

  21. [29]

    Random Structures & Algorithms , volume =

    Jog, Varun and Loh, Po-Ling , title =. Random Structures & Algorithms , volume =. 2018 , doi =

    2018

  22. [30]

    Justice, Sam and Shyamalkumar, N. D. , title =. arXiv preprint arXiv:1905.07652 , year =. 1905.07652 , archivePrefix =

    1905 arXiv

  23. [31]

    IEEE Transactions on Network Science and Engineering , volume =

    Khim, Justin and Loh, Po-Ling , title =. IEEE Transactions on Network Science and Engineering , volume =. 2017 , doi =. 1510.05461 , archivePrefix =

    2017 arXiv

  24. [32]

    Finding the seed of uniform attachment trees , journal =

    Lugosi, G. Finding the seed of uniform attachment trees , journal =. 2019 , doi =. 1801.01816 , archivePrefix =

    2019 arXiv

  25. [33]

    PLoS Computational Biology , volume =

    Navlakha, Saket and Kingsford, Carl , title =. PLoS Computational Biology , volume =. 2011 , doi =. 1008.5166 , archivePrefix =

    2011 arXiv

  26. [34]

    IEEE Transactions on Information Theory , volume =

    Shah, Devavrat and Zaman, Tauhid , title =. IEEE Transactions on Information Theory , volume =. 2011 , doi =. 0909.4370 , archivePrefix =

    2011 arXiv

  27. [35]

    and Mahmoud, Hosam M

    Smythe, Robert T. and Mahmoud, Hosam M. , title =. Theory of Probability and Mathematical Statistics , volume =

  28. [36]

    2024 , doi =

    van der Hofstad, Remco , title =. 2024 , doi =

    2024

  29. [37]

    Phase transition in the recoverability of network history , journal =

    Young, Jean-Gabriel and St-Onge, Guillaume and Laurence, Edward and Murphy, Charles and H. Phase transition in the recoverability of network history , journal =. 2019 , doi =. 1803.09191 , archivePrefix =

    2019 arXiv

Pith tools

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