Monitor placement to timely detect misinformation in Online Social Networks

Online Social Networks (OSNs), such as Facebook, Twitter and Google+, facilitate the interactions and communications among people. However, they also make it a fertile land for misinformation to rapidly spread out, which may lead to detrimental consequences. Thus it is imperative to detect the misinformation propagating through OSNs by placing monitors. In this paper, we first study a general misinformation detection problem and show its equivalence to the influence maximization problem. Moreover, in order to prevent misinformation from reaching specific users, we define a τ-Monitor Placement problem for cases where the partial knowledge of misinformation sources is available. We prove the #P complexity of this problem and additionally propose an efficient algorithm to solve it. Extensive experiments on real-world data show the effectiveness of our proposed algorithm with respect to minimizing the number of monitors.