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
- 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
- Change point estimation in a dynamic stochastic block model
- Change-point detection in panel data via double CUSUM statistic
- CONTINUOUS INSPECTION SCHEMES
- 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
- scientific article; zbMATH DE number 3150484 (Why is no real title available?)
- 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
(47)- Multiple change points detection and clustering in dynamic networks
- Minimax rates in sparse, high-dimensional change point detection
- Community detection on mixture multilayer networks via regularized tensor decomposition
- The Bethe Hessian and information theoretic approaches for online change-point detection in network data
- Discussion of `Detecting possibly frequent change-points: wild binary segmentation 2 and steepest-drop model selection'
- On change-point estimation under Sobolev sparsity
- Univariate mean change point detection: penalization, CUSUM and optimality
- Detection and localization of change-points in high-dimensional network traffic data
- Changepoint Inference for Erdős–Rényi Random Graphs
- Change point estimation in a dynamic stochastic block model
- scientific article; zbMATH DE number 7626763 (Why is no real title available?)
- Exact tests for offline changepoint detection in multichannel binary and count data with application to networks
- Change point estimation in high dimensional Markov random-field models
- Covariate-assisted matrix completion with multiple structural breaks
- Time‐varying β‐model for dynamic directed networks
- Optimal multiple change-point detection for high-dimensional data
- Optimal change-point detection and localization
- Network online change point localization
- Recent advances on mechanisms of network generation: community, exchangeability, and scale-free properties
- Change-point inference in high-dimensional regression models under temporal dependence
- Monitoring Network Changes in Social Media
- Change point estimation for a stochastic heat equation
- Multilayer random dot product graphs: estimation and online change point detection
- On the impossibility of detecting a late change-point in the preferential attachment random graph model
- Aggregate spectral clustering for community detection in multi-layer popularity adjusted block model
- Multiple network embedding for anomaly detection in time series of graphs
- Change Point Detection in Dynamic Networks via Regularized Tensor Decomposition
- Estimating time-varying networks for high-dimensional time series
- Optimal Network Pairwise Comparison
- Euclidean Mirrors and Dynamics in Network Time Series
- On the tightness of graph-based statistics
- Robust change point detection for high-dimensional linear models with tolerance for outliers and heavy tails
- Bootstrapping networks with latent space structure
- Improving power by conditioning on less in post-selection inference for changepoints
- Online network change point detection with missing values and temporal dependence
- Change-Point Detection for Object-Valued Time Series
- Random interval distillation for detection of change-points in Markov chain Bernoulli networks
- On Optimal Tracking of Structural Changes in Time-Varying Networks
- Detecting a late changepoint in the preferential attachment model
- Dynamic clustering for heterophilic stochastic block models with time-varying node memberships
- Joint estimation of edge probabilities for multi-layer networks via neighborhood smoothing
- Detection and estimation of vertexwise latent position shifts across networks
- A note on the Cox-model based partial likelihood for change-point detection in a covariate
- Adaptive inference in a dynamic nonparametric -model for networks
- Localising change points in piecewise polynomials of general degrees
- Optimal covariance change point localization in high dimensions
- changepoints
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)
