This page is a companion for the paper
Amir Ghasemian, Pan Zhang, Aaron Clauset, and Cristopher Moore, and Leto Peel
Detectability thresholds and optimal algorithms for community structure in dynamic networks, Phys. Rev. X 6, 031005 (2016).
on dynamic community detection.
The detection of communities within a dynamic network is a common means for obtaining a coarse-grained view of a complex system and for investigating its underlying processes. While a number of methods have been proposed in the machine learning and physics literature, we lack a theoretical analysis of their strengths and weaknesses, or of the ultimate limits on when communities can be detected. In this project, we study the fundamental limits of detecting community structure in dynamic networks. Specifically, we analyze the limits of detectability for a dynamic stochastic block model where nodes change their community memberships over time, but where edges are generated independently at each time step. Using the cavity method, we derive a precise detectability threshold as a function of the rate of change and the strength of the communities. Below this sharp threshold, we claim that no efficient algorithm can identify the communities better than chance. We then give two algorithms that are optimal in the sense that they succeed all the way down to this threshold. The first uses belief propagation, which gives asymptotically optimal accuracy, and the second is a fast spectral clustering algorithm, based on linearizing the belief propagation equations. These results (see Fig. below) extend our understanding of the limits of community detection in an important direction, and introduce new mathematical tools for similar extensions to networks with other types of auxiliary information.
The overlap for (top) belief propagation and (bottom) our spectral algorithm. Please refer to the paper, Fig. 3 for more details.
Dynamic Nonbacktracking Spectral Clustering.
If you use this code in your research, please cite it as follows:
@article{ghasemian2016detectability,
title = {Detectability thresholds and optimal algorithms for community structure in dynamic networks},
author = {Ghasemian, Amir and Zhang, Pan and Clauset, Aaron and Moore, Cristopher and Peel, Leto},
journal = {Physical Review X},
volume = {6},
number = {3},
pages = {031005},
year = {2016},
publisher = {APS},
}