Pith. sign in

REVIEW 2 major objections 4 minor 45 references

A Proof of The Changepoint Detection Threshold Conjecture in Preferential Attachment Models

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

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

Pith's one-line read This paper proves that when the attachment parameter changes within the last $o(\sqrt{n})$ steps of a growing preferential attachment network, no test based solely on the final snapshot can detect the change: the total variation distance…

desk verdict Strong paper resolving a real conjecture, but the stochastic domination lemma at the heart of the proof has a genuine gap that needs repair. read the letter →

arxiv 2502.00514 v3 pith:7F2JUX5B submitted 2025-02-01 math.PR math.COmath.STstat.TH

Hang Du , Shuyang Gong , Jiaming Xu This is my paper · ORCID
classification math.PRmath.COmath.STstat.TH MSC 05C8060J8062F03
keywords preferentialattachmentchangepointdetectiontotalvariationdistancelikelihoodratiosecondmomentmethodEfron-Steininequalitybranchingprocesssinglenetworksnapshot
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

The paper resolves a conjecture on changepoint detection in preferential attachment networks. It shows that if the network's attachment rule changes at time $n - o(\sqrt{n})$, the final snapshot contains too little information for any statistical test to distinguish the changed network from one that never changed. The proof bounds the total variation distance between the two snapshot distributions and shows that it vanishes, so the best possible test is no better than random guessing. It also proves that no estimator can locate the changepoint with error $o(\sqrt{n})$, matching the known $O(\sqrt{n})$ estimator and settling the localization threshold. A reader should care because this identifies a fundamental information limit: in the late-change regime, no clever use of network structure can beat random guessing.

What carries the argument

The argument is carried by an exact likelihood-ratio formula between the changed and unchanged conditional models after revealing the network history up to time $M = n - N$ with $\Delta^2 \ll N \ll n$. For a single late changepoint ($\tau_n = n-1$), the likelihood ratio is $C_1 \frac{1}{N} \sum_{v \in V_n \setminus V_M} |C(v)| \lambda_v X_v$, where $C(v)$ is the connected component of vertex $v$ in the subgraph of late vertices, $\lambda_v$ is the probability that $v$ is the last vertex to arrive given its component, and $X_v$ is the ratio of attachment probabilities under the changed versus unchanged rule. The proof controls the second moment of this ratio using the Efron–Stein inequality; the key variance estimate $\mathrm{Var}[S] = O(1/N)$ rests on showing that the size of a late vertex's component is stochastically dominated by a sub-critical branching process with offspring distribution $\mathrm{Binomial}(m, 2N/n)$ plus $\mathrm{Geometric}(1 - 2mN/n)$. An interpolation triangle inequality reduces a change $\Delta$ steps before the end to $\Delta$ one-step changes, so the one-step bound $O(1/\sqrt{N})$ with $N \gg \Delta^2$ yields the theorem.

What would settle it

Simulate the conditional null model for moderate $n$ and estimate $\mathrm{Var}[S] = \mathrm{Var}[(1/N)\sum_v |C(v)| \lambda_v X_v]$ or the component-size tail $P[|C(v)| \geq k]$ for a window $N$ with $n - \tau_n = 1$: a decay slower than $1/N$, or a tail exceeding $2e^{-k+1}$, would expose a failure in the branching-process domination and invalidate the theorem.

Watch

Extended reading notes

Core claim

The central discovery is Theorem 2.3: for fixed $m \geq 1$ and $\delta \neq \delta'$, if $\tau_n$ satisfies $n - \tau_n = o(\sqrt{n})$, then $\mathrm{TV}(Q_{n,n}, Q_{n,\tau_n}) = o(1)$, where $Q_{n,\tau_n}$ is the distribution of the final snapshot when the attachment shift changes from $\delta$ to $\delta'$ at time $\tau_n$. Since the minimum achievable sum of Type-I and Type-II errors equals one minus total variation, this makes every test asymptotically powerless. Theorem 2.4 extends the result to estimation: no estimator based on the snapshot can satisfy $|\hat{\tau}_n - \tau_n| = o(\sqrt{n})$ with non-vanishing probability uniformly over $\tau_n \in [\varepsilon n, n]$. Together these results confirm the conjecture raised in [7] and show that the estimator proposed in [8], which attains $O(\sqrt{n})$ error, is order-optimal.

