Distributed Community Detection via Metastability of the 2-Choices Dynamics

Emilio Cruciani, Emanuele Natale, Giacomo Scornavacca

Introduction

Community detection is a cornerstone of network science, focusing on identifying clusters of nodes with high internal connectivity. While Label Propagation Algorithms (LPAs) are widely used for this task due to their simplicity and speed, they often lack rigorous theoretical guarantees, especially on sparse graphs. This paper bridges that gap by providing the first rigorous analysis of the 2-Choices dynamics—a local voting rule—on structured networks. The authors demonstrate that this simple process can effectively reveal community structures by reaching a "metastable" state where different clusters achieve internal consensus on distinct labels.

The 2-Choices Dynamics

The 2-Choices dynamics is an elegantly simple local interaction rule. In each discrete time step, every node in the network samples two of its neighbors at random (with replacement). If both sampled neighbors share the same state (or "color"), the node adopts that state. If the neighbors differ, the node retains its current state. This rule acts as a form of "implicit sparsification," as nodes only ever process information from two neighbors regardless of their actual degree, leading to a quasi-linear message complexity of $O(n \log n)$.

The Clustered Regular Graph Model

To provide a rigorous analysis, the authors utilize a specific synthetic benchmark: the $(2n, d, b)$-clustered regular graph. This model consists of two communities, each of size $n$. Every node has a total degree $d$, with $a$ edges connecting to nodes within its own community and $b$ edges connecting to the "other" community (where $d = a + b$).

The (2n, d, b)-clustered regular graph model used for theoretical analysis.

The analysis assumes these communities are "good expanders" internally, characterized by their spectral properties. The goal is to show that the 2-Choices dynamics can distinguish these two communities even when the "cut" (the number of inter-community edges $b$) is relatively sparse.

Metastability and Convergence

The core contribution of the paper is the discovery of a metastable phase. While the system will eventually reach a global consensus (where all nodes share the same color), there exists a significant time window where the communities remain distinct.

A sequence of local interactions leading to population state changes, mirroring evolutionary dynamics.

Key findings include:

  • Rapid Symmetry Breaking: Starting from a random initial state, the system breaks symmetry in just $O(\log n)$ rounds. Random noise is sufficient to nudge the two communities toward different colors.
  • Long-Term Stability: Once an "almost-clustered" state is reached—where Community A is predominantly one color and Community B is another—it persists for a polynomial number of rounds ($n^c$). This duration is more than sufficient for practical applications to identify the network's clusters.
  • High Probability Success: While a single run has a constant probability of success, running $O(\log n)$ independent instances in parallel ensures the community structure is revealed with high probability.

Conclusion and Biological Implications

Beyond network science, this work offers a "proof of concept" for evolutionary biology. It provides a mathematical framework for how speciation—the divergence of biological populations—can emerge naturally from local interaction rules and physical topology. Future work aims to relax the "regularity" constraint of the graphs and extend the analysis to multi-community and multi-color scenarios, further unifying the theory of community-detecting dynamics.

Summary updated

Abstract

We investigate the behavior of a simple majority dynamics on networks of agents whose interaction topology exhibits a community structure. By leveraging recent advancements in the analysis of dynamics, we prove that, when the states of the nodes are randomly initialized, the system rapidly and stably converges to a configuration in which the communities maintain internal consensus on different states. This is the first analytical result on the behavior of dynamics for nonconsensus problems on non-complete topologies, based on the first symmetry-breaking analysis in such setting.Our result has several implications in different contexts in which dynamics are adopted for computational and biological modeling purposes. In the context of Label Propagation Algorithms, a class of widely used heuristics for community detection, it represents the first theoretical result on the behavior of a distributed label propagation algorithm with quasi-linear message complexity. In the context of evolutionary biology, dynamics such as the Moran process have been used to model the spread of mutations in genetic populations (Lieberman, Hauert, and Nowak 2005); our result shows that, when the probability of adoption of a given mutation by a node of the evolutionary graph depends super-linearly on the frequency of the mutation in the neighborhood of the node and the underlying evolutionary graph exhibits a community structure, there is a non-negligible probability for species differentiation to occur.
BibTeX
@inproceedings{cruciani2019distributed,
  author = {Emilio Cruciani and Emanuele Natale and Giacomo Scornavacca},
  title = {{Distributed Community Detection via Metastability of the 2-Choices Dynamics}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33016046},
}
Figure