document: Limiting the spread of misinformation in social networks In this work , we study the notion of competing campaigns in a social network and address the problem of influence limitation where a `` bad '' campaign starts propagating from a certain node in the network and use the notion of limiting campaigns to counteract the effect of misinformation . The problem can be summarized as identifying a subset of individuals that need to be convinced to adopt the competing ( or `` good '' ) campaign so as to minimize the number of people that adopt the `` bad '' campaign at the end of both propagation processes . We show that this optimization problem is NP-hard and provide approximation guarantees for a greedy solution for various definitions of this problem by proving that they are submodular . We experimentally compare the performance of the greedy method to various heuristics . The experiments reveal that in most cases inexpensive heuristics such as degree centrality compare well with the greedy approach . We also study the influence limitation problem in the presence of missing data where the current states of nodes in the network are only known with a certain probability and show that prediction in this setting is a supermodular problem . We propose a prediction algorithm that is based on generating random spanning trees and evaluate the performance of this approach . The experiments reveal that using the prediction algorithm , we are able to tolerate about 90 % missing data before the performance of the algorithm starts degrading and even with large amounts of missing data the performance degrades only to 75 % of the performance that would be achieved with complete data .
doc_bio_tags: O O O O B O B I O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O