An Edge-Centric Approach for Change Point Detection in Dynamic Networks

The graph-theoretic analysis of dynamic networks has attracted much research interests recently. Change point detection is essential to understand the dynamic structure of time evolving networks. This work proposes an edge-centric approach to detect the change points of dynamic networks. In the proposed method, a singular value decomposition (SVD) is performed on a newly defined edge-segment matrix and the decomposition is projected to a lower dimensional latent space. Then the dissimilarity between graph segments is calculated for detecting the change points. The approach applies to directed/undirected and weighted/unweighted dynamic graphs. Experiments are conducted on both a synthetic dataset and the Enron email dataset. Results show that change points of the dynamic networks are effectively detected by the proposed approach.