Load-bearing premise

The proof's variance bound rests on Lemma 5.6's claim that a late vertex's component is stochastically dominated by a sub-critical branching process with independent $\mathrm{Binomial}(m, 2N/n)$ and $\mathrm{Geometric}(1 - 2mN/n)$ offspring; if the conditional independence or the union bound behind that domination fails, the $O(1/N)$ variance estimate and the total-variation conclusion do not follow.

Editorial extensions

If this is right

  • The minimum-degree test of [7] is optimal up to constants: it detects strongly when $n-\tau_n = \omega(\sqrt{n})$, detects weakly when $n-\tau_n = \Omega(\sqrt{n})$, and the new result shows nothing can detect when $n-\tau_n = o(\sqrt{n})$.
  • Any estimator of the changepoint from the final snapshot has worst-case error at least of order $\sqrt{n}$ uniformly over $\tau_n \in [\varepsilon n, n]$, so the $O(\sqrt{n})$ accuracy of the estimator in [8] cannot be improved in rate.
  • The impossibility is information-theoretic rather than computational: even a test that uses all degrees and all subgraph structure of the snapshot fails in the $o(\sqrt{n})$ regime.
  • The result remains true if the observer is also given the entire network history up to any time $t$ satisfying $\Delta^2 \ll n-t \ll n$, so the barrier is intrinsic to the late-vertex structure of the snapshot.

Reading between the lines

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

  • The proof's dependence on an explicit encoding suggests the $\sqrt{n}$ threshold is a property of the hidden arrival order rather than of the affine attachment rule; the same interpolation and Efron–Stein strategy should transfer to polynomial or arbitrary attachment functions once an analogous encoding and branching domination are available.
  • The theorem does not pin down the constant: for $\Delta = c\sqrt{n}$, weak detection is possible, but the exact range of $c$ where tests remain essentially powerless, and the optimal constant in the $\sqrt{n}$ localization error, remain open.
  • The impossibility applies strictly to a single final snapshot with no side information; repeated snapshots, vertex timestamps, or node metadata would bypass the information limit identified here.
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 / 4 minor

Summary. The paper studies changepoint detection and localization in preferential attachment models with affine attachment function, where a single final snapshot of the network is observed. The main results are Theorem 2.3, asserting that if the changepoint occurs at time τ_n with n - τ_n = o(√n), then the total variation distance between the null distribution P_n and the alternative distribution Q_{n,τ_n} tends to 0, so every test is asymptotically powerless; and Theorem 2.4, asserting that no estimator can locate the changepoint within o(√n) with non-vanishing probability uniformly over τ_n ∈ [εn, n]. The proof strategy interpolates the changepoint one step at a time, reveals the network history up to time n - N with Δ^2 ≪ N ≪ n, derives a closed-form likelihood ratio (Proposition 5.1), and bounds its variance by the Efron-Stein inequality (Proposition 4.1). The variance bound relies on a stochastic domination of component sizes by a subcritical branching process (Lemma 5.6 and Proposition 5.4). The paper is well structured and largely self-contained, with the main theorems stated precisely and the proof organized into explicit propositions and lemmas.

Significance. If correct, this is a substantial contribution: it resolves Conjecture 3.2 of Bet et al. and proves that the Bhamidi et al. changepoint estimator is order-optimal, establishing a sharp √n threshold for both detection and localization. The proof is ambitious and contains several elegant and reusable ideas, especially the interpolation over changepoint times, the partial-revelation likelihood ratio in Proposition 5.1, and the coupling via a subcritical branching process in Lemma 5.6-5.7. The paper also gives a clean reduction from localization impossibility to detection impossibility via a data-processing inequality, which is a nice structural step. However, the load-bearing stochastic-domination lemma (Lemma 5.6) is not fully proved as written; the issues identified below affect the central variance bound and hence the main theorems, so the manuscript requires nontrivial revision before it can be accepted.

