Detecting a late changepoint in the preferential attachment model

Motivated by the problem of detecting a change in the evolution of a network, we consider the preferential attachment random graph model with a time-dependent attachment function. Our goal is to detect whether the attachment mechanism changed over time, based on a single snapshot of the network and without directly observable information about the dynamics. We cast this question as a hypothesis testing problem, where the null hypothesis is a preferential attachment model with a constant affine attachment parameter 𝛿0, and the alternative hypothesis is a preferential attachment model where the affine attachment parameter changes from 𝛿0 to 𝛿1 at an unknown changepoint time 𝜏𝑛. For our analysis we focus on the regime where 𝛿0 and 𝛿1 are fixed, and the changepoint occurs close to the observation time of the network (i.e., 𝜏𝑛 = 𝑛 − 𝑐𝑛𝛾 with 𝑐 > 0 and 𝛾 ∈ (0, 1)). This corresponds to a rather relevant scenario where we aim to detect the changepoint shortly after it has happened. We present two tests based on the number of vertices with minimal degree, and show that these are asymptotically powerful when 1 2 < 𝛾 < 1. We conjecture that any test based on the final network snapshot will be powerless when 𝛾 < 1 2 . The first test we propose requires knowledge of 𝛿0. The second test is significantly more involved, and does not require the knowledge of 𝛿0 while still achieving the same asymptotic performance guarantees. Furthermore, we prove that the test statistics for both tests are asymptotically normal, allowing for accurate calibration of the tests. This is demonstrated by numerical experiments, that also illustrate the finite sample test properties.