Detecting Overlapping Temporal Community Structure in Time-Evolving Networks
This work addresses the challenge of understanding complex networks by revealing stable, overlapping communities over time, which is incremental as it builds on existing community detection methods.
The authors tackled the problem of detecting overlapping temporal community structure in dynamic networks by proposing a method that maximizes a quality function with a temporal smoothness constraint, and they provided theoretical guarantees and experimental results on real and synthetic networks.
We present a principled approach for detecting overlapping temporal community structure in dynamic networks. Our method is based on the following framework: find the overlapping temporal community structure that maximizes a quality function associated with each snapshot of the network subject to a temporal smoothness constraint. A novel quality function and a smoothness constraint are proposed to handle overlaps, and a new convex relaxation is used to solve the resulting combinatorial optimization problem. We provide theoretical guarantees as well as experimental results that reveal community structure in real and synthetic networks. Our main insight is that certain structures can be identified only when temporal correlation is considered and when communities are allowed to overlap. In general, discovering such overlapping temporal community structure can enhance our understanding of real-world complex networks by revealing the underlying stability behind their seemingly chaotic evolution.