major comments (2)
  1. [Lemma 5.6, Eq. (13)] The union bound for the number of type (ii) vertices conditions on a realization of T_{t-1} and N_t^1,...,N_t^{l-1}. These conditioning sets may contain vertices that are adjacent to v_l but were revealed through earlier leaves ("hidden children"). Each such vertex increases deg(v_l) from m to m+r, so the probability that a later vertex attaches to v_l is bounded by (m+r+δ)/D, not by (j+1)/M as the product in Eq. (13) assumes. Since Eq. (13) starts the product at j=0 and does not incorporate r, the bound is not valid uniformly over the conditioning events. This matters because the geometric domination in Eq. (14) is the exact input used to obtain the exponential tail in Proposition 5.4 and hence the O(1/N) variance bound in Proposition 4.1.
  2. [Lemma 5.6, sentence after Eq. (14)] The assertion that "the numbers of type (i) and type (ii) vertices in N_t^l are conditionally independent" is stated without proof and is not immediate from the preferential attachment dynamics. Both counts depend on the current degree of v_l and on which vertices have already been revealed; in particular, a large number of type (i) neighbors increases the current degree of v_l and therefore increases the rate of later type (ii) attachments. Marginal stochastic domination of each count does not imply that the sum is dominated by the independent sum Y+Z in Definition 5.5 without an additional independence or negative-association argument. Since this is the crucial step connecting the BFS component to the subcritical branching process, the proof needs an explicit coupling or a different argument at this point.
minor comments (4)
  1. [Section 4, proof of Theorem 2.3] The name "Cauchy-Schwartz" should be "Cauchy-Schwarz".
  2. [Lemma 5.6, Eq. (13)] The phrase "the first k times that v_l is attached by later vertices" is ambiguous when m>1, since v_l can receive several edges from the same vertex at one arrival time. If "times" means vertex arrivals, the per-time probability is at most m(j+1)/M and the binomial coefficient should be (N choose k), with an extra factor m^k; if "times" means edge arrivals, the text should say so explicitly. The final bound (mN/M)^k is correct in either case, but the counting should be clarified.
  3. [Section 5, encoder definition] In the definition of the encoder, the symbol K_{t,i} is first used as the size of the multi-set ⃗E_{t,i} but the text writes "∆= K_{t,i}"; this appears to be a typographical error for "=: K_{t,i}".
  4. [Proof of Theorem 2.4] In Eq. (2), the notation Q_{τ_n,τ_n} and Q_{τ_n,σ_n} is slightly confusing because the first subscript normally denotes the network size; the text later clarifies that these are distributions of the snapshot at time τ_n, but this should be stated at the point of first use.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof is a self-contained derivation from the model definition, with no fitted parameters and no load-bearing self-citation.

full rationale

The paper's main theorem is proved self-containedly: the likelihood ratio in Proposition 5.1 is computed directly from the model definition in Definition 2.1, and the subsequent variance bound rests on the paper's own Efron-Stein coupling and subcritical branching comparison in Lemmas 5.3, 5.6, and 5.7. No parameter is fitted to the target quantity, and no conclusion is imported from a prior statement of the conjecture. The only self-citation is [42], a survey of the second-moment method whose author overlap is not load-bearing because the technique is standard and the paper supplies its own exponential tail bound rather than relying on the survey for the result. The skeptical concern about Lemma 5.6's conditional-independence and union-bound steps is a potential gap in a de novo proof, not a circular reduction: the lemma is derived by the authors rather than assumed from earlier work, so even if it failed the result would be unproven, not circular. The detection-to-localization implication in Theorem 2.4 legitimately uses Theorem 2.3 as an input only after Theorem 2.3 has been proved. Accordingly, no circular step is present.

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

