Robust misinformation prevention with uncertainty on suspicious nodes.

The misinformation prevention (MP) problem, which aims to find anchor nodes (P-seeds) to start an anti-spread of positive information, has attracted abundant research attention due to its practical application in reducing the risk of social unrest. Existing MP researches ideally assume that the M-seeds (nodes start misinformation spread) are known in advance. However, the misinformation spread usually occurs abruptly so that M-seeds are not easy to be identified as prior knowledge. In this paper, we study the MP problem with uncertain M-seeds. We assume that only a set of suspicious nodes (S-nodes) is known. Each S-node has a transition probability (T-prob) for becoming an M-seed. With different T-prob availability, we propose and study two new research problems: (1) the probabilistic MP (PMP) problem given exactly all the T-probs, and (2) the robust MP (RMP) problem given a confidence interval for each T-prob. For the PMP problem, we propose the prefixed Hybrid sampling based Misinformation Prevention (pHMP) algorithm that return a (1 − 1 / e − ɛ) -approximate solution. For the RMP problem, we optimize the worst-case ratio between the current solution and the optimal one. Two bi-criteria algorithms are proposed that achieve both δ absolute error and (1 − 1 / e − ɛ) 2 (1 − η) and (1 − 1 / e − ɛ) (1 − η) relative error respectively. We conduct extensive experiments on several real world datasets. The results show the proposed algorithms are superior over the baseline algorithm on all datasets, and robust against the changing of different application conditions. [ABSTRACT FROM AUTHOR]