On Misinformation Containment in Online Social Networks
On Misinformation Containment in Online Social Networks
复制标题
DOI：
--
复制
发表时间：
2018-09
期刊：
影响因子：
--
通讯作者：
G. Tong;Weili Wu;D. Du
中科院分区：
文献类型：
--
作者：
G. Tong;Weili Wu;D. Du
网上广泛传播的错误信息可能会造成公众恐慌和严重的经济损失。遏制虚假信息问题旨在通过发起竞争运动，限制虚假信息在在线社交网络中的传播。在现实场景的激励下，我们首次分析了当允许任意数量的级联时的错误信息遏制问题。本文有四个贡献。首先，我们提供了一个多级联扩散的形式化模型，并引入了一个重要的概念，称为级联优先级。其次，我们表明，除非$NP \subseteq DTIME(n^{\polylog{n}})$，否则错误信息遏制问题不能在多项式时间内近似于$\Omega(2^{\log^{1-\epsilon}n^4})$因子。第三，我们介绍了在现实社交网络中常见的几种级联优先级。最后，我们设计了新的算法来解决错误信息的遏制问题。实验结果证明了该算法的有效性。
The widespread online misinformation could cause public panic and serious economic damages. The misinformation containment problem aims at limiting the spread of misinformation in online social networks by launching competing campaigns. Motivated by realistic scenarios, we present the first analysis of the misinformation containment problem for the case when an arbitrary number of cascades are allowed. This paper makes four contributions. First, we provide a formal model for multi-cascade diffusion and introduce an important concept called as cascade priority. Second, we show that the misinformation containment problem cannot be approximated within a factor of $\Omega(2^{\log^{1-\epsilon}n^4})$ in polynomial time unless $NP \subseteq DTIME(n^{\polylog{n}})$. Third, we introduce several types of cascade priority that are frequently seen in real social networks. Finally, we design novel algorithms for solving the misinformation containment problem. The effectiveness of the proposed algorithm is supported by encouraging experimental results.