Sequential detection of temporal communities in evolving networks by estrangement confinement

Temporal communities are the result of a consistent partitioning of nodes across multiple snapshots of an evolving network, and they provide insights into how dense clusters in a network emerge, combine, split and decay over time. Reliable detection of temporal communities requires finding a good community partition in a given snapshot while simultaneously ensuring that it bears some similarity to the partition(s) found in the previous snapshot(s). This is a particularly difficult task given the extreme sensitivity of community structure yielded by current methods to changes in the network structure. Motivated by the inertia of inter-node relationships, we present a new measure of partition distance called estrangement, and show that constraining estrangement enables the detection of meaningful temporal communities at various degrees of temporal smoothness in diverse real-world datasets. Estrangement confinement consequently provides a principled approach to uncovering temporal communities in evolving networks. (V. Kawadia and S. Sreenivasan, http://arxiv.org/abs/1203.5126)