  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 $\Delta$-regular graph is sufficiently smaller than
$\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 $\Delta$-regular Ramanujan graph if the initial number of blue
nodes is $s\leq \beta n$, the number of blue nodes in the next round is at most
$\frac{cs}{\Delta}$ for some constants $c,\beta>0$. This settles an open
problem by Peleg.
