Bet et al.'s changepoint detection threshold conjecture for preferential attachment models

Let $G_n$ be the final snapshot of a preferential attachment network on $n$ vertices, and suppose the changepoint is in the late-change regime $\tau_n=n-\Delta$ with $\bigtriangleup=c n^\gamma$, where $c>0$ and $\gamma\in(0,1)$. A test based on $G_n$ has Type-I and Type-II errors, and weak detection means that the sum of these errors is bounded away from $1$ as $n\to\infty$. Bet et al.'s conjecture. If $\gamma<1/2$, then all tests based on $G_n$ are powerless, that is, the sum of Type-I and Type-II errors converges to $1$ as $n\to\infty$. The conjecture identifies $\gamma=1/2$ as the changepoint detection threshold: the minimum-degree test achieves weak detection at the boundary, while detection below the threshold should be impossible. This conjecture is resolved affirmatively in the paper, which proves impossibility when the change occurs at time $n-o(\sqrt n)$; the corresponding impossibility of estimating the changepoint with error smaller than $o(\sqrt n)$ is also established.