Premium
Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models
Author(s) -
Shimizu Nobutaka,
Shiraga Takeharu
Publication year - 2021
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20992
Subject(s) - combinatorics , vertex (graph theory) , random graph , stochastic block model , mathematics , graph , voting , block (permutation group theory) , best practice , discrete mathematics , statistics , cluster analysis , politics , political science , law , management , economics
This is concerned with voting processes on graphs where each vertex holds one of two different opinions. In particular, we study the Best‐of‐two and the Best‐of‐three . Here at each synchronous round, each vertex updates its opinion to match the majority among the opinions of two random neighbors and itself (the Best‐of‐two) or the opinions of three random neighbors (the Best‐of‐three). In this study, we consider the Best‐of‐two and the Best‐of‐three on the stochastic block model G (2 n , p , q ), which is a random graph consisting of two distinct Erdős–Rényi graphs G ( n , p ) joined by random edges with a density q ≤ p . We prove phase transition results for these processes: there is a threshold r ∗ such that, if q / p > r ∗ then the process reaches consensus within O ( log n ) rounds and the process requires exp ( Ω ( n ) ) rounds if q / p < r ∗ . For the Best‐of‐two and Best‐of‐three, the thresholds arer ∗ = 5 − 2 and r ∗ = 1/7, respectively.