@article{Cruciani_Natale_Scornavacca_2019, title={Distributed Community Detection via Metastability of the 2-Choices Dynamics}, volume={33}, url={https://ojs.aaai.org/index.php/AAAI/article/view/4560}, DOI={10.1609/aaai.v33i01.33016046}, abstractNote={<p>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.</p><p>Our result has several implications in different contexts in which dynamics are adopted for computational and biological modeling purposes. In the context of <em>Label Propagation Algorithms</em>, a class of widely used heuristics for <em>community detection</em>, it represents the first theoretical result on the behavior of a distributed label propagation algorithm with quasi-linear message complexity. In the context of <em>evolutionary biology</em>, 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 <em>species differentiation</em> to occur.</p>}, number={01}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Cruciani, Emilio and Natale, Emanuele and Scornavacca, Giacomo}, year={2019}, month={Jul.}, pages={6046-6053} }