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 at time $n$ 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 $\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 assume that the changepoint occurs close to the observation time of the network, which corresponds to the 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. The first test assumes knowledge of $\delta_0$, while the second does not. We show that these are asymptotically powerful when $n-\tau_n \gg n^{1/2}$. Furthermore, we prove that the test statistics for both tests are asymptotically normal, allowing for accurate calibration of the tests. If time allows, we will present numerical experiments to illustrate the finite sample test properties.
Area: CS8 - Combinatorial structures in probability and statistics (Elia Bisi)
Keywords: Preferential attachment model, Changepoint detection.
Please Login in order to download this file