Segmenting Dynamic Network Data

Rex C. Y. Cheung, Alexander Aue, 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—ranging from social interactions and global trade systems to biological pathways—are dynamic entities that evolve over time. Analyzing these "time series" of networks presents two fundamental challenges: community detection and change-point detection. Community detection involves identifying clusters of nodes with dense internal connections, while change-point detection seeks the specific moments when the network's underlying structural rules shift.

Existing methodologies often address these problems in isolation or rely on rigid assumptions, such as a fixed number of communities across all time steps. This paper introduces a unified framework that simultaneously identifies when a network changes and how its community structure is reorganized, providing a statistically principled approach to segmenting dynamic networks without needing to pre-specify the number of communities or change points.

Methodology

The proposed framework is built upon the Minimum Description Length (MDL) principle, which treats statistical modeling as a data compression problem. The optimal model is defined as the one that achieves the shortest total description of the data.

Core Components

  • Stochastic Block Model (SBM): The SBM serves as the underlying statistical engine, where edge probabilities are determined by community assignments.
  • Two-Part MDL Criterion: The objective function minimizes the sum of the code length required to describe the model (change points and community assignments) and the code length of the data given that model (log-likelihood).
  • Search Algorithms: To ensure computational feasibility, the authors employ a recursive top-down splitting approach for community detection and a screening process for change points. The screening process utilizes the normalized 1-norm distance between consecutive adjacency matrices to identify candidate change points, followed by a greedy top-down search to finalize segments.

Results and Discussion

The methodology was validated through extensive synthetic simulations and an analysis of the World Trade Web (WTW) dataset, which tracks international trade between 196 countries from 1948 to 2000.

Synthetic Performance

In numerical experiments, the MDL approach demonstrated superior accuracy compared to existing methods like "Multi-Step" and "SCOUT." A key advantage of the MDL criterion is its natural penalty for model complexity, which prevents the detection of spurious change points caused by minor fluctuations in edge density.

MDL Change-Point Detection Accuracy

As shown in Figure 1, the MDL method produces sharp, clear signals at the true change-point locations. In contrast, other methods often "hallucinate" structural shifts. For instance, Figure 2 illustrates the performance of the SCOUT method (with BIC), which identifies a high frequency of change points across the entire time series, leading to significant over-segmentation and loss of structural clarity.

Spurious Detections in SCOUT (with BIC)

Real-World Application: World Trade Web

When applied to 53 years of global trade data, the model identified five major change points (1959, 1965, 1974, 1980, and 1990). These segments correspond to significant historical events, such as the decolonization of Africa in the 1960s and the rapid globalization of the 1990s, where South American nations integrated into the primary global trade community. The model's flexibility allows the number of communities to change between segments, capturing how groups merge or splinter over decades.

Conclusion

The MDL-based framework offers a robust and flexible solution for the simultaneous detection of change points and community structures in dynamic networks. By allowing the number of communities to vary between segments and utilizing a principled compression-based objective, it avoids the pitfalls of over-fitting and rigid parameterization. Future research will focus on relaxing the independence assumption between time steps by incorporating temporal dependencies, such as Markov structures, and extending the framework to handle weighted and directed network data.

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{cheung2020segmenting,
  author = {Rex C. Y. Cheung and Alexander Aue and Thomas C. M. Lee},
  title = {{Segmenting Dynamic Network Data}},
  journal = {IEEE Trans. Signal Inf. Process. Over Networks},
  year = {2020},
  url = {https://openreview.net/forum?id=VWPXBToU6N6},
}
Figure