Maximizing the Spread of Inuence through a Social
Network
David Kempe
Dept. of Computer Science
Cornell University, Ithaca NY
kempe@cs.cornell.edu
Jon Kleinbergy
Dept. of Computer Science
Cornell University, Ithaca NY
kleinber@cs.cornell.edu
·Eva Tardos
z
Dept. of Computer Science
Cornell University, Ithaca NY
eva@cs.cornell.edu
ABSTRACT
Models for the processes by which ideas and inuence propagate
through a social network have been studied in a number of do-
mains, including the diffusion of medical and technological innova-
tions, the sudden and widespread adoption of various strategies in
game-theoretic settings, and the effects of “word of mouth” in the
promotion of new products. Recently, motivated by the design of
viral marketing strategies, Domingos and Richardson posed a fun-
damental algorithmic problem for such social network processes:
if we can try to convince a subset of individuals to adopt a new
product or innovation, and the goal is to trigger a large cascade of
further adoptions, which set of individuals should we target?
We consider this problem in several of the most widely studied
models in social network analysis. The optimization problem of
selecting the most inuential nodes is NP-hard here, and we pro-
vide the rst provable approximation guarantees for efcient algo-
rithms. Using an analysis framework based on submodular func-
tions, we show that a natural greedy strategy obtains a solution that
is provably within 63% of optimal for several classes of models;
our framework suggests a general approach for reasoning about the
performance guarantees of algorithms for these types of inuence
problems in social networks.
We also provide computational experiments on large collabora-
tion networks, showing that in addition to their provable guaran-
tees, our approximation algorithms signicantly out-perform node-
selection heuristics based on the well-studied notions of degree
centrality and distance centrality from the eld of social networks.
Categories and Subject Descriptors
F.2.2 [A