Reaching a Consensus on Random Networks: The Power of Few
Reaching a Consensus on Random Networks: The Power of Few
复制标题
在随机网络上达成共识：少数人的力量
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
V. Vu
中科院分区：
文献类型：
--
作者：
L. Tran;V. Vu
一个由 $n$ 个人组成的社区分为两个阵营：红色和蓝色。个体通过社交网络联系在一起，这影响了他们的颜色。每天，每个人都会根据邻居中的大多数来改变自己的颜色。如果社区中的每个人在某个时刻都变成红色（蓝色），则红色（蓝色）获胜。
当底层网络是随机 Erdos-Renyi 图 $G(n, p)$ 时，我们研究这个过程。在平衡的初始状态下（每个阵营中有 $n/2$ 人），很明显每种颜色以相同的概率获胜。
我们的研究表明，对于任何常数 $p$ 和 $\varepsilon$，都存在一个常数 $C$，这样如果一个阵营有 $n/2 +C$ 个体，那么它获胜的概率至少为 $1 - \varepsilon$。这里令人惊讶的关键事实是 $C$ 并不依赖于社区人口 $n$。当$p=1/2$且$\varepsilon =.1$时，可以将$C$设置为小至6。如果该过程的目的是选择一名候选人，那么这意味着只需要$6$的“叛逃者”就能以压倒性的优势一致赢得选举。
A community of $n$ individuals splits into two camps, Red and Blue. The individuals are connected by a social network, which influences their colors. Everyday, each person changes his/her color according to the majority among his/her neighbors. Red (Blue) wins if everyone in the community becomes Red (Blue) at some point.
We study this process when the underlying network is the random Erdos-Renyi graph $G(n, p)$. With a balanced initial state ($n/2$ person in each camp), it is clear that each color wins with the same probability.
Our study reveals that for any constants $p$ and $\varepsilon$, there is a constant $C$ such that if one camp has $n/2 +C$ individuals, then it wins with probability at least $1 - \varepsilon$. The surprising key fact here is that $C$ does not depend on $n$, the population of the community. When $p=1/2$ and $\varepsilon =.1$, one can set $C$ as small as 6. If the aim of the process is to choose a candidate, then this means it takes only $6$ "defectors" to win an election unanimously with overwhelming odd.
多数动力学猜想的解决：密集随机图中的快速稳定
影响因子：
1
作者：
Fountoulakis N
通讯作者：
Fountoulakis N
DOI：
10.1137/1.9781611974782.169
发表时间：
2016-02
期刊：
ArXiv
影响因子：
--
作者：
Dan Alistarh;J. Aspnes;David Eisenstat;Rati Gelashvili;R. Rivest
通讯作者：
Dan Alistarh;J. Aspnes;David Eisenstat;Rati Gelashvili;R. Rivest