On the complexity of reasoning about opinion diffusion under majority dynamics

摘要

We study opinion diffusion on social graphs where agents hold binary opinions and where social pressure leads them to conform to the opinion manifested by the majority of their neighbors. We provide bounds relating the number of agents that suffice to spread an opinion to all other agents with the number of required propagation steps. Bounds are established constructively, via polynomial time algorithms that identify the agents that must act as seeds. In particular, we show that, on any given social graph G=(N,E), it is possible to efficiently identify a set formed by half of the agents that can lead to consensus in min⁡{⌊|N|/2⌋,even(G)+1} propagation steps, where even(G) is the number of agents with an even number of neighbors in G. The result marks the boundary of tractability, since we show that the existence of sets of seeds consisting of less than half of the agents depends on certain features of the underlying graphs, which are NP-hard to identify. In fact, other NP-hardness results emerge from our analysis. In particular, by closing a problem left open in the literature, we show that it is intractable to decide whether further stable configurations exist in addition to the “consensus” ones (where all agents hold the same opinion). Eventually, for all these problems related to reasoning about opinion diffusion, we show that islands of tractability can be identified by focusing on classes of tree-like social graphs.