License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2019.32
URN: urn:nbn:de:0030-drops-113397
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11339/
Shimizu, Nobutaka ;
Shiraga, Takeharu
Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models
Abstract
This paper 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 and discrete time step, 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). Previous studies have explored these processes on complete graphs and expander graphs, but we understand significantly less about their properties on graphs with more complicated structures.
In this paper, we study the Best-of-two and the Best-of-three on the stochastic block model G(2n,p,q), which is a random graph consisting of two distinct Erdös-Rényi graphs G(n,p) joined by random edges with density q <= p. We obtain two main results. First, if p=omega(log n/n) and r=q/p is a constant, we show that there is a phase transition in r with threshold r^* (specifically, r^*=sqrt{5}-2 for the Best-of-two, and r^*=1/7 for the Best-of-three). If r>r^*, the process reaches consensus within O(log log n+log n/log (np)) steps for any initial opinion configuration with a bias of Omega(n). By contrast, if r<r^*, then there exists an initial opinion configuration with a bias of Omega(n) from which the process requires at least 2^{Omega(n)} steps to reach consensus. Second, if p is a constant and r>r^*, we show that, for any initial opinion configuration, the process reaches consensus within O(log n) steps. To the best of our knowledge, this is the first result concerning multiple-choice voting for arbitrary initial opinion configurations on non-complete graphs.
BibTeX - Entry
@InProceedings{shimizu_et_al:LIPIcs:2019:11339,
author = {Nobutaka Shimizu and Takeharu Shiraga},
title = {{Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models}},
booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)},
pages = {32:1--32:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-126-9},
ISSN = {1868-8969},
year = {2019},
volume = {146},
editor = {Jukka Suomela},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11339},
URN = {urn:nbn:de:0030-drops-113397},
doi = {10.4230/LIPIcs.DISC.2019.32},
annote = {Keywords: Distributed Voting, Consensus Problem, Random Graph}
}
|
Keywords: |
|
Distributed Voting, Consensus Problem, Random Graph |
|
Collection: |
|
33rd International Symposium on Distributed Computing (DISC 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
08.10.2019 |
