Contact: Tijana Milenkovic, tmilenko AT nd DOT edu

Introduction: Many evolving complex systems can be modeled via dynamic networks. An important problem in dynamic network research is community detection, which identifies groups of topologically related nodes. Typically, this problem is approached by assuming either that each time point has a distinct community organization or that all time points share one community organization. In reality, the truth likely lies between these two extremes, since some time periods can have community organization that evolves while others can have community organization that stays the same. To find the compromise, we consider community detection in the context of the problem of segment detection, which identifies contiguous time periods with consistent network structure. Consequently, we formulate a combined problem of segment community detection (SCD), which simultaneously partitions the network into contiguous time segments with consistent community organization and finds this community organization for each segment. To solve SCD, we introduce SCOUT, an optimization framework that explicitly considers both segmentation quality and partition quality. SCOUT addresses limitations of existing methods that can be adapted to solve SCD, which typically consider only one of segmentation quality or partition quality. In a thorough evaluation, SCOUT outperforms the existing methods in terms of both accuracy and computational complexity.

Reference: Yuriy Hulovatyy and Tijana Milenkovic. "SCOUT: simultaneous time segmentation and community detection in dynamic networks", Nature Scientific Reports, 6, Article number: 37557, DOI:10.1038/srep37557, 2016.

Software: Implementation (executable) of SCOUT is available here. The source code for SCOUT is available here.

Data: Synthetic networks from our paper are available here. Here are links to real-world networks from our paper: Hypertext, AMD HOPE, High School, Reality Mining, Enron, Senate, and aging data used for the case study.