Document Open Access Logo

Brief Announcement: Phase Transitions of the k-Majority Dynamics in a Biased Communication Model

Authors Emilio Cruciani , Hlafo Alfie Mimun , Matteo Quattropani , Sara Rizzo

PDF

File

Thumbnail PDF
PDF
LIPIcs.DISC.2020.42.pdf
  • Filesize: 359 kB
  • 3 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Random walks and Markov chains
  • Theory of computation → Distributed algorithms
  • Mathematics of computing → Probabilistic algorithms
  • Mathematics of computing → Markov processes
Keywords
  • Biased Communication
  • Consensus
  • Majority Dynamics
  • Markov Chains
  • Metastability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We analyze the binary-state (either ℛ or ℬ) k-majority dynamics in a biased communication model where nodes have some fixed probability p, independent of the dynamics, of being seen in state ℬ by their neighbors. In this setting we study how p, as well as the initial unbalance between the two states, impact on the speed of convergence of the process, identifying sharp phase transitions.

Cite As Get BibTex

Emilio Cruciani, Hlafo Alfie Mimun, Matteo Quattropani, and Sara Rizzo. Brief Announcement: Phase Transitions of the k-Majority Dynamics in a Biased Communication Model. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 42:1-42:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.DISC.2020.42

Author Details

Emilio Cruciani
  • Inria, I3S Lab, Université Côte d'Azur, CNRS, Valbonne, France
Hlafo Alfie Mimun
  • Department of Economics and Finance, LUISS, Roma, Italy
Matteo Quattropani
  • Department of Economics and Finance, LUISS, Roma, Italy
Sara Rizzo
  • Gran Sasso Science Institute, L'Aquila, Italy

References

  1. Luca Becchetti, Emilio Cruciani, Francesco Pasquale, and Sara Rizzo. Step-by-step community detection in volume-regular graphs. In ISAAC 2019, pages 20:1-20:23, 2019. Google Scholar
  2. Colin Cooper, Robert Elsässer, Hirotaka Ono, and Tomasz Radzik. Coalescing random walks and voting on connected graphs. SIAM J. Discrete Math., 27(4):1748-1758, 2013. Google Scholar
  3. Emilio Cruciani, Emanuele Natale, André Nusser, and Giacomo Scornavacca. Phase transition of the 2-choices dynamics on core-periphery networks. In AAMAS 2018, pages 777-785, 2018. Google Scholar
  4. Emilio Cruciani, Emanuele Natale, and Giacomo Scornavacca. Distributed community detection via metastability of the 2-choices dynamics. In AAAI 2019, pages 6046-6053, 2019. Google Scholar
  5. Mohsen Ghaffari and Johannes Lengler. Nearly-tight analysis for 2-choice and 3-majority consensus dynamics. In PODC 2018, pages 305-313, 2018. Google Scholar
  6. Nobutaka Shimizu and Takeharu Shiraga. Phase transitions of best-of-two and best-of-three on stochastic block models. In DISC 2019, pages 32:1-32:17, 2019. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact