Detection, Estimation, and Reconstruction in Networks: A Proof of The Changepoint Detection Threshold Conjecture in Preferential Attachment Models
Presenter
April 23, 2025
Keywords:
- combinatorial statistics
- random graphs
- network inference
- network reconstruction
- detection
- estimation
MSC:
- 05C80 - Random graphs (graph-theoretic aspects) [See also 60B20]
- 60C05 - Combinatorial probability
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. 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. 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. is order-optimal.