Balancing spreads of influence in a social network

The personalization of our news consumption on social media has a tendency to reinforce our pre-existing beliefs instead of balancing our opinions. This finding is a concern for the health of our democracies which rely on an access to information providing diverse viewpoints. To tackle this issue from a computational perspective, Garimella et al. (NIPS'17) modeled the spread of these viewpoints, also called campaigns, using the well-known independent cascade model and studied an optimization problem that aims at balancing information exposure in a social network when two opposing campaigns propagate in the network. The objective in their NP-hard optimization problem is to maximize the number of people that are exposed to either both or none of the viewpoints. For two different settings, one corresponding to a model where campaigns spread in a correlated manner, and a second one, where the two campaigns spread in a heterogeneous manner, they provide constant ratio approximation algorithms. In this paper, we investigate a more general formulation of this problem. That is, we assume that μ different campaigns propagate in a social network and we aim to maximize the number of people that are exposed to either nu or none of the campaigns, where μ≥nu≥2. We provide dedicated approximation algorithms for both the correlated and heterogeneous settings. Interestingly, for the heterogeneous setting with nu≥ 3, we give a reduction leading to several approximation hardness results. Maybe most importantly, we obtain that the problem cannot be approximated within a factor of n-g(n) for any g(n)=o(1) assuming Gap-ETH, denoting with n the number of nodes in the social network. For nu ≥ 4, there is no n-ε-approximation algorithm if a certain class of one-way functions exists, where ε > 0 is a given constant which depends on nu.