  In this work, we consider misinformation propagating through a social network
and study the problem of its prevention. In this problem, a "bad" campaign
starts propagating from a set of seed nodes in the network and we use the
notion of a limiting (or "good") campaign to counteract the effect of
misinformation. The goal is to identify a set of $k$ users that need to be
convinced to adopt the limiting campaign so as to minimize the number of people
that adopt the "bad" campaign at the end of both propagation processes.
  This work presents \emph{RPS} (Reverse Prevention Sampling), an algorithm
that provides a scalable solution to the misinformation mitigation problem. Our
theoretical analysis shows that \emph{RPS} runs in $O((k + l)(n + m)(\frac{1}{1
- \gamma}) \log n / \epsilon^2 )$ expected time and returns a $(1 - 1/e -
\epsilon)$-approximate solution with at least $1 - n^{-l}$ probability (where
$\gamma$ is a typically small network parameter and $l$ is a confidence
parameter). The time complexity of \emph{RPS} substantially improves upon the
previously best-known algorithms that run in time $\Omega(m n k \cdot
POLY(\epsilon^{-1}))$. We experimentally evaluate \emph{RPS} on large datasets
and show that it outperforms the state-of-the-art solution by several orders of
magnitude in terms of running time. This demonstrates that misinformation
mitigation can be made practical while still offering strong theoretical
guarantees.
