Majority opinion diffusion: when tie-breaking rule matters.

Consider a graph G, which represents a social network, and assume that initially each node
is either blue or white (corresponding to its opinion on a certain topic). In each round, all
nodes simultaneously update their color to the most frequent color in their neighborhood.
This is called the Majority Model (MM) if a node keeps its color in case of a tie and the
Random Majority Model (RMM) if it chooses blue with probability 1/2 and white otherwise. We study the convergence properties of the above models, including stabilization
time, periodicity, and the number of stable confgurations. In particular, we prove that the
stabilization time in RMM can be exponential in the size of the graph, which is in contrast
with the previously known polynomial bound on the stabilization time of MM. We provide
some bounds on the minimum size of a winning set, which is a set of nodes whose agreement on a color in the initial coloring enforces the process to end in a coloring where all
nodes share that color. Furthermore, we calculate the expected fnal number of blue nodes
for a random initial coloring, where each node is colored blue independently with some
fxed probability, on cycle graphs. Finally, we conduct some experiments which complement our theoretical fndings and also let us investigate other aspects of the models.