Mathematics

Dr. Venkatesh Srinivasan
University of Victoria, Canada

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 then to identify a subset 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.

We present  "Reverse Prevention Sampling (RPS)", an algorithm that provides a scalable solution to the misinformation prevention problem. Our theoretical analysis shows that RPS returns a good approximate solution with high probability. Furthermore, the time complexity of RPS substantially improves upon the previously best-known algorithm for this problem. 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. Our work demonstrates that misinformation prevention can be made practical while still offering strong theoretical guarantees.

(Joint work with Michael Simpson and Alex Thomo, University of Victoria)