Optimal change point detection and localization in sparse dynamic networks
From MaRDI portal
Abstract: We study the problem of change point localization in dynamic networks models. We assume that we observe a sequence of independent adjacency matrices of the same size, each corresponding to a realization of an unknown inhomogeneous Bernoulli model. The underlying distribution of the adjacency matrices are piecewise constant, and may change over a subset of the time points, called change points. We are concerned with recovering the unknown number and positions of the change points. In our model setting we allow for all the model parameters to change with the total number of time points, including the network size, the minimal spacing between consecutive change points, the magnitude of the smallest change and the degree of sparsity of the networks. We first identify a region of impossibility in the space of the model parameters such that no change point estimator is provably consistent if the data are generated according to parameters falling in that region. We propose a computationally-simple algorithm for network change point localization, called Network Binary Segmentation, that relies on weighted averages of the adjacency matrices. We show that Network Binary Segmentation is consistent over a range of the model parameters that nearly cover the complement of the impossibility region, thus demonstrating the existence of a phase transition for the problem at hand. Next, we devise a more sophisticated algorithm based on singular value thresholding, called Local Refinement, that delivers more accurate estimates of the change point locations. Under appropriate conditions, Local Refinement guarantees a minimax optimal rate for network change point localization while remaining computationally feasible.
Recommendations
- Optimal nonparametric change point analysis
- Optimal covariance change point localization in high dimensions
- The Bethe Hessian and information theoretic approaches for online change-point detection in network data
- Univariate mean change point detection: penalization, CUSUM and optimality
- Multiple change points detection and clustering in dynamic networks
Cites work
- scientific article; zbMATH DE number 3150484 (Why is no real title available?)
- scientific article; zbMATH DE number 7255138 (Why is no real title available?)
- A MOSUM procedure for the estimation of multiple random change points
- A survey of statistical network models
- Attribute Fusion in a Latent Process Model for Time Series of Graphs
- CONTINUOUS INSPECTION SCHEMES
- Change-point detection in panel data via double CUSUM statistic
- Dynamic network models and graphon estimation
- Emergence of Scaling in Random Networks
- Global spectral clustering in dynamic networks
- High dimensional change point estimation via sparse projection
- Latent space models for dynamic networks
- Locality Statistics for Anomaly Detection in Time Series of Graphs
- Matrix estimation by universal singular value thresholding
- Multiple-Change-Point Detection for High Dimensional Time Series via Sparsified Binary Segmentation
- Narrowest-Over-Threshold Detection of Multiple Change Points and Change-Point-Like Features
- Network cross-validation for determining the number of communities in network data
- Random Dot Product Graph Models for Social Networks
- Rate-optimal graphon estimation
- Spectral clustering in the dynamic stochastic block model
- Statistical clustering of temporal networks through a dynamic stochastic block model
- Time-varying network models
- Topics at the Frontier of Statistics and Network Analysis
- Univariate mean change point detection: penalization, CUSUM and optimality
- Wild binary segmentation for multiple change-point detection
Cited in
(23)- Optimal multiple change-point detection for high-dimensional data
- Optimal change-point detection and localization
- The Bethe Hessian and information theoretic approaches for online change-point detection in network data
- Minimax rates in sparse, high-dimensional change point detection
- On change-point estimation under Sobolev sparsity
- Recent advances on mechanisms of network generation: community, exchangeability, and scale-free properties
- Detection and localization of change-points in high-dimensional network traffic data
- Change-point inference in high-dimensional regression models under temporal dependence
- Change point estimation in high dimensional Markov random-field models
- Multiple change points detection and clustering in dynamic networks
- Localising change points in piecewise polynomials of general degrees
- Optimal covariance change point localization in high dimensions
- Network online change point localization
- Community detection on mixture multilayer networks via regularized tensor decomposition
- changepoints
- Time‐varying β‐model for dynamic directed networks
- Discussion of `Detecting possibly frequent change-points: wild binary segmentation 2 and steepest-drop model selection'
- Changepoint Inference for Erdős–Rényi Random Graphs
- Covariate-assisted matrix completion with multiple structural breaks
- scientific article; zbMATH DE number 7626763 (Why is no real title available?)
- Monitoring Network Changes in Social Media
- Exact tests for offline changepoint detection in multichannel binary and count data with application to networks
- Univariate mean change point detection: penalization, CUSUM and optimality
This page was built for publication: Optimal change point detection and localization in sparse dynamic networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q97726)