The proof has no free parameters fitted to data and introduces no new entities. It relies on standard probability inequalities and on the specific preferential attachment model. The key non-standard premise is the stochastic domination lemma (Lemma 5.6), which is proven but not independently verified.

assumptions (4)
  • standard math Data processing inequality for total variation
    Used in the interpolation step and in the proof of Theorem 2.4 to show that TV does not increase under transformations that regenerate the network (Section 1 and Eq. (2)).
  • standard math Efron-Stein inequality
    Used in Section 5 to bound the variance of the likelihood ratio by the sum of marginal influence terms.
  • domain assumption Stochastic domination of component size by a sub-critical branching process
    Lemma 5.6: the conditional distribution of the number of neighbors of a vertex is dominated by Binomial(m, 2N/n) + Geometric(1 - 2mN/n); the argument relies on the affine attachment rule and the lower bound M/n ≥ 1/2. This is the main technical premise of the proof.
  • domain assumption PA model definition with fixed m ≥ 1, δ, δ' > -m and n → ∞
    The model is the affine preferential attachment model with a changepoint in the additive shift; the proof assumes this specific parametric form.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Proof of The Changepoint Detection Threshold Conjecture in Preferential Attachment Models." pith.science (2026). https://pith.science/paper/7F2JUX5B

@misc{pith2026250200514,
  author       = {Pith},
  title        = {Pith review of: A Proof of The Changepoint Detection Threshold Conjecture in Preferential Attachment Models},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7F2JUX5B}},
  note         = {Machine review of arXiv:2502.00514}
}
abstract

We investigate the problem of detecting and estimating a changepoint in the attachment function of a network evolving according to a preferential attachment model on $n$ vertices, using only a single final snapshot of the network. Bet et al.~\cite{bet2023detecting} show that a simple test based on thresholding the number of vertices with minimum degrees can detect the changepoint when the change occurs at time $n-\Omega(\sqrt{n})$. They further make the striking conjecture that detection becomes impossible for any test if the change occurs at time $n-o(\sqrt{n}).$ Kaddouri et al.~\cite{kaddouri2024impossibility} make a step forward by proving the detection is impossible if the change occurs at time $n-o(n^{1/3}).$ In this paper, we resolve the conjecture affirmatively, proving that detection is indeed impossible if the change occurs at time $n-o(\sqrt{n}).$ Furthermore, we establish that estimating the changepoint with an error smaller than $o(\sqrt{n})$ is also impossible, thereby confirming that the estimator proposed in Bhamidi et al.~\cite{bhamidi2018change} is order-optimal.

Figures

Figures reproduced from arXiv: 2502.00514 by the authors.

