  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 [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.
