Reverse Prevention Sampling for Misinformation Mitigation in Social Networks. 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.  :92,work presents emphRPS (Reverse Prevention Sampling), an algorithm that provides a scalable solution to the misinformation mitigation problem. Our theoretical analysis shows that emphRPS runs in O((k  l)(n  m)(frac11  gamma) log n  epsilon2 ) expected time and returns a (1  1e  epsilon)approximate solution with at least 1  nl probability (where gamma is a typically small network parameter and l is a confidence parameter). The time complexity of emphRPS substantially improves upon the previously bestknown algorithms that run in time Omega(m n k cdot POLY(epsilon1)). We experimentally evaluate emphRPS on large datasets and show that it outperforms the stateoftheart 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.

Latencybounded Target Set Selection in Signed Networks It is welldocumented that social networks play a considerable role in information spreading. The dynamic processes governing the diffusion of information have been studied in many fields, including epidemiology, sociology, economics, and computer science. A widely studied problem in the area of viral marketing is the target set selection: in order to market a new product, hoping it will be adopted by a large fraction of individuals in the network, which set of individuals should we xe2x80x9ctargetxe2x80x9d (for instance, by offering them free samples of the product)? In this paper, we introduce a diffusion model in which some of the neighbors of a node have a negative influence on that node, namely, they induce the node to reject the feature that is supposed to be spread. We study the target set selection problem within this model, first proving a strong inapproximability result holding also when the diffusion process is required to reach all the nodes in a couple of rounds. Then, we consider a set of restrictions under which the problem is approximable to some extent.