Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models. Issue 1 (11th January 2021)

• Record Type: Journal Article
• Authors: Shimizu, Nobutaka; Shiraga, Takeharu
• Is Part Of: Random structures & algorithms. Volume 59:Issue 1(2021)
• Page Start: 96
• Page End: 140
• Publication Date: 2021-01-11
• Subjects: consensus problem -- distributed voting -- random graph; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20992
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: 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 are r ∗ = 5 − 2 and r ∗ = 1/7, respectively.