Change-point detection in dynamic networks via graphon estimation

Abstract

We propose a general approach for change-point detection in dynamic networks. The proposed method is model-free and covers a wide range of dynamic networks. The key idea behind our approach is to effectively utilize the network structure in designing change-point detection algorithms. This is done via an initial step of graphon estimation, where we propose a modified neighborhood smoothing~(MNBS) algorithm for estimating the link probability matrices of a dynamic network. Based on the initial graphon estimation, we then develop a screening and thresholding algorithm for multiple change-point detection in dynamic networks. The convergence rate and consistency for the change-point detection procedure are derived as well as those for MNBS. When the number of nodes is large~(e.g., exceeds the number of temporal points), our approach yields a faster convergence rate in detecting change-points comparing with an algorithm that simply employs averaged information of the dynamic network across time. Numerical experiments demonstrate robust performance of the proposed algorithm for change-point detection under various types of dynamic networks, and superior performance over existing methods is observed. A real data example is provided to illustrate the effectiveness and practical impact of the procedure.

References in corpus (7)

• Stochastic blockmodels and community structure in networks
• Matrix estimation by Universal Singular Value Thresholding
• An efficient and principled method for detecting communities in networks
• Rate-optimal graphon estimation
• Nonparametric maximum likelihood approach to multiple change-point problems
• Optimal Change Point Detection and Localization in Sparse Dynamic Networks
• Spectral Clustering for Multiple Sparse Networks: I

Cited by in corpus (10)

• Estimation of subgraph density in noisy networks
• Statistically and Computationally Efficient Change Point Localization in Regression Settings
• Data segmentation algorithms: Univariate mean change and beyond
• A review on minimax rates in change point detection and localisation
• Change point localization in dependent dynamic nonparametric random dot product graphs
• Joint Network Topology Inference via a Shared Graphon Model
• Change-Point Detection in Dynamic Networks with Missing Links
• Hypothesis testing for populations of networks
• Adaptive Inference for Change Points in High-Dimensional Data
• Training Graph Neural Networks by Graphon Estimation