Balancing Spreads of Influence in a Social Network

Ruben Becker, Federico Coro, Gianlorenzo D'Angelo, Hugo Gilbert
AAAI 2020

Abstract : The personalization of our news consumption on social media has a tendency to reinforce our pre-existing beliefs instead of balancing our opinions. To tackle this issue, Garimella et al. (NIPS'17) modeled the spread of these viewpoints, also called campaigns, using the independent cascade model introduced by Kempe, Kleinberg and Tardos (KDD'03) and studied an optimization problem that aims to balance information exposure when two opposing campaigns propagate in a network. This paper investigates a natural generalization of this optimization problem in which $\mu$ different campaigns propagate in the network and we aim to maximize the expected number of nodes that are reached by at least $\nu$ or none of the campaigns, where $\mu \ge \nu \ge 2$. Following Garimella et al., we investigate two settings, a simplified setting, in which we show that the problem can be approximated within a constant factor for any constant $\mu$ and $\nu$ and a more general setting for which we give reductions leading to several approximation hardness results when $\nu \ge 3$. For instance, if we assume true the Gap-ET hypothesis, we prove that the problem cannot be approximated within a factor of $n^{-g(n)}$ for any $g(n) = o(1)$ where $n$ is the number of nodes in the network. We complement these hardness results with an $\Omega(n^{-1/2})$-approximation algorithm for the general setting when $\nu = 3$ and $\mu$ is arbitrary.