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. We frame this as a hypothesis testing problem where the null hypothesis is a preferential attachment model with $n$ vertices and a constant affine attachment with parameter $\delta_0$, and the alternative hypothesis is a preferential attachment model where the affine attachment parameter changes from $\delta_0$ to $\delta_1$ at an unknown changepoint time $\tau_n$. For our analysis we focus on a scenario where one only sees the final network realization (and not its evolution), and the changepoint occurs “late”, namely $\tau_n = n − cn^\gamma$ with $c \geq 0$ and $\gamma\in(0,1)$. This corresponds to the relevant scenario where we aim to detect the changepoint shortly after it has happened. We present two asymptotically powerful tests that are able to distinguish between the null and alternative hypothesis when $\gamma\gt 1/2$. The first test requires knowledge of $\delta_0$, while the second test is significantly more involved, and does not require the knowledge of $\delta_0$ while still achieving the same performance guarantees. Furthermore, we determine the asymptotic distribution of the test statistics, which allows us to easily calibrate the tests in practice. Finally, we conjecture that in the setting considered there are no powerful tests when $\gamma\lt 1/2$. Our theoretical results are complemented with numerical evidence that illustrates the finite sample characteristics of the proposed procedures.

Joint work with Gianmarco Bet, Kay Bogerd, and Remco van der Hofstad.