Abstract

We study the problem of change point detection in dynamic networks. We assume that we observe a sequence $\{A(t)\}_{t=1,...,T} \subset R^{n \times n}$ of independent adjacency matrices. Our task is to recover with high accuracy the number and locations the of change points, which are assumed unknown. Our generic model setting allows for all the model parameters to change with the total number of time points $T$, including the network size $n$, the minimal spacing between consecutive change points $\Delta$, the normalized magnitude of smallest change size $\kappa_0$ and the sparsity of the network models $\rho$.

We introduce a novel algorithm namely Consistent Network Change Point Detection, which is shown to detect change points consistently with a minimax optimal testing rate with merely sample average estimators of the graphons. In order to achieve optimal localization rates of the change points, we provide an optional second step, namely Local Refinement, which relies on a stronger condition and which utilizes more advanced graphon estimation techniques. By refining a set of already consistent estimators, our method is computationally efficient. The minimax analysis reveals a phase transition effect based for the problems of network change point testing and localization.