  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.
