# Convergence of Opinion Diffusion is PSPACE-complete

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Dec 2019.

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

- [Majority Opinion Diffusion in Social Networks: An Adversarial Approach](https://mlsanity.com/paper/2012.03143/) (2020)
- [Random Majority Opinion Diffusion: Stabilization Time, Absorbing States, and Influential Nodes](https://mlsanity.com/paper/2302.06760/) (2023)
- [A Structural Complexity Analysis of Synchronous Dynamical Systems](https://mlsanity.com/paper/2312.08385/) (2023)
- [Viral Marketing in Social Networks with Competing Products](https://mlsanity.com/paper/2312.15819/) (2023)
- [Finding Nontrivial Minimum Fixed Points in Discrete Dynamical Systems](https://mlsanity.com/paper/2301.04090/) (2023)
- [A Generalisation of Voter Model: Influential Nodes and Convergence Properties](https://mlsanity.com/paper/2411.04564/) (2024)

## Abstract (arXiv)

We analyse opinion diffusion in social networks, where a finite set of individuals is connected in a directed graph and each simultaneously changes their opinion to that of the majority of their influencers. We study the algorithmic properties of the fixed-point behaviour of such networks, showing that the problem of establishing whether individuals converge to stable opinions is PSPACE-complete.