Report ID
2010-02
Report Date
Abstract
In this work, we study the notion of competing campaigns
in a social network. By modeling the spread of influence
in the presence of competing campaigns, we provide neces-
sary tools for applications such as emergency response where
the goal is to limit the spread of misinformation. We study
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 iden-
tifying 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 op-
timization problem is NP-hard and provide approximation
guarantees for a greedy solution for various definitions of this
problem by proving that they are submodular. Although the
greedy algorithm is a polynomial time algorithm, for today’s
large scale social networks even this solution is computation-
ally very expensive. Therefore, we study the performance of
the degree centrality heuristic as well as other heuristics that
have implications on our specific problem. The experiments
on a number of close-knit regional networks obtained from
the Facebook social network show that in most cases inex-
pensive heuristics do in fact compare well with the greedy
approach.
Document
2010-02.pdf423.74 KB