Theory of Computing
-------------------
Title     : Maximizing the Spread of Influence through a Social Network
Authors   : David Kempe, Jon Kleinberg, and Eva Tardos
Volume    : 11
Number    : 4
Pages     : 105-147
URL       : https://theoryofcomputing.org/articles/v011a004

Abstract
--------

Models for the processes by which ideas and influence propagate
through a social network have been studied in a number of domains,
including the diffusion of medical and technological innovations, 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. Motivated by the design of viral marketing strategies,
Domingos and Richardson posed a fundamental 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 influential nodes is NP-hard here.  The two
conference papers upon which this article is based (KDD 2003 and
ICALP 2005) provide the first provable approximation guarantees for
efficient algorithms.  Using an analysis framework based on
submodular functions, 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 influence problems in social
networks.

We also provide computational experiments on large collaboration
networks, showing that in addition to their provable guarantees,
our approximation algorithms significantly out-perform
node-selection heuristics based on the well-studied notions of
degree centrality and distance centrality from the field of social
networks.

The present article is an expanded version of two conference papers
which appeared in KDD 2003 and ICALP 2005, respectively.