Approximate Algorithms for Data-Driven Influence Limitation

Sourav Medya*, Arlei Silva, Ambuj Singh

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

Online social networks have become major battlegrounds for political campaigns, viral marketing, and the dissemination of news. As a consequence, 'bad actors' are increasingly exploiting these platforms, which is a key challenge for their administrators, businesses and society in general. The spread of fake news is a classical example of the abuse of social networks by these bad actors. While some have advocated for stricter policies to control the spread of misinformation in social networks, this often happens in detriment of their democratic and organic structure. In this paper, we aim to limit the influence of a target group in a social network via the removal of a few users/links. We formulate the influence limitation problem in a data-driven fashion, by taking into account past propagation traces. More specifically, our algorithms find critical edges to be removed in order to decrease the influence of a target group based on past data. The idea is to control the diffusion processes while minimizing the amount of disturbance in the network structure. Moreover, we consider two types of constraints over edge removals, a budget constraint and also a, more general, set of matroid constraints. These problems lead to interesting challenges in terms of algorithm design. For instance, we are able to show that influence limitation is APX-hard and propose deterministic and probabilistic approximation algorithms for the budgeted and the matroid version of the problem, respectively. Experiments show that the proposed approaches outperform several baselines.

Original languageEnglish (US)
Pages (from-to)2641-2652
Number of pages12
JournalIEEE Transactions on Knowledge and Data Engineering
Volume34
Issue number6
DOIs
StatePublished - Jun 1 2022

Keywords

  • approximation
  • combinatorial optimization
  • Influence control
  • network design

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Approximate Algorithms for Data-Driven Influence Limitation'. Together they form a unique fingerprint.

Cite this