论文标题
对影响最大化的可扩展对抗攻击算法
Scalable Adversarial Attack Algorithms on Influence Maximization
论文作者
论文摘要
在本文中，我们研究了社交网络中动态影响传播模型下对影响最大化的对抗性攻击。特别是，给定一个已知的种子集，问题是通过删除有限数量的节点和边缘来最大程度地减少从s传播的影响。这个问题反映了许多应用程序情况，例如通过隔离和疫苗接种在社交网络中阻止病毒（例如COVID-19）传播，通过冻结伪造的帐户来阻止谣言传播，或通过激励某些用户忽略竞争对手的信息来攻击竞争对手的影响力。在本文中，在线性阈值模型下，我们适应了反向影响采样方法，并提供了采样有效的有效反向到达路径的有效算法来解决问题。我们在反向采样上提出了三种不同的设计选择，所有这些选择都可以保证$ 1/2 - \ Varepsilon $近似（对于任何小$ \ varepsilon> 0 $）和有效的运行时间。
In this paper, we study the adversarial attacks on influence maximization under dynamic influence propagation models in social networks. In particular, given a known seed set S, the problem is to minimize the influence spread from S by deleting a limited number of nodes and edges. This problem reflects many application scenarios, such as blocking virus (e.g. COVID-19) propagation in social networks by quarantine and vaccination, blocking rumor spread by freezing fake accounts, or attacking competitor's influence by incentivizing some users to ignore the information from the competitor. In this paper, under the linear threshold model, we adapt the reverse influence sampling approach and provide efficient algorithms of sampling valid reverse reachable paths to solve the problem. We present three different design choices on reverse sampling, which all guarantee $1/2 - \varepsilon$ approximation (for any small $\varepsilon >0$) and an efficient running time.
