Random Majority Opinion Diffusion: Stabilization Time, Absorbing States, and Influential Nodes

Consider a graph 𝐺 with 𝑛 nodes and 𝑚 edges, which represents a social network, and assume that initially each node is blue or white (indicating 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 prove that there are graphs for which RMM needs exponentially many rounds to reach a stable configuration in expectation, and such a configuration can have exponentially many states (i.e., colorings). This is in contrast to MM, which is known to always reach a stable configuration with one or two states in O (𝑚) rounds. For the special case of a cycle graph 𝐶 𝑛 , we prove the stronger and tight bounds of ⌈𝑛/2⌉-1 and O (𝑛 2) in MM and RMM, respectively. Furthermore, we show that the number of stable colorings in MM on 𝐶 𝑛 is equal to Θ (Φ 𝑛), where Φ = (1 +