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.
@cite_5 proposes a novel estimator for estimating the link probability matrix @math of an undirected network by neighborhood smoothing (NBS). The essential idea consists of the following: Given an adjacent matrix @math , the link probability @math between node @math and @math is estimated by where @math is a certain set of neighboring nodes of node @math , which consists of the nodes that exhibit similar connection patterns as node @math . With a well-designed neighborhood adaptive to the network structure, the smoothing achieves an accurate estimation for @math . NBS in @cite_5 estimates @math with a single adjacency matrix @math . For a dynamic network, a sequence of adjacency matrices @math is available, which provides extra information of the network. By aggregating information from repeated observations across time, in Section , we propose a modified NBS by carefully shrinking the neighborhood size, which yields a better convergence rate in estimating the link probability matrix @math and thus an improved rate in change-point detection.
@cite_5
2962719258
The estimation of probabilities of network edges from the observed adjacency matrix has important applications to predicting missing links and network denoising. It has usually been addressed by estimating the graphon, a function that determines the matrix of edge probabilities, but this is ill-defined without strong assumptions on the network structure. Here we propose a novel computationally efficient method, based on neighborhood smoothing to estimate the expectation of the adjacency matrix directly, without making the structural assumptions that graphon estimation requires. The neighborhood smoothing method requires little tuning, has a competitive mean-squared error rate, and outperforms many benchmark methods on link prediction in simulated and real networks.