Optimal change point detection and localization in sparse dynamic networks (Q97726)

The study refers to a dynamic network model consisting of a sequence (A(t))\(^T_{t=1}\) of \(n\times n\) adjacency matrices of independent inhomogeneous Bernoulli networks with means (\(\theta\)(t))\(^T_{t=1}\) that satisfy a set of conditions, summarized as Assumption~1. The model is described by the parameters: \(\Delta\), \(k_0\), \(n\) and \(\rho\). When \(T\) grows unbounded, the parameters will change as functions of \(T\) and the number \(K\) of change points will change, too. One is concerned with the problem of estimating the number and location of the change points, based on one observation \((A(1),\dots, A(T))\) of adjacency matrices satisfying Assumption~1. The feasibility of a consistent estimation of the change point location is studied in the second section. One develops an algorithm called network binary segmentation, NBS, which is able to localize multiple change points consistently. In the third section, one shows that under stronger conditions on model and scaling, a two-step procedure can achieve a minimax optimal localization rate. The procedure applies first NBS and then a local refinement procedure, the LR algorithm. The authors prove that the LR procedure indeed improves localization rates, it is nearly minimax optimal. New assumptions are introduced. Simulation results are presented in the fourth section. Proofs of the main results are presented in the Appendix part. Some details, discussion and technical elements can be found in the supplementary material to this article, \url{doi:10.1214/20-AOS1953SUPP;.pdf}.