Influence maximization, defined by Kempe, Kleinberg, and Tardos (2003), is the
problem of finding a small set of seed nodes in a social network that maximizes
the spread of influence under certain influence cascade models. In this paper,
we propose an extension to the independent cascade model that incorporates the
emergence and propagation of negative opinions. The new model has an explicit
parameter called quality factor to model the natural behavior of people turning
negative to a product due to product defects. Our model incorporates negativity
bias (negative opinions usually dominate over positive opinions) commonly
acknowledged in the social psychology literature. The model maintains some nice
properties such as submodularity, which allows a greedy approximation algorithm
for maximizing positive influence within a ratio of 1-1/e. We define a quality
sensitivity ratio (qs-ratio) of influence graphs and show a tight bound of
*Θ(√n/k)* on the qs-ratio, where n is the number of nodes in the
network and k is the number of seeds selected, which indicates that seed
selection is sensitive to the quality factor for general graphs. We design an
efficient algorithm to compute influence in tree structures, which is nontrivial
due to the negativity bias in the model. We use this algorithm as the core to
build a heuristic algorithm for influence maximization for general graphs.
Through simulations, we show that our heuristic algorithm has matching influence
with a standard greedy approximation algorithm while being orders of magnitude
faster.