Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models

DOI10.1002/rsa.20992zbMath1527.68027OpenAlexW2982652745MaRDI QIDQ6074651

Nobutaka Shimizu, Takeharu Shiraga

Publication date: 12 October 2023

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20992

zbMATH Keywords

random graphconsensus problemdistributed voting

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Voting theory (91B12) Distributed systems (68M14) Distributed algorithms (68W15) Random walks on graphs (05C81) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (1)

Brief Announcement: Discrete Incremental Voting

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Global majority consensus by local majority polling on graphs of a given degree sequence
• An improvement of convergence rate estimates in the Lyapunov theorem
• Easy impossibility proofs for distributed consensus problems
• Fast consensus for voting on general expander graphs
• Distributed probabilistic polling and applications to proportionate agreement
• Simple dynamics for plurality consensus
• Introduction to Random Graphs
• A Biological Solution to a Fundamental Distributed Computing Problem
• BOULWARE STATE IN EXACTLY SOLVABLE MODELS OF 2D DILATON GRAVITY
• Community Detection and Stochastic Block Models
• Stabilizing Consensus with Many Opinions
• The Linear Voting Model
• Find Your Place: Simple Distributed Algorithms for Community Detection
• The Power of Two Choices in Distributed Voting
• A Survey of Statistical Network Models
• Random walks on graphs: new bounds on hitting, meeting, coalescing and returning
• Nearly-Tight Analysis for 2-Choice and 3-Majority Consensus Dynamics
• On coalescence time in graphs: When is coalescing as fast as meeting?: Extended Abstract
• Ignore or Comply?
• Coalescing Random Walks and Voting on Connected Graphs
• Implicit Functions and Solution Mappings
• Concentration of multivariate polynomials and its applications
• Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models

This page was built for publication: Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models