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
In network science, identifying communities—groups of nodes more densely connected to each other than to the rest of the network—is a fundamental task. While heuristics like Label Propagation Algorithms (LPAs) are widely used, they often lack rigorous theoretical guarantees on non-complete topologies. Most research on network dynamics has focused on how systems reach global consensus. This paper addresses the inverse: can simple, local rules lead to stable non-consensus, where communities "agree to disagree"? We provide the first theoretical proof that a decentralized "2-Choices" dynamics can effectively perform community detection by reaching a metastable state where communities maintain internal consensus on different labels.
The Clustered Regular Graph Model
The authors analyze the dynamics on a $(2n, d, b)$-clustered regular graph. This model consists of two communities of size $n$. Every node has $d$ total neighbors, with $a$ neighbors in its own community and $b$ neighbors in the other ($d = a+b$). This structure serves as a benchmark for community detection theory, providing a controlled environment for mathematical proof.
2-Choices Dynamics and Symmetry Breaking
The 2-Choices dynamics is a quadratic process: in each discrete time step, every node samples two neighbors at random. If both neighbors share the same state, the node adopts that state; otherwise, it remains unchanged. Unlike linear models like the Voter dynamics, which drift aimlessly, the non-linearity of the 2-Choices rule acts as a "drift" that pushes communities toward internal consensus much faster than inter-community noise can disrupt it.
The analysis focuses on symmetry breaking—how small random fluctuations at initialization are amplified into large-scale structural patterns. The authors prove that from a random binary initialization, the system reaches an "almost-clustered" configuration in just $O(\log n)$ rounds with constant probability.
Metastability and Key Results
A critical insight of this work is that the "long-term" behavior of such systems (global consensus) is often less interesting than the metastable transitory state. Once the system reaches a clustered state, it remains there for a super-polynomial amount of time ($n^c$ rounds), making it practically useful for computational or biological processes.
Key results include:
- Efficiency: The dynamics act as a distributed community detection algorithm with quasi-linear message complexity ($O(n \log n)$).
- Sparsity: The analysis holds for sparse communities where node degrees are as low as $n^{1/2}$, significantly lower than the $n^{3/4}$ required by previous theoretical models.
Biological Implications: Sympatric Speciation
The paper provides a mathematical "proof of concept" for sympatric speciation—the evolution of new species from a single ancestor within the same geographic region. It demonstrates how simple local interactions and a clustered social structure can lead to long-lived genetic divergence, modeled through processes similar to the Moran process.
Conclusion
This work bridges the gap between simple local dynamics and global community structure. While currently restricted to regular topologies and sparse cuts, it establishes a theoretical foundation for understanding how non-linear update rules can reveal hidden network structures and drive biological differentiation. Future research will explore generalizations to non-regular graphs and denser inter-community connections.
Summary updated