TY - UNPB

T1 - Detecting a late changepoint in the preferential attachment model

AU - Bet, Gianmarco

AU - Bogerd, Kay

AU - Castro, Rui M.

AU - Hofstad, Remco van der

PY - 2023/10/4

Y1 - 2023/10/4

N2 - 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 $\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 the regime where $\delta_0$ and $\delta_1$ are fixed, and the changepoint occurs close to the observation time of the network (i.e., $\tau_n = n - c n^\gamma$ with $c>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 tests based on the number of vertices with minimal degree, and show that these are asymptotically powerful when $\tfrac{1}{2}

AB - 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 $\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 the regime where $\delta_0$ and $\delta_1$ are fixed, and the changepoint occurs close to the observation time of the network (i.e., $\tau_n = n - c n^\gamma$ with $c>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 tests based on the number of vertices with minimal degree, and show that these are asymptotically powerful when $\tfrac{1}{2}

KW - math.ST

KW - math.PR

KW - stat.TH

KW - 05C80, 60F05, 62M02, 60C05

M3 - Preprint

BT - Detecting a late changepoint in the preferential attachment model

ER -