Approximate Algorithms for Data-Driven Influence Limitation
Approximate Algorithms for Data-Driven Influence Limitation
复制标题
DOI：
10.1109/tkde.2020.3016293
复制
发表时间：
2022-06
影响因子：
8.9
通讯作者：
Sourav Medya;A. Silva;Ambuj K. Singh
中科院分区：
文献类型：
--
作者：
Sourav Medya;A. Silva;Ambuj K. Singh
在线社交网络已经成为政治竞选、病毒式营销和新闻传播的主要战场。因此，“不良行为者”越来越多地利用这些平台，这对这些平台的管理人员、企业和整个社会都是一个关键挑战。假新闻的传播是这些不良行为者滥用社交网络的典型例子。虽然有些人主张采取更严格的政策来控制错误信息在社交网络中的传播，但这种情况往往损害其民主和有机结构。在本文中，我们的目标是通过删除一些用户/链接来限制目标群体在社交网络中的影响力。我们制定的影响力限制问题的数据驱动的方式，考虑到过去的传播轨迹。更具体地说，我们的算法找到关键的边缘被删除，以减少基于过去的数据的目标群体的影响。我们的想法是控制扩散过程，同时最大限度地减少网络结构中的干扰量。此外，我们考虑两种类型的约束，在边缘去除，预算约束，也是一个更一般的，一组拟阵约束。这些问题在算法设计方面带来了有趣的挑战。例如，我们能够证明影响限制是APX硬的，并分别为预算和拟阵版本的问题提出确定性和概率近似算法。实验表明，所提出的方法优于几个基线。
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.