Detecting Overlapping Temporal Community Structure in Time-Evolving Networks
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Sequential detection of temporal communities by estrangement confinementScientific Reports, 2012
- A Survey of Social-Based Routing in Delay Tolerant Networks: Positive and Negative Social EffectsIEEE Communications Surveys & Tutorials, 2012
- Rank-Sparsity Incoherence for Matrix DecompositionSIAM Journal on Optimization, 2011
- Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix DecompositionsSIAM Review, 2011
- Detection of Overlapping Communities in Dynamical Social Networks2010
- Community Structure in Time-Dependent, Multiscale, and Multiplex NetworksScience, 2010
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm MinimizationSIAM Review, 2010
- Modeling Spatial and Temporal Dependencies of User Mobility in Wireless Mobile NetworksIEEE/ACM Transactions on Networking, 2009
- Modularity-maximizing graph communities via mathematical programmingThe European Physical Journal B, 2008
- Reality mining: sensing complex social systemsPersonal and Ubiquitous Computing, 2005