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

arXiv: https://arxiv.org/abs/2302.06760 · HTML: https://mlsanity.com/paper/2302.06760/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 51 references that are in the map.
- First posted on arXiv 14 Feb 2023.

## Builds on (most cited first, 12 of 12)

- [Influence maximization in unknown social networks: Learning Policies for Effective Graph Sampling](https://mlsanity.com/paper/1907.11625/) (2019)
- [Controlling Elections through Social Influence](https://mlsanity.com/paper/1711.08615/) (2017)
- [Convergence of Opinion Diffusion is PSPACE-complete](https://mlsanity.com/paper/1912.09864/) (2019)
- [Biased Opinion Dynamics: When the Devil Is in the Details](https://mlsanity.com/paper/2008.13589/) (2020)
- [Opinion Forming in Erdos-Renyi Random Graph and Expanders](https://mlsanity.com/paper/1805.12172/) (2018)
- [Majority Opinion Diffusion in Social Networks: An Adversarial Approach](https://mlsanity.com/paper/2012.03143/) (2020)
- [Limitations of Greed: Influence Maximization in Undirected Networks Re-visited](https://mlsanity.com/paper/2002.11679/) (2020)
- [Majority Vote in Social Networks: Make Random Friends or Be Stubborn to Overpower Elites](https://mlsanity.com/paper/2109.14265/) (2021)
- [Majority Model on Random Regular Graphs](https://mlsanity.com/paper/1711.07423/) (2017)
- [How Hard is Safe Bribery?](https://mlsanity.com/paper/2201.10383/) (2022)
- [Asynchronous Opinion Dynamics in Social Networks](https://mlsanity.com/paper/2201.12923/) (2022)
- [Probabilistic Inference of Winners in Elections by Independent Random Voters](https://mlsanity.com/paper/2101.12524/) (2021)

## Built on by (most cited first, 2 of 2)

- [Viral Marketing in Social Networks with Competing Products](https://mlsanity.com/paper/2312.15819/) (2023)
- [A Generalisation of Voter Model: Influential Nodes and Convergence Properties](https://mlsanity.com/paper/2411.04564/) (2024)

## Abstract (arXiv)

Consider a graph G with n nodes and m edges, which represents a social network, and assume that initially each node is blue or white. 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(m) rounds. For the special case of a cycle graph Cn, we prove the stronger and tight bounds of lceil n/2rceil-1 and O(n2) in MM and RMM, respectively. Furthermore, we show that the number of stable colorings in MM on Cn is equal to Theta(Phin), where Phi = (1+√5)/2 is the golden ratio, while it is equal to 2 for RMM. We also study 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. We present tight bounds on the minimum size of a winning set for both MM and RMM. Furthermore, we analyze our models for a random initial coloring, where each node is colored blue independently with some probability p and white otherwise. Using some martingale analysis and counting arguments, we prove that the expected final number of blue nodes is respectively equal to (2p2-p3)n/(1-p+p2) and pn in MM and RMM on a cycle graph Cn. Finally, we conduct some experiments which complement our theoretical findings and also lead to the proposal of some intriguing open problems and conjectures to be tackled in future work.