We consider opinion diffusion on social graphs where agents hold opinions and where social pressure leads them to conform to the opinion manifested by the majority of their neighbors. Within this setting, we look for dynamics that allows us to maximize the diffusion of a target opinion given the initial opinions of all agents. In particular, we focus on the setting where more than two opinions are available to the agents, and we show that the properties of this setting are entirely different from those characterizing the setting where agents hold binary opinions only. Indeed, while it is well-known that greedy dynamics are always optimal ones in the binary case, this is no longer true in our more general setting and-rather surprisingly-even if just three opinions are available. Moreover, while it is possible to decide in polynomial time if a dynamics leading to consensus exists when agents have two available opinions, the problem becomes computationally intractable with three opinions, regardless of the fraction of agents that have the target opinion as their initial opinion. (C) 2021 Elsevier B.V. All rights reserved.

Optimal majority dynamics for the diffusion of an opinion when multiple alternatives are available

Greco G.
2021-01-01

Abstract

We consider opinion diffusion on social graphs where agents hold opinions and where social pressure leads them to conform to the opinion manifested by the majority of their neighbors. Within this setting, we look for dynamics that allows us to maximize the diffusion of a target opinion given the initial opinions of all agents. In particular, we focus on the setting where more than two opinions are available to the agents, and we show that the properties of this setting are entirely different from those characterizing the setting where agents hold binary opinions only. Indeed, while it is well-known that greedy dynamics are always optimal ones in the binary case, this is no longer true in our more general setting and-rather surprisingly-even if just three opinions are available. Moreover, while it is possible to decide in polynomial time if a dynamics leading to consensus exists when agents have two available opinions, the problem becomes computationally intractable with three opinions, regardless of the fraction of agents that have the target opinion as their initial opinion. (C) 2021 Elsevier B.V. All rights reserved.
2021
Opinion diffusion
Stability
Consensus
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11770/353877
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 2
social impact