%0 Generic %1 tran2019reaching %A Tran, Linh %A Vu, Van %D 2019 %K influence network_analysis %T Reaching a Consensus on Random Networks: The Power of Few %U http://arxiv.org/abs/1911.10279 %X 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 $=.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.

@misc{tran2019reaching, abstract = {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.}, added-at = {2020-05-20T14:08:58.000+0200}, author = {Tran, Linh and Vu, Van}, biburl = {https://www.bibsonomy.org/bibtex/26ad439eb40f7d633cec45943db410209/j.c.m.janssen}, description = {Reaching a Consensus on Random Networks: The Power of Few}, interhash = {6aae00e949450d5cdd293afcdf6ec557}, intrahash = {6ad439eb40f7d633cec45943db410209}, keywords = {influence network_analysis}, note = {cite arxiv:1911.10279}, timestamp = {2020-05-20T14:08:58.000+0200}, title = {Reaching a Consensus on Random Networks: The Power of Few}, url = {http://arxiv.org/abs/1911.10279}, year = 2019 }