Opinion Forming in Erdos-Renyi Random Graph and Expanders

Assume for a graph $G=(V,E)$ and an initial configuration, where each node is blue or red, in each discrete-time round all nodes simultaneously update their color to the most frequent color in their neighborhood and a node keeps its color in case of a tie. We study the behavior of this basic process, which is called majority model, on the binomial random graph ${\mathcal{G}}_{n,p}$ and regular expanders. First we consider the behavior of the majority model in ${\mathcal{G}}_{n,p}$ with an initial random configuration, where each node is blue independently with probability $p_b$ and red otherwise. It is shown that in this setting the process goes through a phase transition at the connectivity threshold, namely $\frac{\log n}{n}$. Furthermore, we discuss the majority model is a good' and fast’ density classifier on regular expanders. More precisely, we prove if the second-largest absolute eigenvalue of the adjacency matrix of an $n$-node $\mathrm{\Delta }$-regular graph is sufficiently smaller than $\mathrm{\Delta }$ then the majority model by starting from $(\frac{1}{2}-\delta )n$ blue nodes (for an arbitrarily small constant $\delta >0$) results in fully red configuration in sub-logarithmically many rounds. As a by-product of our results, we show Ramanujan graphs are asymptotically optimally immune, that is for an $n$-node $\mathrm{\Delta }$-regular Ramanujan graph if the initial number of blue nodes is $s\le \beta n$, the number of blue nodes in the next round is at most $\frac{cs}{\mathrm{\Delta }}$ for some constants $c,\beta >0$. This settles an open problem by Peleg.