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

International audienceWe 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