Mitigating Negative Influence Diffusion is Hard

The way how the influence of a set of users is diffused in a social network has been widely studied in the last decades. Most of the work focused on maximizing the spread of influence or the diffusion of information (e.g., a viral marketing message) starting from a set of initial nodes called seeds. Unfortunately, malicious users can use these algorithms to spread negative messages, consisting of racist or hateful contents, misinformation, or fake news. We consider a scenario in which a malicious entity, the attacker, spreads a negative message and another entity, the defender, tries to mitigate the effects of the negative message by spreading another message that invalidates the former with some evidence that its content is wrong. The attacker has the advantage of playing first, knowing that the defender will play afterward, while the defender has the advantage of observing the attacker's spread. We define two optimization problems: the attacker, who is aware of the defender and her budget, selects a set of seeds to maximize the number of influenced nodes; when the attacker's diffusion process is finished, the defender selects her own seeds with the aim of minimizing the number of nodes that remain influenced by the attacker.