Detecting Change Points in the Large-Scale Structure of Evolving Networks

Authors

  • Leto Peel University of Colorado at Boulder
  • Aaron Clauset University of Colorado at Boulder

DOI:

https://doi.org/10.1609/aaai.v29i1.9574

Keywords:

dynamic networks, change-point detection, generative models, model comparison

Abstract

Interactions among people or objects are often dynamic in nature and can be represented as a sequence of networks, each providing a snapshot of the interactions over a brief period of time. An important task in analyzing such evolving networks is change-point detection, in which we both identify the times at which the large-scale pattern of interactions changes fundamentally and quantify how large and what kind of change occurred. Here, we formalize for the first time the network change-point detection problem within an online probabilistic learning framework and introduce a method that can reliably solve it. This method combines a generalized hierarchical random graph model with a Bayesian hypothesis test to quantitatively determine if, when, and precisely how a change point has occurred. We analyze the detectability of our method using synthetic data with known change points of different types and magnitudes, and show that this method is more accurate than several previously used alternatives. Applied to two high-resolution evolving social networks, this method identifies a sequence of change points that align with known external ``shocks'' to these networks.

Downloads

Published

2015-02-21

How to Cite

Peel, L., & Clauset, A. (2015). Detecting Change Points in the Large-Scale Structure of Evolving Networks. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9574

Issue

Section

Main Track: Novel Machine Learning Algorithms