Detecting misinformation in online social networks before it is too late
Detecting misinformation in online social networks before it is too late
复制标题
在为时已晚之前检测在线社交网络中的错误信息
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
M. Thai
中科院分区：
文献类型：
--
作者：
Huiling Zhang;Alan Kuhnle;Huiyuan Zhang;M. Thai
虽然在线社交网络提供了对大量信息源的访问，但它们也使虚假或不准确内容得以广泛传播。错误信息传播所造成的不良后果使其及时检测成为当务之急。一个重要的问题是，需要多少监测员才能在早期阶段发现所有错误信息级联。为了回答这个问题，我们定义了一个时间约束的错误信息检测（TCMD）问题。正如我们已经证明的那样，TCMD问题不存在多项式时间的（1 - ε）ln n-近似。大量独立的错误信息级联和异构延迟使得错误信息检测更具挑战性。我们的方法包括随机规划和O（ln（1 + n））的近似算法的单跳检测。这种方法可以提供一般检测所需监视器数量的下限。此外，我们提出了一种基于网络压缩的解决方案，其有效性得到了广泛的实验结果的验证。
While online social networks provide access to a massive information source, they also enable wide dissemination of false or inaccurate content. Undesirable results caused by misinformation propagation make its timely detection very imperative. An important question is how many monitors are required to detect all misinformation cascades at their early stage. To answer this question, we define a Time Constrained Misinformation Detection (TCMD) problem. As we have proved, there is no polynomial time (1 - ε) ln n-approximation for the TCMD problem. The large number of independent misinformation cascades and heterogeneous delays make misinformation detection more challenging. Our approach includes stochastic programming and an O(ln(1 + n)) approximation algorithm for one-hop detection. This approach can provide a lower bound on the number of required monitors for general detection. Furthermore, we propose a network-compression based solution, whose effectiveness is validated by extensive experimental results.