Limiting the Spread of Misinformation in Social Networks
Conference, 20th International World Wide Web Conference (WWW 2011), Hyderabad, India - March 28 - April 01, 2011, page 665--674. New York, NY, USA, ACM, (2011)Abstract
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.
