On Misinformation Containment in Online Social Networks
The widespread online misinformation could cause public panic and serious economic damages. The misinformation containment problem aims at limiting the spread of misinformation in online social networks by launching competing campaigns. Motivated by realistic scenarios, we present an analysis of the misinformation containment problem for the case when an arbitrary number of cascades are allowed. This paper makes four contributions. First, we provide a formal model for multi-cascade diffusion and introduce an important concept called as cascade priority. Second, we show that the misinformation containment problem cannot be approximated within a factor of Ω(2 log 1− n 4 ) in polynomial time unless N P ⊆ DT IM E(n polylog n ). Third, we introduce several types of cascade priority that are frequently seen in real social networks. Finally, we design novel algorithms for solving the misinformation containment problem. The effectiveness of the proposed algorithm is supported by encouraging experimental results.
This paper addresses the problem of minimizing the effect of negative (e.g., false, harmful) information cascades in online social networks, i.e. misinformation containment. In particular, they consider the case of an arbitrary number of cascades, whereas most prior work in NIPS, KDD, INFOCOM, etc. have focused on the cases of one or two cascades. The authors provide a formal model for multi-cascade influence diffusion and cascade priority (Section 3), design an algorithm for minimizing the number of affected nodes (Section 5), provide theoretical bounds in terms of runtime and optimality (Section 4), and demonstrate the superiority of their algorithm against baselines on real-world datasets.  Overall, I think this is a very good submission. The authors provide clear motivation for the multi-cascade misinformation problem, rigorous theory around the proposed algorithm, and a reasonably comprehensive set of experiments on three real-world datasets. The paper is both original and significant because at least to my knowledge, the multi-cascade problem in online social networks has not been mathematically modeled before. Further, the paper is well written, with all ideas and even theorems explained with clarity. For these reasons, I recommend accepting the paper.  At the same time, I also found two areas for improvement. First, I would encourage the authors to consider a more comprehensive set of propagation probabilities in the experimentation. As it stands, it seems that these are set deterministically based on the observed social network, e.g., the number of activities observed from u to v and the out degree of particular nodes. This is not likely to capture nuances in how people influence one another, though, including the susceptibility of individuals, the influential power of individuals, and the fraction of interactions that are actually attempting to spread information. There is of course no way to account for all of these factors, but one idea would be to add random Gaussian noise on each of the link weights, and average the results over multiple trials, to see how robust the algorithms are to fluctuations. Another possibility would be to weight each of the probabilities by a measure of importance of the root node, like their social centrality.  Second, I feel that the authors refer to the supplemental material too often. To rectify this, I would suggest moving Section 4 and a few of the less important theorems entirely to the supplemental material, and instead including more of the proofs from Sections 3 and 5 in the manuscript itself. This way the paper would be more self-contained, and the reader does not have to flip back and forth between the paper and the supplement as much.