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

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.

Introduction

Real-world networks—such as social interactions, the World Wide Web, or international trade systems—are dynamic entities that evolve over time. Analyzing these "time series" of networks presents two primary challenges: identifying clusters of nodes (community detection) and pinpointing the moments when the network's organizational structure shifts (change-point detection). Traditionally, these problems have been addressed in isolation, often requiring researchers to pre-specify the number of change points or struggling with networks where the node set varies over time. This paper introduces a unified framework that simultaneously identifies change points and community structures, leveraging the Minimum Description Length (MDL) principle for automated parameter selection.

Methodology

The proposed approach integrates community detection and change-point identification into a single optimization problem. By doing so, it avoids the error propagation common in sequential methods.

The Minimum Description Length (MDL) Principle

At the heart of the methodology is the MDL principle, which treats model selection as a data compression problem. The optimal model is defined as the one that provides the shortest description of the data. This framework naturally balances model fit against complexity, effectively preventing over-fitting without the need for manually tuned penalty parameters.

Model Components

  1. Stochastic Block Model (SBM): The SBM serves as the underlying statistical engine, where edge probabilities between nodes are determined by their community memberships.
  2. Top-Down Community Search: Instead of traditional bottom-up clustering, the authors employ a recursive splitting algorithm. Communities are divided only if the split reduces the total MDL, ensuring a parsimonious representation.
  3. Change-Point Screening: To maintain computational efficiency, a screening process identifies candidate change points by measuring structural "jumps" between consecutive network snapshots.

Experimental Validation

The framework was tested using both synthetic simulations and real-world data:

  • Synthetic Data: Six simulation settings evaluated the algorithm's performance against noise, sparsity, and edge correlation in networks of 280 to 400 nodes over 30 time steps.
  • World Trade Web (WTW): The algorithm analyzed the International Trade Network (196 countries, 1948–2000) to detect major historical and economic shifts.

Results and Discussion

The MDL-based approach demonstrated superior accuracy compared to existing methods like Multi-Step and SCOUT. In synthetic tests, while competing methods often "hallucinated" extra change points (over-segmentation), the MDL approach remained precise.

Comparison of change-point detection accuracy between MDL, Multi-Step, and SCOUT methods.

As shown in the figure above, the MDL method identifies the true change points (indicated by red dashed lines) with high frequency and minimal noise. In contrast, methods like Multi-Step and SCOUT (with BIC) exhibit significant over-segmentation, identifying numerous false positives across the time series.

Performance of MDL versus competing methods in an alternative simulation scenario.

In dense network simulations, the proposed method achieved a Normalized Mutual Information (NMI) of 1.0, indicating perfect community recovery. On the WTW dataset, the algorithm identified five major change points (1959, 1965, 1974, 1980, and 1990) that align with significant global events, such as African decolonization and South American economic integration. The beauty of the MDL approach is its ability to handle "node churn"—nodes joining or leaving the network—without losing the consistency of the detected community structures.

Conclusion and Future Work

This research provides a robust, automated tool for analyzing evolving networks. By handling varying node sets and avoiding manual parameter tuning, the MDL framework offers a significant advancement over isolated detection methods. Future work will focus on incorporating Markov structures to model edge persistence, further refining the model's accuracy for social and biological networks where relationships exhibit short-term stability.

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},
}
Figure