Balancing the Spread of Two Opinions in Sparse Social Networks (Student Abstract)

We propose a new discrete model for simultaneously spreading two opinions within a social network inspired by the famous TARGET SET SELECTION problem. We are given a social network, a seed-set of agents for each opinion, and two thresholds per agent. The first threshold represents the willingness of an agent to adopt an opinion if she has no opinion at all, while the second threshold states the readiness to acquire a second opinion arriving. The goal is to add as few agents as possible to the initial seed-sets such that, once the process started with these seed-set stabilises, each agent has either both opinions or none. We perform an initial study of its computational complexity. It is not surprising that the problem is NP-hard even in quite restricted settings. Therefore, we investigate the complexity of the problem from the parametrized point-of-view with special focus on sparse networks, which appears often in practice. Among other things, we show that the proposed problem is in FPT if we parametrize by the vertex cover number of the underlying graph.

Authors

• Dušan Knop Czech Technical University in Prague
• Šimon Schierreich AGH University of Krakow
• Ondřej Suchý

Keywords

No keywords are indexed for this paper.