Resolution of a conjecture on majority dynamics: Rapid stabilization in dense random graphs
Resolution of a conjecture on majority dynamics: Rapid stabilization in dense random graphs
复制标题
多数动力学猜想的解决：密集随机图中的快速稳定
DOI：
10.1002/rsa.20970
复制
发表时间：
2020
影响因子：
1
通讯作者：
Fountoulakis N
中科院分区：
文献类型：
--
作者：
Fountoulakis N
本文研究了二项随机图G（n，p）的多数动力学，其中p =d/n.在这个过程中，每个顶点都有一个在{-1，+ 1}中的状态，并且在每一轮中，每个顶点都采用其大多数邻居的状态，在平局的情况下保持其状态。我们表明，以高概率的过程中达到最多四个回合。这证实了Benjamini等人的猜想。
We study majority dynamics on the binomial random graphG(n,p) withp=d/nand , for some large . In this process, each vertex has a state in {− 1, + 1} and at each round every vertex adopts the state of the majority of its neighbors, retaining its state in the case of a tie. We show that with high probability the process reaches unanimity in at most four rounds. This confirms a conjecture of Benjamini et al.
登录
查看更多内容
通过图表上的本地多数投票得出全球多数共识
DOI：
--
发表时间：
2012
期刊：
International Conference on Network Games, Control and Optimization
影响因子：
--
作者：
Mohammed Abdullah;M. Draief
通讯作者：
M. Draief
影响因子：
1.9
作者：
Mossel, Elchanan;Neeman, Joe;Tamuz, Omer
通讯作者：
Tamuz, Omer
在随机网络上达成共识：少数人的力量
DOI：
--
发表时间：
2019
期刊：
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
影响因子：
--
作者：
L. Tran;V. Vu
通讯作者：
V. Vu
Erdös-Rényi 随机图和扩展器中的意见形成
DOI：
--
发表时间：
2018
期刊：
International Symposium on Algorithms and Computation
影响因子：
--
作者：
Ahad N. Zehmakan
通讯作者：
Ahad N. Zehmakan
影响因子：
0.8
作者：
E. Goles;J. Olivos
通讯作者：
J. Olivos