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

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. (2023) 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-Ω(√(n)). They further make the striking conjecture that detection becomes impossible for any test if the change occurs at time n-o(√(n)). Kaddouri et al. (2024) 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(√(n)). Furthermore, we establish that estimating the changepoint with an error smaller than o(√(n)) is also impossible, thereby confirming that the estimator proposed in Bhamidi et al. (2018) is order-optimal.