Balancing spreads of influence in a social network
share
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 ν or none of the campaigns, where μ>ν>2. We provide dedicated approximation algorithms for both the correlated and heterogeneous settings. Interestingly, for the heterogeneous setting with ν> 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 ν> 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 ν.
READ FULL TEXT
