Distributed Community Detection via Metastability of the 2-Choices\n Dynamics

Emilio Cruciani, Emanuele Natale, Giacomo Scornavacca

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 non-consensus 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; 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.

Introduction

Community detection—identifying groups of nodes that are more densely connected to each other than to the rest of the network—is a fundamental task in network science. While many "Label Propagation Algorithms" (LPAs) exist as heuristics, they often lack rigorous theoretical guarantees, especially regarding their behavior on non-complete topologies. Most existing theory on simple dynamics focuses on how a network reaches global consensus. However, for community detection, the goal is symmetry breaking: where different parts of the network reach different local consensuses. This paper provides a rigorous theoretical foundation for how simple, local interactions can reveal large-scale structure.

The Clustered Regular Graph Model

To study these dynamics, the authors define a specific mathematical environment: the $(2n, d, b)$-clustered regular graph. This model consists of two communities, each of size $n$. Within each community, nodes are connected in an $a$-regular fashion (where $a = d - b$). The two communities are then linked by a sparse $b$-regular bipartite cut.

The (2n, d, b)-clustered regular graph model consisting of two a-regular communities connected by a b-regular bipartite cut.

The 2-Choices Dynamics

The core of the analysis is the 2-Choices rule. In each synchronous round, every node samples two neighbors at random (with replacement). If both neighbors share the same state (color), the node adopts that state; otherwise, it remains unchanged.

Starting from a random initialization, the authors prove that this non-linear rule acts as an amplifier. It turns tiny initial biases into community-wide consensus. By using spectral analysis and probabilistic concentration tools (like Chernoff bounds), they show that the internal "expansion" of a community helps it reach consensus faster than the "noise" from the neighboring community can disrupt it.

Metastability and Symmetry Breaking

A key contribution of this work is the analysis of metastability. While the system will eventually reach a global consensus (an absorbing state), it stays in a "clustered" state—where the two communities hold different labels—for a super-polynomial amount of time ($n^c$ rounds). In this context, metastability is not a delay but a computational success: the transitory state is exactly what is needed for community detection.

Biological Parallel: The Moran Process

The results offer a "proof of concept" for speciation in evolutionary biology. Dynamics like the Moran process are often used to model how mutations spread. The paper shows that if the probability of adopting a mutation depends super-linearly on its frequency in a neighborhood (as in 2-Choices), species differentiation can occur even with interbreeding (represented by the $b$-regular cut).

The Moran process on a graph, illustrating the selection for reproduction and the replacement of a neighbor.

Key Results and Efficiency

  • Convergence and Stability: The system reaches an "almost-clustered" configuration in $O(\log n)$ rounds and remains stable for at least $n^c$ rounds with high probability.
  • Computational Efficiency: The algorithm achieves a quasi-linear message complexity of $O(n \log n)$, making it highly scalable.
  • Improved Bounds: This randomized approach works on much sparser communities than previous deterministic models, requiring an internal degree of only $a \ge n^{1/2}$ compared to the previous $a \ge n^{3/4}$.

Conclusion

This work provides the first analytical symmetry-breaking analysis for dynamics on non-complete topologies. By framing metastability as a feature rather than a bug, the authors bridge the gap between distributed computing heuristics and biological modeling, offering new insights into how local rules drive global structure.

Summary updated

Abstract

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