Convergence of Opinion Diffusion is PSPACE-complete
Not on the map. Why?
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.
Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). First posted on arXiv 20 Dec 2019.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2020: 1; 2021: 0; 2022: 0; 2023: 4; 2024: 1.
6 papers.
- 2020Majority Opinion Diffusion in Social Networks: An Adversarial Approachcited by 4
- 2023Random Majority Opinion Diffusion: Stabilization Time, Absorbing States, and Influential Nodescited by 2
- 2023A Structural Complexity Analysis of Synchronous Dynamical Systemscited by 1
- 2023Viral Marketing in Social Networks with Competing Productscited by 1
- 2023Finding Nontrivial Minimum Fixed Points in Discrete Dynamical Systemscited by 0
- 2024A Generalisation of Voter Model: Influential Nodes and Convergence Propertiescited by 0
- 2024A Generalisation of Voter Model: Influential Nodes and Convergence Properties7 Nov 2024
- 2023Viral Marketing in Social Networks with Competing Products25 Dec 2023
- 2023A Structural Complexity Analysis of Synchronous Dynamical Systems12 Dec 2023
- 2023Random Majority Opinion Diffusion: Stabilization Time, Absorbing States, and Influential Nodes14 Feb 2023
- 2023Finding Nontrivial Minimum Fixed Points in Discrete Dynamical Systems6 Jan 2023
- 2020Majority Opinion Diffusion in Social Networks: An Adversarial Approach5 Dec 2020