Balancing Spreads of Influence in a Social Network

Ruben Becker, Federico Corò, Gianlorenzo D'Angelo, Hugo GilbertAAAI 2020 · DOI

Abstract

This paper addresses the algorithmic roots of "echo chambers" and "filter bubbles" on social media. We generalize the problem of balancing information exposure to multiple campaigns through the $\mu$-$\nu$-BALANCE problem. The objective is to maximize the number of social network users exposed to either none or at least $\nu$ different information campaigns out of $\mu$ total. Our analysis reveals a significant "hardness jump" as the diversity threshold $\nu$ increases. While constant-factor approximations are possible in correlated settings, the general heterogeneous case is notoriously difficult, requiring novel greedy strategies to achieve even modest approximation guarantees.

Introduction

Social media algorithms often prioritize engagement, which can inadvertently create environments where users are only exposed to viewpoints that reinforce their existing beliefs. To combat this polarization, researchers have proposed "balancing" information exposure. The core challenge is an optimization problem: given a social network and several competing campaigns (e.g., different political perspectives), how can we select a small set of "seed" users to start these campaigns so that the general public receives a balanced view?

Earlier work focused on the case of exactly two campaigns ($\mu=2$). This work generalizes the problem to $\mu$ campaigns and a threshold $\nu$. The logic is that being exposed to only one or two viewpoints in a multi-faceted debate can be more polarizing than seeing nothing at all or seeing a broad spectrum of ideas.

The $\mu$-$\nu$-BALANCE Problem

We model information spread using the Independent Cascade Model (ICM), where nodes "activate" their neighbors with certain probabilities. The $\mu$-$\nu$-BALANCE problem seeks to select seed sets for $\mu$ campaigns to maximize the number of nodes that are either "oblivious" (0 campaigns) or "well-informed" (at least $\nu$ campaigns).

We distinguish between two primary settings:

  1. Heterogeneous Setting: Each campaign spreads with its own independent probability distribution. This is the most realistic but also the most computationally challenging.
  2. Correlated Setting: All campaigns spread identically. If a user shares one campaign, they share all campaigns they have received.

Algorithmic Approaches

The objective function for $\mu$-$\nu$-BALANCE is not submodular due to the threshold $\nu$, meaning standard greedy algorithms do not provide the usual guarantees. To address this, we propose several strategies:

  • GREEDYTUPLE: Instead of adding one seed at a time, this algorithm picks a "tuple" of seeds (size $\nu - \ell$) to jump-start the reward function when a node has already seen $\ell$ campaigns.
  • GREEDYITER: An iterative approach that maximizes the number of nodes reached by $\ell+1$ campaigns, given they were already reached by $\ell$ campaigns.
  • Fictitious Campaigning: For the correlated setting, we introduce a "fictitious" campaign to simplify the objective into a submodular maximization task, yielding better approximation ratios.

Hardness and Complexity

A striking insight of this work is the "hardness jump" that occurs as the threshold $\nu$ increases. While $\nu=2$ allows for a constant-factor approximation, $\nu=3$ makes the problem as hard as the "Densest-$k$-Subgraph" problem.

Figure 1: A gadget construction used in the hardness reduction for the $\mu$-$\nu$-BALANCE problem, illustrating the propagation of influence across a chain of nodes with specific activation probabilities.

As shown in Figure 1, the complexity arises from the need to coordinate multiple campaigns to reach the same nodes. For $\nu \geq 4$, the problem cannot be approximated within a factor of $n^{-\epsilon}$ under standard cryptographic assumptions.

Theoretical Results

The paper's results are primarily mathematical proofs regarding approximation bounds:

  • Heterogeneous Case: For $\nu \geq 3$, there is no $n^{-g(n)}$-approximation for any $g(n) = o(1)$. We provide an algorithm with an $\Omega(n^{-1/2})$ approximation ratio specifically for $\nu=3$.
  • Correlated Case: We achieve a constant-factor approximation of $(1 - 1/e - \epsilon)/(2(\nu + 1))$, demonstrating that balancing is computationally feasible if campaigns spread in a synchronized manner.

Conclusion

The $\mu$-$\nu$-BALANCE problem highlights the inherent difficulty in promoting information diversity algorithmically. While synchronized campaign spreads offer a path to tractability, the general case of diverse, independent viewpoints presents significant theoretical hurdles. Future work should explore "smoother" objective functions where exposure is treated as a spectrum rather than a binary threshold, and test these greedy variants on real-world social graphs to evaluate average-case performance.

Summary updated

BibTeX
@inproceedings{becker2020balancing,
  author = {Ruben Becker and Federico Corò and Gianlorenzo D'Angelo and Hugo Gilbert},
  title = {{Balancing Spreads of Influence in a Social Network}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i01.5327},
}
Figure