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 introduced by Kempe et al. (KDD'03) 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, Garimella et al. 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 ν or none of the campaigns, where µ ≥ ν ≥ 2. We provide dedicated approximation algorithms for both the correlated and heterogeneous settings. Interestingly, while the problem can still be approximated within a constant factor in the correlated setting for any constant values of µ and ν, for the heterogeneous setting with ν ≥ 3, we give reductions 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 the Gap-ETH hypothesis, denoting with n the number of nodes in the social network. For ν ≥ 4, we furthermore show a stronger hardness of approximation bound under a different condition, that is, if a certain class of one-way functions exists, then there is no n -ǫ -approximation algorithm where ǫ > 0 is a given constant which depends on ν. This complements our finding of an approximation algorithm for the heterogeneous case that for arbitrary µ and ν = 3 leads to an approximation ratio of order n -1/2 .