Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models
Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models
复制标题
随机块模型上的最佳二选一和最佳三选一的相变
DOI：
10.1002/rsa.20992
复制
发表时间：
2021
影响因子：
1
通讯作者：
Shiraga Takeharu
中科院分区：
文献类型：
--
作者：
Shimizu Nobutaka;Shiraga Takeharu
这与图上的投票过程有关，其中每个顶点持有两种不同意见之一。我们特别研究了两局两胜和三局两胜。在每个同步轮中，每个顶点都会更新其意见，以匹配两个随机邻居及其自身的意见中的大多数（“两个最佳”）或三个随机邻居（“三个最佳”）的意见。在本研究中，我们考虑随机块模型 G(2n,p,q) 上的二选一和三选一，该模型是由两个不同的 Erdős-Rényi 图 G(n,p) 由密度 q≤p 的随机边连接而成的随机图。我们证明这些过程的相变结果：存在一个阈值r*，如果q/p>r*，那么该过程在轮次内达成共识，并且如果q/p<r*，该过程需要轮次。对于“二选一”和“三选一”，阈值分别为 andr*= 1/7。
This is concerned with voting processes on graphs where each vertex holds one of two different opinions. In particular, we study theBest‐of‐twoand theBest‐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 modelG(2n,p,q), which is a random graph consisting of two distinct Erdős–Rényi graphsG(n,p) joined by random edges with a densityq≤p. We prove phase transition results for these processes: there is a thresholdr∗such that, ifq/p>r∗then the process reaches consensus within rounds and the process requires rounds ifq/p<r∗. For the Best‐of‐two and Best‐of‐three, the thresholds are andr∗= 1/7, respectively.