Consistent detection and optimal localization of all detectable change points in piecewise stationary arbitrarily sparse network-sequences
arXiv:2009.02112
Abstract
We consider the offline change point detection and localization problem in the context of piecewise stationary networks, where the observable is a finite sequence of networks. We develop algorithms involving some suitably modified CUSUM statistics based on adaptively trimmed adjacency matrices of the observed networks for both detection and localization of single or multiple change points present in the input data. We provide rigorous theoretical analysis and finite sample estimates evaluating the performance of the proposed methods when the input (finite sequence of networks) is generated from an inhomogeneous random graph model, where the change points are characterized by the change in the mean adjacency matrix. We show that the proposed algorithms can detect (resp. localize) all change points, where the change in the expected adjacency matrix is above the minimax detectability (resp. localizability) threshold, consistently without any a priori assumption about (a) a lower bound for the sparsity of the underlying networks, (b) an upper bound for the number of change points, and (c) a lower bound for the separation between successive change points, provided either the minimum separation between successive pairs of change points or the average degree of the underlying networks goes to infinity arbitrarily slowly. We also prove that the above condition is necessary to have consistency.
24 pages
References in corpus (8)
- A High-Resolution Human Contact Network for Infectious Disease Transmission
- Measuring large-scale social networks with high resolution
- Information dynamics shape the networks of Internet-mediated prostitution
- Inferring the mesoscale structure of layered, edge-valued and time-varying networks
- Detection and localization of change-points in high-dimensional network traffic data
- Anomaly Detection in Time Series of Graphs using Fusion of Graph Invariants
- Change-Point Estimation in High-Dimensional Markov Random Field Models
- Extraction of Temporal Networks from Term Co-occurrences in Online Textual Sources