Fast Change Point Detection on Dynamic Social Networks

Abstract

A number of real world problems in many domains (e.g. sociology, biology, political science and communication networks) can be modeled as dynamic networks with nodes representing entities of interest and edges representing interactions among the entities at different points in time. A common representation for such models is the snapshot model - where a network is defined at logical time-stamps. An important problem under this model is change point detection. In this work we devise an effective and efficient three-step-approach for detecting change points in dynamic networks under the snapshot model. Our algorithm achieves up to 9X speedup over the state-of-the-art while improving quality on both synthetic and real world networks.

arXiv commentIJCAI'17

References in corpus (5)

• Stochastic blockmodels and community structure in networks
• Community structure and scale-free collections of Erdös-Rényi graphs
• Random graph models for dynamic networks
• Fast Generation of Large Scale Social Networks with Clustering
• Detecting weak changes in dynamic events over networks

Cited by in corpus (6)

• Consistent polynomial-time unseeded graph matching for Lipschitz graphons
• Latent Space Model for Higher-order Networks and Generalized Tensor Decomposition
• Asymptotic distribution-free change-point detection for data with repeated observations
• Constant State of Change: Engagement Inequality in Temporal Dynamic Networks
• Size Agnostic Change Point Detection Framework for Evolving Networks
• Optimality of Graph Scanning Statistic for Online Community Detection