Distributed Community Detection via Metastability of the 2-Choices Dynamics
Authors: Emilio Cruciani, Emanuele Natale, Giacomo Scornavacca6046-6053
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. Our new analysis combines symmetry-breaking techniques (Becchetti et al. 2016; Clementi et al. 2018) and concentration of probability arguments with a linear algebraic approach (Cooper et al. 2015; 2017) to obtain the first symmetry-breaking analysis for dynamics on non-complete topologies. |
| Researcher Affiliation | Academia | Emilio Cruciani, Emanuele Natale, Giacomo Scornavacca Gran Sasso Science Institute emilio.cruciani@gssi.it Max Planck Institute f ur Informatik & Universit e Cˆote d Azur, CNRS, I3S, Inria natale@i3s.unice.fr Universit a degli Studi dell Aquila giacomo.scornavacca@graduate.univaq.it |
| Pseudocode | No | The paper describes the 2-CHOICES dynamics ('In each round, each node u chooses two neighbors v, w uniformly at random with replacement; if v and w support the same color, then u updates its own color to their color, otherwise u keeps its previously supported color.'), but this is a textual description rather than a formally formatted pseudocode or algorithm block. |
| Open Source Code | No | The paper is theoretical and does not mention or provide any open-source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and analyzes dynamics on abstract graph structures like a '(2n, d, b)-clustered regular graph' and the Stochastic Block Model, rather than performing empirical evaluation on specific datasets. No dataset is mentioned as being used for training or evaluation, nor is any concrete access information provided. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets, thus there is no mention of training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any computational experiments or their setup, therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe any computational implementation or experiment. Therefore, no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and focuses on mathematical proofs and analyses of dynamics. It does not describe any experimental setup details, hyperparameters, or system-level training settings. |