TY - JOUR AU - Cruciani, Emilio AU - Natale, Emanuele AU - Scornavacca, Giacomo PY - 2019/07/17 Y2 - 2024/03/29 TI - Distributed Community Detection via Metastability of the 2-Choices Dynamics JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 33 IS - 01 SE - AAAI Technical Track: Multiagent Systems DO - 10.1609/aaai.v33i01.33016046 UR - https://ojs.aaai.org/index.php/AAAI/article/view/4560 SP - 6046-6053 AB - <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> ER -