Figure 1
Figure 1. A final network snapshot of a preferential attachment graph with [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure credit [28]: Typical Preferential attachment graph with m = 1 and ∆ = o(n 1/3 ). The arrows are pointing from a vertex to its parent. The arrival times of all vertices, except for the set S of leaf vertices (highlighted in bolded red), are revealed. To extend the impossibility result to ∆ = o(n 1/2 ), one can only reveal the vertices arriving up to time n − ∆′ , where ∆2 ≪ ∆′ ≪ n. However, when ∆ = Ω(n 1/3 ) … view at source ↗
Figure 3
Figure 3. Figure credit [28]: Typical Preferential attachment graph with m = 1 and ∆ = Ω(n 1/3 ). The arrows are pointing from a vertex to its parent. Vertices arriving after τn may attach to vertices arrived earlier in [τ ′ n + 1, τ ], as shown by dashed vertices at bottom. Step 1: Interpolation Our starting point is as follows. As illustrated in [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Typical Preferential attachment graph with [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

45 extracted references · 43 canonical work pages

  1. [1]

    Broadcasting on random recursive trees

    Louigi Addario-Berry, Luc Devroye, G ´abor Lugosi, and Vasiliki Velona. Broadcasting on random recursive trees. Annals of Applied Probability, 2021

    work page 2021

  2. [2]

    Root finding algorithms and persistence of jordan centrality in growing random trees

    Sayan Banerjee and Shankar Bhamidi. Root finding algorithms and persistence of jordan centrality in growing random trees. The Annals of Applied Probability , 32(3):2180–2210, 2022

    work page 2022

  3. [3]

    Fluctuation bounds for continuous time branching processes and evolution of growing trees with a change point

    Sayan Banerjee, Shankar Bhamidi, and Iain Carmichael. Fluctuation bounds for continuous time branching processes and evolution of growing trees with a change point. The Annals of Applied Probability, 33(4):2919–2980, 2023

    work page 2023

  4. [4]

    Degree centrality and root finding in growing random networks

    Sayan Banerjee and Xiangying Huang. Degree centrality and root finding in growing random networks. Electronic Journal of Probability, 28:1–39, 2023

    work page 2023

  5. [5]

    Emergence of scaling in random networks.Science, 286(5439):509–512, 1999

    Albert-L ´aszl´o Barab´asi and R´eka Albert. Emergence of scaling in random networks.Science, 286(5439):509–512, 1999

    work page 1999

  6. [6]

    Inference in balanced community modulated recursive trees

    Anna Ben-Hamou and Vasiliki Velona. Inference in balanced community modulated recursive trees. Bernoulli, 31(1):457–483, 2025

    work page 2025

  7. [7]

    Detecting a late changepoint in the preferential attachment model

    Gianmarco Bet, Kay Bogerd, Rui M Castro, and Remco van der Hofstad. Detecting a late changepoint in the preferential attachment model. arXiv preprint arXiv:2310.02603, 2023. 20

    work page Pith review arXiv 2023

  8. [8]

    Change point detection in network mod- els: Preferential attachment and long range dependence

    Shankar Bhamidi, Jimmy Jin, and Andrew Nobel. Change point detection in network mod- els: Preferential attachment and long range dependence. The Annals of Applied Probability, 28(1):35–78, 2018

    work page 2018

Show all 45 references
  1. [9]

    Change point estimation in a dynamic stochastic block model

    Monika Bhattacharjee, Moulinath Banerjee, and George Michailidis. Change point estimation in a dynamic stochastic block model. Journal of Machine Learning Research, 21(107):1–59, 2020

    2020

  2. [10]

    Concentration Inequalities - A Nonasymptotic Theory of Independence

    St ´ephane Boucheron, G ´abor Lugosi, and Pascal Massart. Concentration Inequalities - A Nonasymptotic Theory of Independence. Oxford University Press, 2013

    2013

  3. [11]

    Root estimation in galton–watson trees

    Anna M Brandenberger, Luc Devroye, and Marcel K Goh. Root estimation in galton–watson trees. Random Structures & Algorithms, 61(3):520–542, 2022

    2022

  4. [12]

    Archaeology of random recursive dags and cooper-frieze random networks

    Simon Briend, Francisco Calvillo, and G ´abor Lugosi. Archaeology of random recursive dags and cooper-frieze random networks. Combinatorics, Probability and Computing, 32(6):859– 873, 2023

    2023

  5. [13]

    Estimating the history of a random recursive tree

    Simon Briend, Christophe Giraud, G ´abor Lugosi, and D´eborah Sulem. Estimating the history of a random recursive tree. arXiv preprint arXiv:2403.09755, 2024

    2024 arXiv

  6. [14]

    Finding adam in random growing trees

    S ´ebastien Bubeck, Luc Devroye, and G´abor Lugosi. Finding adam in random growing trees. Random Structures & Algorithms, 50(2):158–172, 2017

    2017

  7. [15]

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

    S ´ebastien Bubeck, Ronen Eldan, Elchanan Mossel, and Mikl ´os R´acz. From trees to seeds: on the inference of the seed from large trees in the uniform attachment model. Bernoulli, 23(4A):2887–2916, 2017

    2017

  8. [16]

    On the influence of the seed graph in the preferential attachment model

    S ´ebastien Bubeck, Elchanan Mossel, and Mikl´os R´acz. On the influence of the seed graph in the preferential attachment model. IEEE Transactions on Network Science and Engineering, 2(1):30–39, 2015

    2015

  9. [17]

    Likelihood-based inference for ran- dom networks with changepoints

    Daniel Cirkovic, Tiandong Wang, and Xianyang Zhang. Likelihood-based inference for ran- dom networks with changepoints. arXiv preprint arXiv:2206.01076, 2022

    2022 arXiv

  10. [18]

    Eve, adam and the preferential attachment tree

    Alice Contat, Nicolas Curien, Perrine Lacroix, Etienne Lasalle, and Vincent Rivoirard. Eve, adam and the preferential attachment tree. Probability Theory and Related Fields , 190(1):321–336, 2024

    2024

  11. [19]

    Inference on the history of a randomly growing tree

    Harry Crane and Min Xu. Inference on the history of a randomly growing tree. Journal of the Royal Statistical Society Series B: Statistical Methodology, 83(4):639–668, 2021

    2021

  12. [20]

    Scaling limits and influence of the seed graph in preferential attachment trees

    Nicolas Curien, Thomas Duquesne, Igor Kortchemski, and Ioan Manolescu. Scaling limits and influence of the seed graph in preferential attachment trees. Journal de l’ ´Ecole Polytech- nique—Math´ematiques, 2:1–34, 2015

    2015

  13. [21]

    A preferential attachment model with random initial degrees

    Maria Deijfen, Henri Van Den Esker, Remco Van Der Hofstad, and Gerard Hooghiemstra. A preferential attachment model with random initial degrees. Arkiv f ¨or matematik, 47:41–72, 2009. 21

    2009

  14. [22]

    On the discovery of the seed in uniform attachment trees

    Luc Devroye and Tommy Reddad. On the discovery of the seed in uniform attachment trees. Internet Mathematics, pages 75–93, 2019

    2019

  15. [23]

    Change-point detection in dynamic networks with missing links

    Farida Enikeeva and Olga Klopp. Change-point detection in dynamic networks with missing links. Operations Research, 2025

    2025

  16. [24]

    On the asymptotic normality of estimating the affine preferential attachment network models with random initial degrees

    Fengnan Gao and Aad van der Vaart. On the asymptotic normality of estimating the affine preferential attachment network models with random initial degrees. Stochastic Processes and their Applications, 127(11):3754–3775, 2017

    2017

  17. [25]

    Statistical inference in parametric preferential attach- ment trees

    Fengnan Gao and Aad van der Vaart. Statistical inference in parametric preferential attach- ment trees. arXiv preprint arXiv:2111.00832, 2021

    2021 arXiv

  18. [26]

    Consistent es- timation in general sublinear preferential attachment trees

    Fengnan Gao, Aad van der Vaart, Rui Castro, and Remco van der Hofstad. Consistent es- timation in general sublinear preferential attachment trees. Electronic Journal of Statistics, 11(2):3979 – 3999, 2017

    2017

  19. [27]

    The recovery of the root of a tree

    John Haigh. The recovery of the root of a tree. Journal of Applied Probability, 7(1):79–88, 1970

    1970

  20. [28]

    On the impossibility of detect- ing a late change-point in the preferential attachment random graph model

    Ibrahim Kaddouri, Zacharie Naulet, and ´Elisabeth Gassiat. On the impossibility of detect- ing a late change-point in the preferential attachment random graph model. arXiv preprint arXiv:2407.18685, 2024

    2024 arXiv

  21. [29]

    Confidence sets for the source of a diffusion in regular trees

    Justin Khim and Po-Ling Loh. Confidence sets for the source of a diffusion in regular trees. IEEE Transactions on Network Science and Engineering, 4(1):27–40, 2016

    2016

  22. [30]

    An efficient reconciliation algorithm for social networks

    Nitish Korula and Silvio Lattanzi. An efficient reconciliation algorithm for social networks. Proc. VLDB Endow., 7(5):377–388, January 2014

    2014

  23. [31]

    G ´abor Lugosi and Alan S. Pereira. Finding the seed of uniform attachment trees. Electronic Journal of Probability, 24:1–15, 2019

    2019

  24. [32]

    Times: Temporal information maximally extracted from structures

    Abram N Magner, Jithin K Sreedharan, Ananth Y Grama, and Wojciech Szpankowski. Times: Temporal information maximally extracted from structures. InProceedings of the 2018 World Wide Web Conference, pages 389–398, 2018

    2018

  25. [33]

    Information theory: From coding to learning

    Yury Polyanskiy and Yihong Wu. Information theory: From coding to learning. Cambridge university press, 2025

    2025

  26. [34]

    Correlated randomly growing graphs

    Mikl ´os Z R ´acz and Anirudh Sridhar. Correlated randomly growing graphs. The Annals of Applied Probability, 32(2):1058–1111, 2022

    2022

  27. [35]

    Rumors in a network: Who’s the culprit? IEEE Transac- tions on information theory, 57(8):5163–5181, 2011

    Devavrat Shah and Tauhid Zaman. Rumors in a network: Who’s the culprit? IEEE Transac- tions on information theory, 57(8):5163–5181, 2011

    2011

  28. [36]

    Finding rumor sources on random trees

    Devavrat Shah and Tauhid Zaman. Finding rumor sources on random trees. Operations research, 64(3):736–755, 2016

    2016

  29. [37]

    Random Graphs and Complex Networks (Volume One)

    Remco Van Der Hofstad. Random Graphs and Complex Networks (Volume One). Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2016. 22

    2016

  30. [38]

    Random Graphs and Complex Networks (Volume Two)

    Remco Van Der Hofstad. Random Graphs and Complex Networks (Volume Two). Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2024

    2024

  31. [39]

    Quickest change detection

    Venugopal V Veeravalli and Taposh Banerjee. Quickest change detection. In Academic press library in signal processing, volume 3, pages 209–255. Elsevier, 2014

    2014

  32. [40]

    Optimal change point detection and localization in sparse dynamic networks

    Daren Wang, Yi Yu, and Alessandro Rinaldo. Optimal change point detection and localization in sparse dynamic networks. The Annals of Statistics, 49(1):203–232, 2021

    2021

  33. [41]

    Locality statistics for anomaly detection in time series of graphs

    Heng Wang, Minh Tang, Youngser Park, and Carey E Priebe. Locality statistics for anomaly detection in time series of graphs. IEEE Transactions on Signal Processing, 62(3):703–717, 2013

    2013

  34. [42]

    Statistical problems with planted structures: Information- theoretical and computational limits

    Yihong Wu and Jiaming Xu. Statistical problems with planted structures: Information- theoretical and computational limits. arXiv preprint arXiv:1806.00118, 2018

    2018 arXiv

  35. [43]

    Sequential (quickest) change detection: Classical results and new directions

    Liyan Xie, Shaofeng Zou, Yao Xie, and Venugopal V Veeravalli. Sequential (quickest) change detection: Classical results and new directions. IEEE Journal on Selected Areas in Informa- tion Theory, 2(2):494–514, 2021

    2021

  36. [44]

    Phase transition in the recoverability of network history

    Jean-Gabriel Young, Guillaume St-Onge, Edward Laurence, Charles Murphy, Laurent H´ebert-Dufresne, and Patrick Desrosiers. Phase transition in the recoverability of network history. Physical Review X, 9(4):041056, 2019

    2019

  37. [45]

    Change-point detection in dynamic networks via graphon estimation

    Zifeng Zhao, Li Chen, and Lizhen Lin. Change-point detection in dynamic networks via graphon estimation. arXiv preprint arXiv:1908.01823, 2019. 23

    1908 arXiv

Pith tools

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