Biased Majority Opinion Dynamics: Exploiting graph $k$-domination - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2022

Biased Majority Opinion Dynamics: Exploiting graph $k$-domination

Résumé

We study opinion dynamics in multi-agent networks where agents hold binary opinions and are influenced by their neighbors while being biased towards one of the two opinions, called the superior opinion. The dynamics is modeled by the following process: at each round, a randomly selected agent chooses the superior opinion with some probability α, and with probability 1 − α it conforms to the opinion manifested by the majority of its neighbors. In this work, we exhibit classes of network topologies for which we prove that the expected time for consensus on the superior opinion can be exponential. This answers an open conjecture in the literature. In contrast, we show that in all cubic graphs, convergence occurs after a polynomial number of rounds for every α. We rely on new structural graph properties by characterizing the opinion formation in terms of multiple domination, stable and decreasing structures in graphs, providing an interplay between bias, consensus and network structure. Finally, we provide both theoretical and experimental evidence for the existence of decreasing structures and relate it to the rich behavior observed on the expected convergence time of the opinion diffusion model.
Fichier principal
Vignette du fichier
Opinion-Dynamics-IJCAI-22.pdf (416.15 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03676312 , version 1 (23-05-2022)

Identifiants

  • HAL Id : hal-03676312 , version 1

Citer

Hicham Lesfari, Frédéric Giroire, Stéphane Pérennes. Biased Majority Opinion Dynamics: Exploiting graph $k$-domination. IJCAI 2022 - International Joint Conference on Artificial Intelligence, Jul 2022, Vienna, Austria. ⟨hal-03676312⟩
201 Consultations
139 Téléchargements

Partager

Gmail Facebook X LinkedIn More