Detectability Thresholds and Optimal Algorithms for Community Structure in Dynamic Networks

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. Here, 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 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.

Popular Summary

Detecting communities within the networks that characterize complex social, biological, and technological systems is a crucial step in understanding how their structure shapes their function. However, many such networks are dynamic, with nodes changing their connections and affiliations over time in complicated ways. This situation makes community detection more challenging, but correlations across time provide a means to circumvent this issue. Here, we derive a precise mathematical limit on our ability to recover the underlying community structure in a dynamic network, which depends only on the strength of the hidden communities and the rate at which nodes change their community membership.

While a number of models and algorithms have been proposed for dynamic community detection, up to now there has been no theory about the limits of these algorithms. In this study, we use powerful tools from both statistical physics and Bayesian probability to show that a phase transition exists in the detectability of dynamic communities, and we describe two new algorithms that are optimal in the sense that they succeed all the way down to this threshold. The first algorithm is based on belief propagation, known in physics as the cavity method, and the second is a fast spectral clustering algorithm.

We expect that the techniques used to obtain these results can likely be used to derive similar limits and optimal algorithms for other kinds of generalized networks, such as multiplex networks, networks with edge weights, or networks with node attributes. Additionally, our optimal algorithms can be applied to recover dynamic communities in a wide variety of practical settings.

Figure 1

A schematic representation of belief propagation messages [see Eqs. (5) and (6)] being passed along spatial and temporal edges in the spatiotemporal graph.

Figure 2

Overlap as a function of $\epsilon$ for different values of $\eta$ (given in the legend). For each $\eta$, the critical value of $\epsilon$ for $T=40$ is shown as a vertical line in the lower panel, and the hatched area shows the region of detectability for static networks [14, 15]. Each data point is the average of 100 instances, with $n=512$, $T=40$, $k=2$ groups, and average degree $c=16$.

Figure 3

The overlap for (top) belief propagation and (bottom) our spectral algorithm. The detectability transition in Eq. (10) for $T=\infty$ is shown as a solid line. The dashed curve shows the detectability transition for $T=40$; the magenta curve shows the transition for $T=\infty$. Each point shows the average over 100 dynamic networks generated by our model with $n=512$, $T=40$, $k=2$ groups, and average degree $c=16$. The overlap here is calculated by averaging the maximum overlap at each time slot over all permutations. This maximization step implies that the expected overlap in the undetectable region is $O(n^{-1/2})$, and this produces a small deviation away from $\text{overlap}=0$ in our numerical experiments.

Figure 4

The convergence time of belief propagation diverges as we approach the transition. This heat map shows the number of iterations it takes BP to converge to a fixed point, with the same parameters as in Fig. 3. As before, the dashed curve shows the detectability transition for $T=40$, and the magenta curve shows the transition for $T=\infty$.