Research map / Graph learning / Graph algorithms and clustering
Distributed Community Detection via Metastability of the 2-Choices Dynamics
Emilio Cruciani, Emanuele Natale, Giacomo Scornavacca
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Run 2-Choices dynamics from random binary states on a graph with b/d = O(n^{-1/2}) and λ = O(n^{-1/4}) | 2-Choices dynamics · Clustered regular graph | probability of reaching almost-clustered configuration within O(log n) rounds: ≥ γ1 | Improved |
| Start from an almost-clustered configuration and continue the dynamics | 2-Choices dynamics · Clustered regular graph | probability of remaining almost-clustered for n^c rounds: ≥ 1 - n^{-γ2} | Improved |
| Use Θ(log n) independent parallel runs as components of node label vectors | 2-Choices dynamics with Community-Sensitive Labeling · Clustered regular graph | number of node pairs not meeting the labeling condition: polylogarithmic number | Improved |
Closest papers by meaning
- Dynamic Evolution of Complex Networks: A Reinforcement Learning Approach Applying Evolutionary Games to Community Structure (TPAMI 2025 · similarity 0.86)
- Complex Network Evolution Model Based on Turing Pattern Dynamics (TPAMI 2022 · similarity 0.86)
- Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian (NeurIPS 2020 · similarity 0.86)
- Community Detection on Evolving Graphs (NeurIPS 2016 · similarity 0.86)
- Learning Persistent Community Structures in Dynamic Networks via Topological Data Analysis (AAAI 2024 · similarity 0.84)
- Sample Complexity of Linear Regression Models for Opinion Formation in Networks (AAAI 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
