Distributed Community Detection via Metastability of the 2-Choices Dynamics

Abstract : We investigate the behavior of a simple majority dynamics on networksof agents whose interaction topology exhibits a community structure. Byleveraging recent advancements in the analysis of dynamics, we prove that,when the states of the nodes are randomly initialized, the system rapidlyand stably converges to a configuration in which the communities maintaininternal consensus on different states. This is the first analytical resulton the behavior of dynamics for non-consensus problems on non-completetopologies, based on the first symmetry-breaking analysis in such setting.Our result has several implications in different contexts in which dy-namics are adopted for computational and biological modeling purposes.In the context ofLabel Propagation Algorithms, a class of widely usedheuristics forcommunity detection, it represents the first theoretical re-sult on the behavior of a distributed label propagation algorithm withquasi-linear message complexity. In the context ofevolutionary biology,dynamics such as the Moran process have been used to model the spreadof mutations in genetic populations [LHN05]; our result shows that, whenthe probability of adoption of a given mutation by a node of the evolu-tionary graph depends super-linearly on the frequency of the mutationin the neighborhood of the node and the underlying evolutionary graphexhibits a community structure, there is a non-negligible probability for apecies differentiation to occur.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

Littérature citée [38 références]  Voir  Masquer  Télécharger

Contributeur : Emanuele Natale <>
Soumis le : jeudi 11 juillet 2019 - 17:29:18
Dernière modification le : jeudi 12 décembre 2019 - 15:08:52


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-02002462, version 1
  • ARXIV : 1805.01406



Emilio Cruciani, Emanuele Natale, Giacomo Scornavacca. Distributed Community Detection via Metastability of the 2-Choices Dynamics. AAAI 2019 - 33th AAAI Conference Association for the Advancement of Artificial Intelligence, Jan 2019, Honolulu, United States. ⟨hal-02002462⟩



Consultations de la notice


Téléchargements de fichiers