Convergence of Opinion Diffusion Is PSPACE-Complete

Dmitry Chistikov, Grzegorz Lisowski, Mike Paterson, Paolo Turrini

AAAI 2020 pp. 7103-7110

doi:10.1609/AAAI.V34I05.6197 /aaai/2020/chistikov2020aaai-convergence/

Abstract

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.

PDF AAAI Semantic Scholar

Cite

Text

Chistikov et al. "Convergence of Opinion Diffusion Is PSPACE-Complete." AAAI Conference on Artificial Intelligence, 2020. doi:10.1609/AAAI.V34I05.6197

Markdown

[Chistikov et al. "Convergence of Opinion Diffusion Is PSPACE-Complete." AAAI Conference on Artificial Intelligence, 2020.](https://mlanthology.org/aaai/2020/chistikov2020aaai-convergence/) doi:10.1609/AAAI.V34I05.6197

BibTeX

@inproceedings{chistikov2020aaai-convergence,
  title     = {{Convergence of Opinion Diffusion Is PSPACE-Complete}},
  author    = {Chistikov, Dmitry and Lisowski, Grzegorz and Paterson, Mike and Turrini, Paolo},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2020},
  pages     = {7103-7110},
  doi       = {10.1609/AAAI.V34I05.6197},
  url       = {https://mlanthology.org/aaai/2020/chistikov2020aaai-convergence/}
}