Abstract
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.