A0556
Title: Detecting a late changepoint in a growing network
Authors: Gianmarco Bet - Università degli Studi di Firenze (Italy) [presenting]
Abstract: Motivated by the problem of detecting a change in the evolution of a network, the preferential attachment random graph model with a time-dependent attachment function is considered. Our goal is to detect whether the attachment mechanism changes over time based on a single network snapshot. This question is cast 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$. It is focused on the regime where $\delta_0$ and $\delta_1$ are fixed, and the changepoint occurs close to the observation time $n$ of the network (i.e., $\tau_n = n-cn^{\gamma}$ with $c > 0$ and $\gamma\in(0,1)$). This corresponds to the relevant scenario where the aim is to detect the changepoint shortly after it has happened. Two tests based on the number of vertices with a minimal degree are presented, showing that these are asymptotically powerful when $\gamma > 1/2$. The first test requires knowledge of $\delta_0$. The second test is significantly more involved and does not require the knowledge of $\delta_0$ while achieving the same performance guarantees. It is proved that the test statistics for both tests are asymptotically normal, allowing for accurate calibration of the tests.
