Simultaneous Detection of Multiple Change Points and Community Structures in Time Series of Networks

Rex C. Y. Cheung, Alexander Aue, Seungyong Hwang, Thomas C. M. Lee

TL;DR

This paper introduces a unified framework for simultaneously identifying change points (when a network's structure shifts) and community structures (how nodes cluster) in time-varying networks. By leveraging the Minimum Description Length (MDL) principle, the authors create a model-selection objective that automatically balances model complexity with data fit, outperforming existing methods in both accuracy and robustness across synthetic and real-world trade data.

What Problem Does This Paper Address?

Many real-world systems—from social media interactions to international trade—are best represented as networks that evolve over time. Researchers typically want to know two things:

  1. Community Detection: Which nodes belong together in tightly-knit groups?
  2. Change-Point Detection: At what specific moments does the overall organizational structure of the network fundamentally change?

The challenge is that these two problems are deeply intertwined. You can't accurately find a change point without knowing the underlying community structure, and you can't define stable communities if the network is in the middle of a structural shift. Most existing tools tackle these separately or make restrictive assumptions (e.g., the number of communities must stay constant). This paper addresses the need for a robust, simultaneous approach that handles varying community counts and "noisy" temporal data.

Methods

The authors propose a methodology based on two primary pillars:

  • The Stochastic Block Model (SBM): This is the underlying statistical model. It assumes that the probability of an edge existing between two nodes depends solely on which communities those nodes belong to.
  • Minimum Description Length (MDL) Principle: This is the "secret sauce" for model selection. MDL views statistical modeling as data compression. The "best" model is the one that results in the shortest combined description of the model itself and the data given that model. This naturally penalizes overly complex models (too many change points or communities) without requiring manual hyperparameter tuning.

The Algorithms

  1. Community Detection (Top-Down): Unlike the popular "bottom-up" Louvain method, the authors use a recursive splitting approach. They start with one group, split it, and only keep the split if the MDL value decreases (indicating better compression).
  2. Change-Point Detection (Screening + Search): To avoid the computational nightmare of checking every possible combination of time points, they use a screening process based on the normalized distance between consecutive adjacency matrices. They then perform a top-down search on these candidates, followed by a merging step to prune false positives.

Datasets

  • Synthetic Data: The authors tested the model on six distinct simulation settings. These varied in network density (dense vs. sparse), whether edge probabilities were correlated over time, and whether link probabilities shifted slightly within a "stable" segment.
  • World Trade Web (WTW): Also known as the International Trade Network, this dataset tracks trade flows between 196 countries from 1948 to 2000. The authors treated this as an undirected, unweighted network to identify major shifts in global economic organization.

Key Insights and Ideas

  • Simultaneity is Key: By optimizing for change points and communities at once, the model avoids the "error propagation" that happens when you try to solve one before the other.
  • Robustness to "Jitter": A major insight is the model's ability to ignore minor fluctuations in edge probabilities that don't change the fundamental community assignments. In simulations (Settings 2 and 5), the MDL approach correctly identified segments even when the "noise" within a segment was high.
  • MDL as a Natural Regularizer: The MDL objective function (Equation 6 in the paper) includes terms for the number of change points, the number of communities, and the community assignments. This prevents the model from "over-segmenting" the timeline.

Key Results

  • Superior Accuracy: In synthetic tests, the MDL-based method consistently located true change points more accurately than competitors like Multi-Step and SCOUT, which often produced many spurious change points.
  • Community Precision: In dense network simulations, the method achieved a Normalized Mutual Information (NMI) of 1.00, indicating perfect recovery of the ground-truth community structures.
  • Real-World Relevance: On the World Trade Web data, the model detected five change points (1959, 1965, 1974, 1980, and 1990). These dates correspond to major historical milestones:
  • 1959/1965: The decolonization of Africa and the subsequent entry of new nations into global trade.
  • 1974/1980: Shifts in Southeast Asian trade and the reintegration of Indonesia into the global community.
  • 1990: The end of the Cold War and the acceleration of globalization, particularly in South America.

Limitations and Future Work

  • Temporal Independence: The current model assumes that network snapshots are independent within a segment. The authors acknowledge that in reality, an edge at time $t$ is often highly correlated with an edge at $t-1$. They suggest incorporating a Markov structure in future iterations to model this dependency.
  • Computational Load: While the screening process speeds up the search, analyzing extremely long time series with thousands of nodes remains computationally intensive.
  • Graph Complexity: The current work focuses on undirected and unweighted graphs. Extending this to directed or weighted networks (where the "strength" of a trade relationship matters) is a logical next step.

Summary updated

Abstract

In many complex systems, networks and graphs arise in a natural manner. Often, time evolving behavior can be easily found and modeled using time-series methodology. Amongst others, two common research problems in network analysis are community detection and change-point detection. Community detection aims at finding specific sub-structures within the networks, and change-point detection tries to find the time points at which sub-structures change. We propose a novel methodology to detect both community structures and change points simultaneously based on a model selection framework in which the Minimum Description Length Principle (MDL) is utilized as minimizing objective criterion. The promising practical performance of the proposed method is illustrated via a series of numerical experiments and real data analysis.
BibTeX
@article{cheung2020simultaneous,
  author = {Rex C. Y. Cheung and Alexander Aue and Seungyong Hwang and Thomas C. M. Lee},
  title = {{Simultaneous Detection of Multiple Change Points and Community Structures in Time Series of Networks}},
  journal = {IEEE Trans. Signal Inf. Process. Over Networks},
  year = {2020},
  url = {https://openreview.net/forum?id=VWPXBToU6N6},
}

Loading related content...

Figure