Reaching a Consensus on Random Networks: The Power of Few

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 $\epsilon$, there is a constant $C$ such that if one camp has $n/2+C$ individuals, then it wins with probability at least $1-\epsilon$. The surprising key fact here is that $C$ does not depend on $n$, the population of the community. When $p=1/2$ and $\epsilon =.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.