Distributed Community Detection via Metastability of the 2-Choices Dynamics

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

https://hal.archives-ouvertes.fr/hal-02002462
Contributeur : Emanuele Natale <>
Soumis le : jeudi 11 juillet 2019 - 17:29:18
Dernière modification le : samedi 20 juillet 2019 - 15:58:01

Fichier

2_Choices_Metastability___AAAI...
Fichiers produits par l'(les) auteur(s)

Identifiants

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

Collections

Citation

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

Partager

Métriques

Consultations de la notice

77

Téléchargements de fichiers

22