Skip to Main content Skip to Navigation
Conference papers

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

Hicham Lesfari 1, 2, 3 Frédéric Giroire 1 Stéphane Pérennes 1 
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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.
Complete list of metadata
Contributor : Hicham Lesfari Connect in order to contact the contributor
Submitted on : Monday, May 23, 2022 - 6:07:20 PM
Last modification on : Tuesday, August 9, 2022 - 2:44:57 PM


Files produced by the author(s)


  • HAL Id : hal-03676312, version 1


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⟩



Record views


Files downloads