Scalable Misinformation Mitigation in Social Networks Using Reverse Sampling.

We consider misinformation propagating through a social network and study the problem of its prevention. The goal is to identify a set of |$k$| users that need to be convinced to adopt a limiting campaign so as to minimize the number of people that end up adopting the misinformation. This work presents Reverse Prevention Sampling (RPS), an algorithm that provides a scalable solution to the misinformation mitigation problem. Our theoretical analysis shows that 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 RPS substantially improves upon the previously best-known algorithms that run in time |$\Omega (m n k \cdot POLY(\epsilon ^{-1}))$|⁠. We experimentally evaluate 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. [ABSTRACT FROM AUTHOR]