Maximizing Social Influence in Nearly Optimal Time

arXiv:1212.0884v5 [] 22 Jun 2016

Christian Borgs∗

Michael Brautbar†

Jennifer Chayes‡

Brendan Lucier§

Abstract
Diffusion is a fundamental graph process, underpinning such phenomena as epidemic disease
contagion and the spread of innovation by word-of-mouth. We address the algorithmic problem
of finding a set of k initial seed nodes in a network so that the expected size of the resulting
cascade is maximized, under the standard independent cascade model of network diffusion.
Runtime is a primary consideration for this problem due to the massive size of the relevant
input networks.
We provide a fast algorithm for the influence maximization problem, obtaining the nearoptimal approximation factor of (1 − 1e − ǫ), for any ǫ > 0, in time O((m + n)kǫ−2 log n). Our
algorithm is runtime-optimal (up to a logarithmic factor) with respect to network size, and
substantially improves upon the previously best-known algorithms which run in time Ω(mnk ·
POLY(ǫ−1 )). Furthermore, our algorithm can be modified to allow early termination: if it is
terminated after O(β(m + n)k log n) steps for some β < 1 (which can depend on n), then it
returns a solution with approximation factor O(β). Finally, we show that this runtime is optimal
(up to logarithmic factors) for any β and fixed seed size k.

∗

Microsoft Research New England.
Computer and Information Science, University of Pennsylvania. Now at Toast, Inc.
‡
Microsoft Research New England.
§
Microsoft Research New England.

†

0

1

Introduction

Diffusion is a fundamental process in the study of complex networks, modeling the spread of disease,
ideas, or product adoption through a population. The common feature in each case is that local
interactions between individuals can lead to epidemic outcomes. This is the idea behind wordof-mouth advertising, in which information about a product travels via links between individuals
[35, 8, 17, 9, 3, 10, 19]. A prominent application is a viral marketing campaign which aims to use a
small number of targeted interventions to initiate cascades of influence that create a global increase
in product adoption [16, 23, 26, 17].
This application gives rise to an algorithmic problem: given a network, how can we determine
which individuals should be targeted to maximize the magnitude of a resulting cascade [16, 34, 23]?
Supposing that there is a limit k on the number of nodes to target (e.g. due to advertising budgets),
the goal is to efficiently find an appropriate set of k nodes with which to “seed” a diffusion process.
This problem has been studied for various models of influence spread, leading to the development
of polynomial-time algorithms that achieve constant approximations [23, 24, 32].
Relevant networks for this problem can have massive size, on the order of billions of edges. The
running time of an influence maximization algorithm is therefore a primary consideration. This
is compounded by the fact that social network data and influence parameters tend to be volatile,
necessitating recomputation of solutions over time. For these reasons, near-linear runtime is a
practical necessity for algorithms that work with massive network data. This stringent runtime
requirement has spawned a large body of work aimed at developing fast, heuristic methods of
finding influential individuals in social networks, despite the existence of the above-mentioned
approximation algorithms [13, 12, 14, 27, 38, 30, 22, 25]. However, to date, this line of work has
focused primarily on empirical methods. Currently, the fastest algorithms with constant-factor
approximation guarantees have runtime Ω(nmk) [13].
In this paper we bridge this gap by developing a constant-factor approximation algorithm for
the influence maximization problem, under the standard independent cascade model of influence
spread, that runs in quasilinear time. Our algorithm can also be modified to run in sublinear time,
with a correspondingly reduced approximation factor. Before describing these results in detail, we
first provide some background into the influence model.
The Model: Independent Cascades We adopt the independent cascade (IC) model of diffusion, formalized by Kempe et al. [23]. In this model we are given a directed edge-weighted graph
G with n nodes and m edges, representing the underlying network. Influence spreads via a random
process that begins at a set S of seed nodes. Each node, once infected, has a chance of subsequently
infecting its neighbors: the weight of edge e = (v, u) represents the probability that the process
spreads along edge e from v to u. If we write I(S) for the (random) number of nodes that are
eventually infected by this process, then we think of the expectation of I(S) as the influence of set
S. Our optimization problem, then, is to find set S maximizing E[I(S)] subject to |S| ≤ k.
The IC model captures the intuition that influence can spread stochastically through a network,
much like a disease [23, 17, 15]. Since its introduction, it has become one of the prominent models
of influence spread; see for example [13, 12, 14, 27, 38, 24]. Kempe et al. show that E[I(·)] is a
submodular monotone function [23], and hence the problem of maximizing E[I(·)] can be approximated to within a factor of (1 − 1e − ǫ) for any ǫ > 0, in polynomial time, via a greedy hill-climbing
method. In contrast, many other formulations of the influence maximization problem have been
shown to have strong lower bounds on polynomial-time approximability [33, 31, 11, 4].
The greedy approach to maximizing influence in the IC model described above takes time O(kn),
given oracle access to the function E[I(·)]. However, influence values must be computed from the
1

underlying network topology, by (for example) repeated simulation of the diffusion process. This
leads ultimately1 to a runtime2 of Ω(mnk · POLY(ǫ−1 )).
Our Result: A Quasi-Linear Time Algorithm Our main result is an algorithm for finding
(1 − 1e − ǫ)-approximately optimal seed sets in arbitrary directed networks, which runs in time
O((m + n)kǫ−2 log n). This runtime is close to optimal with respect to network size, as we give a
lower bound of Ω(m + n) on the time required to obtain a constant approximation, assuming an
adjacency list representation of the network as well as the the ability to uniformly sample nodes.
We also note that this approximation factor is nearly optimal, as no polytime algorithm achieves
approximation (1 − 1e + ǫ) for any ǫ > 0 unless P = NP [23, 24]. Our algorithm is randomized, and
it succeeds with probability 3/5; moreover, failure is detectable, so this success probability can be
amplified through repetition.
We assume that the network topology is described in the sparse representation of an (arbitrarily
ordered) adjacency list for each vertex, as is natural for sparse graphs such as social networks.
Our algorithms access the network structure in a very limited way: the only queries used by our
algorithms are uniform vertex sampling and traversing the edges incident to a previously-accessed
vertex.
To describe our approach, let us first consider the problem of finding the single node with
highest influence. One strategy would be to estimate the influence of every node directly, e.g., via
repeated simulation, but this is computationally expensive. Alternatively, consider the following
“polling” process: select a node v uniformly at random, and determine the set of nodes that would
have influenced v. Intuitively, if we repeat this process multiple times, and a certain node u appears
often as an “influencer,” then u is likely a good candidate for the most influential node. Indeed,
we show that the probability a node u appears in a set of influencers is proportional to E[I(u)],
and standard concentration bounds show that this probability can be estimated accurately with
relatively few repetitions of the polling process. Moreover, it is possible to efficiently find the set of
nodes that would have influenced a node v: this can be done by simulating the influence process,
starting from v, in the transpose graph (i.e., the original network with edge directions reversed).
This motivates our algorithm, which proceeds in two steps. First, we repeatedly apply the
random sampling technique described above to generate a sparse hypergraph representation of
the network. Each hypergraph edge corresponds to a set of individuals that was influenced by a
randomly selected node in the transpose graph. This preprocessing is done once, resulting in a
structure of size O((m + n)kǫ−2 log(n)). This hypergraph encodes our influence estimates: for a set
of nodes S, the total degree of S in the hypergraph is approximately proportional to the influence of
S in the original graph. In the second step, we run a standard greedy algorithm on this hypergraph
to return a set of size k of approximately maximal total degree.
To make this approach work one needs to overcome several inherent difficulties. First, note that
our sampling method allows us to estimate the influence of a node, but not the marginal benefit
of adding a node to a partially constructed seed set. Thus, unlike prior algorithms, we do not
repeat our estimation procedure to incrementally construct a solution. Instead, we perform all of
our sampling up front and then select the entire seed set using the resulting hypergraph.
Second, our algorithm has a stringent runtime constraint — we must construct our hypergraph
in time O((m+n)kǫ−2 log(n)). To meet this bound, we must be flexible in the number of hyperedges
we construct. Instead of building a certain fixed number of hyperedges, we repeatedly build edges
1

After simple optimizations, such as reusing simulations for multiple nodes.
The best implementations appear to have running time O(mnk log(n) · POLY(ǫ−1 )) [13], though to the best of
our knowledge a formal analysis of this runtime has not appeared in the literature.
2

2

until the total sum of all edge sizes exceeds O((m + n)kǫ−2 log(n)). Intuitively speaking, this
works because the number of hyperedges needed to accurately estimate influence values, times
the expected size of each hyperedge, is roughly constant. Indeed, we should expect to see large
hyperedges only if the network contains many influential nodes, but high influence values require
fewer samples to estimate accurately.
Finally, in order to prevent errors from accumulating when we apply the greedy algorithm to
the hypergraph, it is important that our estimator for the influence function (i.e. total hypergraph
degree) is itself a monotone submodular function.
Early Termination and Sublinear Time We next show how to modify our approximation
algorithm to allow early termination, providing a tradeoff between runtime and approximation
quality. Specifically, if the algorithm is allowed to run for O(β(n + m)k log(n)) steps, and is then
terminated without warning, it can immediately return a solution with approximation factor O(β).
We also provide a lower bound of Ω(max{β 2 , βk } · (m + n)) on the runtime needed to obtain an
O(β)-approximation. Our algorithm is therefore nearly runtime-optimal (up to logarithmic factors)
for any fixed seed size k < β −1 . Our method is randomized, and it succeeds with probability 3/5.
As before, these results assume that the input network is provided in adjacency list format and an
algorithm is allowed to perform uniform sampling of the nodes. Notably, our algorithm accesses
the network structure in a very limited way and is directly implementable (with no additional cost)
in a wide array of graph access models, including the ones used for sublinear-time and property
testing algorithms on sparse graphs [36, 18] and the jump and crawl paradigm of [7].
The intuition behind our modified algorithm is that a tradeoff between execution time and
approximation factor can be achieved by constructing fewer edges in our hypergraph representation.
Given an upper bound on runtime, we can build edges until that time has expired, then run the
influence maximization algorithm using the resulting (impoverished) hypergraph. We show that
this approach generates a solution whose quality degrades gracefully with the preprocessing time,
with an important caveat. If the network contains many nodes with high influence, it may be that
a reduction in runtime prevents us from achieving enough concentration to estimate the influence
of any node. However, in this case, the fact that many individuals have high influence enables an
alternative approach: a node chosen at random, according to the degree distribution of nodes in
the hypergraph representation, is likely to have high influence.
Given the above, our algorithm will proceed by constructing two possible seed sets: one using
the greedy algorithm applied to the constructed hypergraph, and the other by randomly selecting
a singleton according to the hypergraph degree distribution. If k > 1 we will return a union of
these two solutions. When k = 1 we cannot use both solutions, so we must choose; in this case, it
turns out that we can determine which of the two solutions will achieve the desired approximation
by examining the maximum degree in the hypergraph.
Finally, to allow early termination without warning, the algorithm can pause its hypergraph
construction and compute a tentative solution at predetermined intervals (e.g., repeatedly doubling
the number of steps between computations). Then, upon a request to terminate, the algorithm
returns the most recent solution.

1.1

Related Work

Models of influence spread in networks, covering both cascade and threshold phenomena, are wellstudied in the sociology and marketing literature [21, 35, 17]. The problem of finding the most
influential set of nodes to target for a diffusive process was first posed by Domingos and Richardson

3

[16, 34]. A formal development of the IC model, along with a greedy algorithm based upon submodular maximization, was given by Kempe et al. [23]. Many subsequent works have studied the
nature of diffusion in online social networks, using empirical data to estimate influence probabilities
and infer network topology; see [29, 19, 28].
It has been shown that many alternative formulations of the influence maximization problem
are computationally difficult. The problem of finding, in a linear threshold model, a set of minimal
size that influences the entire network was shown to be inapproximable within O(n1−ǫ ) by Chen
[11]. The problem of determining influence spread given a seed set in the IC model is #P-hard [12].
There has been a line of work aimed at improving the runtime of the algorithm by Kempe et
al. [23]. These have focused largely on heuristics, such as assuming that all nodes have relatively
low influence or that the input graph is clustered [12, 14, 25, 38], as well as empirically-motivated
implementation improvements [27, 13]. One particular approach of note involves first attempting to
sparsify the input graph, then estimating influence on the reduced network [14, 30]. Unfortunately,
these sparsification problems are shown to be computationally intractible in general.
Various alternative formulations of influence spread as a submodular process have been proposed
and analyzed in the literature [32, 24], including those that include interations between multiple
diffusive processes [20, 5]. We focus specifically on the IC model, and leave open the question of
whether our methods can be extended to apply to these alternative models.
The influence estimation problem shares some commonality with the problems of local graph
partitioning, as well as estimating pagerank and personalized pagerank vectors [1, 6, 37, 2]. These
problems admit local algorithms based on sampling short random walks. To the best of our understanding, these methods do not seem directly applicable to influence maximization.

2

Model and Preliminaries

The Independent Cascade Model In the independent cascade (IC) model, influence spreads
via an edge-weighted directed graph G. An infection begins at a set S of seed nodes, and spreads
through the network in rounds. Each infected node v has a single chance, upon first becoming
infected, of subsequently infecting his neighbors. Each directed edge e = (v, u) has a weight
pe ∈ [0, 1] representing the probability that the process spreads along edge e to node u in the round
following the round in which v was first infected.
As noted in [23], the above process has the following equivalent description. We can interpret
G as a distribution over unweighted directed graphs, where each edge e is independently realized
with probability pe . If we realize a graph g according to this probability distribution, then we can
associate the set of infected nodes in the original process with the set of nodes reachable from seed
set S in g. We will make use of this alternative formulation of the IC model throughout the paper.
Notation We let m and n denote the number of edges and nodes, respectively, in the weighted
directed graph G. We write g ∼ G to mean that g is drawn from the random graph distribution
G. Given set S of vertices and (unweighted) directed graph g, write Cg (S) for the set of nodes
reachable from S in g. When g is drawn from G, we will refer to this as the set of nodes influenced
by S. We write Ig (S) = |Cg (S)| for the number of nodes influenced by S, which we call the influence
of S in g. We write EG [I(S)] = Eg∼G [Ig (S)] for the expected influence of S in G.
Given two sets of nodes S and W , we write Cg (S|W ) for the set of nodes reachable from S but
not from W . That is, Cg (S|W ) = Cg (S) \ Cg (W ). As before, we write Ig (S|W ) = |Cg (S|W )|; we
refer to this as the marginal influence of S given W . The expected marginal influence of S given
W is EG [I(S|W )] = Eg∼G [Ig (S|W )].
4

In general, a vertex in the subscript of an expectation or probability denotes the vertex being
selected uniformly at random from the set of vertices of G. For example, Ev,G [I(v)] is the average,
over all graph nodes v, of the expected influence of v.
For a given graph g, define gT to be the transpose graph of g: (u, v) ∈ g iff (v, u) ∈ g T . We
apply this notation to both unweighted and weighted graphs.
The Influence Maximization Problem Given graph G and integer k ≥ 1, the influence maximization problem is to find a set S of at most k nodes maximizing the value of EG [I(S)]. Write
OPT = maxS:|S|=k {EG [I(S)]} for the maximum expected influence of any set of k nodes. For
β ≤ 1, we say that a particular set of nodes S with |S| ≤ k is a β-approximation to the influence
maximization problem if EG [I(S)] ≥ β · OPT. We assume that graph G is provided in adjacency
list format, with the neighbors of a given vertex v ordered arbitrarily.
A Simulation Primitive Our algorithms we will make use of a primitive that realizes an instance
of the nodes influenced by a given vertex u in weighted graph G, and returns this set of nodes.
Conceptually, this is done by realizing some g ∼ G and traversing Cg (u).
Let us briefly discuss the implementation of such a primitive. Given node u, we can run a depth
first search in G starting at node u. Before traversing any given edge e, we perform a random test:
with probability pe we traverse the edge as normal, and with probability 1 − pe we do not traverse
edge e and ignore it from that point onward. The set of nodes traversed in this manner is equivalent
to Cg (u) for g ∼ G, due to deferred randomness. We then return the set of nodes traversed. The
runtime of this procedure is precisely the sum of the degrees (in G) of the vertices in Cg (u).
We can implement this procedure for a traversal of g T , rather than g, by following in-links
rather than out-links in our tree traversal.

3

An Approximation Algorithm for Influence Maximization

In this section we present an algorithm for the influence maximization problem on arbitrary directed
graphs. Our algorithm returns a (1 − 1e − ǫ)-approximation to the influence maximization problem,
with success probability 3/5, in time O((m + n)kǫ−2 log n). We discuss how to amplify this success
probability in Section 3.1.
The algorithm is described formally as Algorithm 1, but let us begin by describing our construction informally. Our approach proceeds in two steps. The first step, BuildHypergraph, stochastically generates a sparse, undirected hypergraph representation H of our underlying graph g. This
is done by repeatedly simulating the influence spread process on the transpose of the input graph,
gT . This simulation process is performed as described in Section 2: we begin at a random node u
and proceed via depth-first search, where each encountered edge e is traversed independently with
probability pe . The set of nodes encountered becomes an edge in H. We then repeat this process,
generating multiple hyperedges. The BuildHypergraph subroutine takes as input a bound R on
its runtime; we continue building edges until a total of R steps has been taken by the simulation
process. As discussed in Section 2, the number of steps taken by the process is equal to the number
of edges considered by the depth-first search processes. Once R steps have been taken in total over
all simulations, we return the resulting hypergraph.
In the second step, BuildSeedSet, we use our hypergraph representation to construct our output
set. This is done by repeatedly choosing the node with highest degree in H, then removing that
node and all incident edges from H. The resulting set of k nodes is the generated seed set.

5

Algorithm 1 Maximize Influence
Require: Directed edge-weighted graph G, runtime bound R.
1: H ← BuildHypergraph(R)
2: return BuildSeedSet(H, k)
BuildHypergraph(R):
1: Initialize H = (V, ∅).
2: repeat
3:
Choose node u from G uniformly at random.
4:
Simulate influence spread, starting from u, in G T . Let Z be the set of nodes discovered.
5:
Add Z to the edge set of H.
6: until R steps have been taken in total by the simulation process.
7: return H
BuildSeedSet(H, k):
1: for i = 1, . . . , k do
2:
vi ← argmaxv {degH (v)}
3:
Remove vi and all incident edges from H
4: return {v1 , . . . , vk }
We now turn to provide a detailed analysis of Algorithm 1. Fix k and a weighted directed graph
G. For notational convenience we will assume m ≥ n, by adding edges of weight 0 if necessary.
Theorem 3.1. There exists a constant c such that, for any ǫ ∈ (0, 12 ), if we set R = cmkǫ−2 log(n)
then Algorithm 1 returns a set S with EG [I(S)] ≥ (1 − 1e − ǫ)OPT, with probability at least 3/5.
The runtime of Algorithm 1 is Θ(R) = Θ(mkǫ−2 log(n)).
The idea behind the proof of Theorem 3.1 is as follows. First, we observe that the influence of
a set of nodes S is precisely n times the probability that a node u, chosen uniformly at random,
influences a node from S in the transpose graph g T .
Observation 3.2. For each subset of nodes S ⊆ G, Eg∼G [Ig (S)] = n · Pru,g∼G [S ∩ CgT (u) 6= ∅].
Proof.
Eg∼G [Ig (S)] =

X

Prg∼G [∃v ∈ S such that u ∈ Cg (v)]

u∈g

=

X

Prg∼G [∃v ∈ S such that v ∈ CgT (u)]

u∈g

= nPru,g∼G [∃v ∈ S such that v ∈ CgT (u)]
= nPru,g∼G [S ∩ CgT (u) 6= ∅].

Observation 3.2 implies that we can estimate EG [I(S)] by estimating the probability of the event
S ∩ CgT (u) 6= ∅. The degree of a node v in H is precisely the number of times we observed that v
H (S)
was influenced by a randomly selected node u. We can therefore think of deg
m(H) , the fraction of
edges that intersect S, as an estimator for n1 ·EG [I(S)]. Our primary task is to show that it is a good
estimator. We do this in two steps: in Lemma 3.4 we show that m(H) (the number of iterations

6

taken by BuildHypergraph) is likely to be large, then in Lemma 3.5 we bound our estimation error
conditional on m(H) being large enough.
For establishing bounds on m(H), it will be convenient to denote by AVG the expected number
of steps taken by the simulation process on any given iteration of BuildHypergraph. That is, AVG
is the expected sum of degrees (in G T ) of nodes in CgT (u), where the expectation is over g ∼ G and
the uniform choice of u. The following technical lemma allows us to compare AVG (measured in
edges) to the optimal influence (measured in nodes).
Claim 3.3. AVG ≤

m
n OPT.

Proof. Given a vertex u and an edge e = (v, w), consider the random event indicating whether edge
e is checked as part of the process of growing a depth-first search rooted at u in the IC process
corresponding to graph g T ∼ G T . Note that edge e is checked if and only if node v is influenced
by node u in this invocation of the IC process. In other words, edge e = (v, w) is checked as part
of the influence spread process on line 4 of BuildHypergraph if and only if v ∈ Z. Write mgT (u)
for the random variable indicating the number of edges that are checked as part of building the
influence set Z starting at node u in g T . We then have
AVG =

1
1X
Eg∼G [mgT (u)] =
n
n
u∈G

X

e=(v,w)∈G T



Eg∼G |{u : v ∈ CgT (u)}| .

Noting that v ∈ CgT (u) if and only if u ∈ CgT (v), we then have
AVG =
=
≤

1
n
1
n
1
n

X

Eg∼G [|{u : u ∈ Cg (v)}|]

X

EG [I({v})]

X

OPT =

e=(v,w)∈G T

e=(v,w)∈G T

e=(v,w)∈G T

m
OPT
n

as required.



We will think of H as being built incrementally, one edge at a time, as in the execution of
BuildHypergraph. Since we will discuss the state of H at various points of execution, we will write
M for the number of edges in H when BuildHypergraph terminates. Note that M as a random
variable, corresponding to m(H) after BuildHypergraph has completed.
Lemma 3.4. With probability at least 1 −

2
,
nck/4(1+ǫ)

M satisfies

1
1+ǫ

·

R
AVG

≤M ≤

1
1−ǫ

·

R
AVG .

Proof. Write xi for the fraction of all edges in G that are checked as part of the ith iteration of
BuildHypergraph in Algorithm 1. That is, when building the ith hyperedge of H. Note then that
xi ∈ [0, 1] for all i, and E[xi ] = AVG
m for every i. Moreover, M is precisely the minimal value J such
PJ
that i=1 xi ≥ R/m.
1
R
1
R
Let J1 = 1+ǫ
· AVG
and J2 = 1−ǫ
· AVG
. We wish to show that, with high probability, M ∈ [J1 , J2 ].
P 1
P 2
This is equivalent to the intersection of events Ji=1
xi < R/m and Ji=1
xi > R/m. For the first
event, note that
#
"J
J1
1
X
X
R
AVG
=
.
(1)
E[xi ] = J1 ·
xi =
E
m
m(1 + ǫ)
i=1

i=1

7

Chernoff bounds then imply
##
#
"J
"J
"J
hP
i
1
1
1
J1
X
X
X
−ǫ2 ·E
i=1 xi /4
.
Pr
xi ≥ R/m = Pr
xi ≥ (1 + ǫ)E
xi < e
i=1

i=1

(2)

i=1

Substituting (1) into (2) and using R = cmkǫ−2 log(n), we obtain
Pr

"

J1
X

#

xi ≥ R/m < e−ǫ

i=1

2 ·(1+ǫ)−1 ckǫ−2 log(n)/4

<

1
.
nck/4(1+ǫ)

Applying an identical argument for J2 , we also have
#
"J
2
X
1
1
xi ≤ R/m < ck/2(1−ǫ) < ck/4(1+ǫ) .
Pr
n
n
i=1
Taking a union bound over the two events yields the desired bound.



We are now ready to show that the resulting hypergraph estimates the influence of each set
within a sufficiently small error. For a given integer J, Let DSJ be a random variable denoting the
degree of S in H after J edges have been added to H. We will allow J > M , by considering the
(hypothetical) path of execution of BuildHypergraph had there not been a runtime bound.
Lemma 3.5. For any J ≥

1
1+ǫ

·

R
AVG

and set of nodes S ⊆ V with |S| ≤ k,



1
ǫ · J · OPT
< ck/4(1+ǫ)
Pr DSJ > E[DSJ ] +
n
n
and
Pr



DSJ

<

E[DSJ ] −


ǫ · J · OPT
1
< ck/2(1+ǫ) .
n
n

(3)

(4)

Proof. We first show (3). Observation 3.2 implies that DSJ is the sum of J identically distributed
Bernoulli random variables, each with probability EG [I(S)]/n. Note that we must have E[DSJ ] ≤
J · OPT
n , with equality occuring for the set S of maximal influence. For notational convenience,
choose λ ∈ (0, 1] so that λ · E[DSJ ] = J·OPT
n . Then


h

ǫ   J i
ǫ · J · OPT
J
J
J
E DS .
= Pr DS > 1 +
Pr DS > E[DS ] +
n
λ
We consider two cases. First, if λ > ǫ, then ǫ/λ < 1, and the Multiplicative Chernoff bound (A.1)
implies that
h

ǫ   J i
2
2
J
E DS < e−ǫ ·E[DS ]/4λ .
Pr DSJ > 1 +
λ

Using the fact that E[DSJ ] =

J·OPT
λn

and J ≥

1
1+ǫ

·

R
AVG

=

cmkǫ−2 log n
AVG(1+ǫ) ,

we obtain

h

ǫ   J i
1
− mOPTck log n
Pr DSJ > 1 +
E DS < e 4(1+ǫ)λ3 nAVG ≤ e−ck log n/4(1+ǫ) = ck/4(1+ǫ)
λ
n

where the second inequality used Claim 3.3 and λ ≤ 1.
8

Next suppose λ ≤ ǫ. Then ǫ/λ ≥ 1, and the Chernoff bound implies
h

ǫ   J i
J
Pr DSJ > 1 +
E DS < e−ǫ·E[DS ]/3λ .
λ

Again using E[DSJ ] =

J·OPT
λn

and J ≥

cmkǫ−2 log n
AVG(1+ǫ) ,

we obtain

h

ǫ   J i
1
− mOPTck log n
Pr DSJ > 1 +
E DS < e 3(1+ǫ)λ2 nAVG < e−ck log n/3(1+ǫ) = ck/3(1+ǫ)
λ
n

where the second inequality used Claim 3.3 and λ ≤ 1. This completes the derivation of (3). The
derivation of (4) is similar, yielding


h

ǫ · J · OPT
ǫ   J i
J
J
Pr DS > E[DS ] −
E DS
= Pr DSJ > 1 −
n
λ
1
< ck/2(1+ǫ)
n
as required.



Finally, we must show that the greedy algorithm applied to H in BuildSeedSet returns a good
approximation to the original optimization problem. Recall that, in general, the greedy algorithm
for submodular function maximization proceeds by repeatedly selecting the singleton with maximal
contribution to the function value, up to the cardinality constraint. The following lemma shows
that if one submodular function is approximated sufficiently well by a distribution of submodular
functions, then applying the greedy algorithm to a function drawn from the distribution yields a
good approximation with respect to the original.
Lemma 3.6. Choose δ > 0 and suppose that f : 2V → R≥0 is an arbitrary function. Let D be a
distribution over functions with the property that, for all sets S with |S| ≤ k, Prfˆ∼D [|f (S)− fˆ(S)| >
δ] < 1/nk+ℓ . If we write S ˆ for the set returned by the greedy algorithm on input fˆ, then
f





Pr f (Sfˆ) < (1 − 1/e)
max f (S) − 2δ < 1/nℓ .

fˆ∼D

S : |S|=k

Proof. Taking a union bound over all sets of size at most k, of which there are at most nk , we have
Pr[∃S : |fˆ(S) − f (S)| > δ] ≤ nk · n−k−ℓ = 1/nℓ .
Conditioning on the event that |fˆ(S) − f (S)| ≤ δ for every set S of size at most k, we then have
f (Sfˆ) ≥ fˆ(Sfˆ) − δ ≥ (1 − 1/e)fˆ(S ∗ ) − δ ≥ (1 − 1/e)f (S ∗ ) − 2δ
as required.



We are now ready to complete our proof of Theorem 3.1.
R
1
· AVG
and J2 =
Proof of Theorem 3.1. As in the proof of Lemma 3.4, we will write J1 = 1+ǫ
R
1
1−ǫ · AVG . Condition on the event that M ∈ [J1 , J2 ], which (by Lemma 3.4) has probability
1
2
. We know from Lemma 3.5 that, with probability at least 1 − nck/4(1+ǫ)
,
at least 1 − nck/4(1+ǫ)

9

T
; we will condition on this event as well. Since DSM is dominated by DSJ2 ,
|DSJ2 − E[DSJ2 ]| < ǫ·J2 ·OP
n
and since J2 < 1+ǫ
1−ǫ J1 ≤ (1 + 4ǫ)M for ǫ ≤ 1/2, we conclude that

J2
ǫOP T
ǫOP T
J2 = E[DSM ] ·
+
J2
n
M
n
ǫOP T
M
< E[DSM ] + 4ǫ · E[DSM ] +
n
5ǫOP T
M.
< E[DSM ] +
n

DSM ≤ DSJ2 < E[DSJ2 ] +

T
Similarly, the fact that DSM dominates DSJ1 implies DSM > E[DSM ] − 5ǫOP
M , conditioning on an
n
1
event with probability at least 1 − nck/4(1+ǫ) . Taking the union bound over the complement of the
conditioned events, we conclude that


n · degH (S)
4
Pr EG [I(S)] −
> 5ǫOPT < ck/4(1+ǫ)
m(H)
n
H (S)
(drawn
for each S ⊆ V . We then apply Lemma 3.6 with f (S) := EG [I(S)], fˆ(S) := n·deg
m(H)
from then distribution corresponding to distribution of H returned by BuildHypergraph), and
ck
δ = 5ǫOPT. As long as 4(1+ǫ)
≥ k + 1, Lemma 3.6 implies that, with probability at least 1 − n1 ,
the greedy algorithm applied to H returns a set S with EG [I(S)] ≥ (1 − 1e )OPT − 10ǫOPT =
(1 − 1e − 10ǫ)OPT. Noting that this is precisely the set returned by BuildSeedSet gives the desired
bound on the approximation factor (rescaling ǫ by a constant factor). Thus the claim holds with
probability at least 2/3 − 1/n ≥ 3/5 (for n ≥ 20).
ck
≥ k + 1 is satisfied for c = 4(1 + ǫ)(1 + k1 ). We can therefore take this
Our condition 4(1+ǫ)
value of c in our definition of R.
Finally, we argue that our algorithm can be implemented in the appropriate runtime. The fact
that BuildHypergraph executes in the required time follows from the explicit bound on its runtime.
For BuildSeedSet, we will maintain a list of vertices sorted by their degree in H; this will allow us to
repeatedly select the maximum-degree node in constant time. The initial sort takes time O(n log n).
We must bound the time needed to remove an edge from H and correspondingly update the sorted
list. We will implement the sorted list as a doubly linked list of groups of vertices, where each
group itself is implemented as a doubly linked list containing all vertices of a given degree (with
only non-empty groups present). Each edge of H will maintain a list of pointers to its vertices.
When an edge is removed, the degree of each vertex in the edge decreases by 1; we modify the
list by shifting any decremented vertex to the preceding group (creating new groups and removing
empty groups as necessary). Removing an edge from H and updating the sorted list therefore takes
time proportional to the size of the edge. Since each edge in H can be removed at most once over
all iterations of BuildSeedSet, the total runtime is at most the sum of node degrees in H, which is
at most R.


3.1

Amplifying the Success Probability

Algorithm 1 returns a set of influence at least (1 − 1e − ǫ) with probability at least 3/5. The failure
probability is due to Lemma 3.4: hypergraph H may not have sufficiently many edges after R
steps have been taken by the simulation process in line 4 of the BuildHypergraph subprocedure.
However, note that this failure condition is detectable via repetition: we can repeat Algorithm 1
multiple times, and use only the iteration that generates the most edges. The success rate can then
be improved by repeated invocation, up to a maximum of 1 − 1/n with log(n) repetitions (at which
point the error probability due to Lemma 3.5 becomes dominant).
10

Algorithm 2 Runtime-Flexible Influence Maximization
Require: Directed edge-weighted graph G, runtime bound R, threshold C.
1: H ← BuildHypergraph(R)
2: Choose v ∈ V with probability proportional to degree in H
3: if k > 1 then
4:
S ← BuildSeedSet(H, k − 1)
5:
return S ∪ {v}
6: else
7:
S ← BuildSeedSet(H, 1)
8:
if maxu {degH (u)} > C then return S
9:
else return {v}
We next note that, for any ℓ > 1, the error bound in Lemma 3.5 can be improved to n1ℓ , by
increasing the value of R by a factor of ℓ, since this error derives from Chernoff bounds. This
would allow the success rate of the algorithm to be improved up to a maximum of 1 − n1ℓ by further
repeated invocation. To summarize, the error rate of the algorithm can be improved to 1 − n1ℓ for
any ℓ, at the cost of increasing the runtime of the algorithm by a factor of ℓ2 log(n).

4

Approximate Influence Maximization in Sublinear Time

We now describe a modified algorithm that provides a tradeoff between runtime and approximation
quality. For an an arbitrary β < 1, our algorithm will obtain an O(β)-approximation to the influence
maximization problem, in time O(β(n+m)k log(n)), with probability at least 3/5. In Section 4.1 we
describe an implementation of this algorithm that supports termination after an arbitrary number
of steps, rather than being given the value of β in advance.
Our algorithm is listed as Algorithm 2. The intuition behind our construction is as follows.
We wish to find a set of nodes with high expected influence. One approach would be to apply
Algorithm 1 and simply impose a tighter constraint on the amount of time that can be used to
construct hypergraph H. This might correspond to reducing the value of parameter R by, say, a
factor of β. Unfortunately, the precision of our sampling method does not always degrade gracefully
with fewer samples: if β is sufficiently small, we may not have enough data to guess at a maximuminfluence node (even if we allow ourselves a factor of β in the approximation ratio). In these cases,
the sampling approach fails to provide a good approximation.
However, as we will show, our sampling fails precisely because many of the edges in our hypergraph construction were large, and (with constant probability) this can occur only if many of the
nodes that make up those edges have high influence. In this case, we could proceed by selecting
a node from the hypergraph at random, with probability proportional to its hypergraph degree.
We prove that this procedure is likely to return a node of very high influence precisely in settings
where the original sampling approach would fail.
If k > 1, we can combine these two approaches by returning a union of vertices selected according
to each procedure. If k = 1, we must choose which approach to apply. However, in this case, there
is a simple way to determine whether we have obtained enough samples that BuildSeedSet returns
an acceptable solution: check whether the maximum degree in the hypergraph is sufficiently high.
Theorem 4.1. There exist constants c1 , c2 such that, for any β ∈ (0, 1), if we set R = c1 c2 βmk log(n)
and C = c2 log(n), then Algorithm 2 returns a set S with EG [I(S)] ≥ min{ 41 , β} · OPT, with probability at least 3/5. The runtime of Algorithm 2 is Θ(R) = Θ(βmk log(n)).
11

Our proof of Theorem 4.1 proceeds via two cases, depending on whether H has many or few
edges as a function of OPT. We first show that, subject to H having many edges, set S from line 5
or 8 (corresponding to k > 1 and k = 1, respectively) is likely to have high influence. This follows
the analysis from Theorem 3.1.
Lemma 4.2. Suppose constant c2 in the statement of Theorem 4.1 is sufficiently large. If m(H) ≥
c2 nk log(n)
, then the set S returned by Algorithm 2 satisfies EG [I(S)] ≥ 14 OPT with probability at
OPT
least 1 − n1 (over randomness in H).
log(n)
Proof. Suppose k = 1, so S is as defined on line 7. If we now apply Lemma 3.5 to J = c2 nk
,
OPT
taking ǫ = 16 , followed by the analysis of BuildSeedSet(H, k) from the proof of Theorem 3.1, we get
that EG [I(S)] ≥ 21 OPT, as required.
If k > 1, applying Lemma 3.5 with ǫ = 16 yields instead that EG [I(S)] ≥ 12 OPTk−1 , where
OPTk−1 is the maximum influence over sets of size at most k − 1. But now, by submodularity,
1 k−1
1
1

2 OPTk−1 ≥ 2 ( k )OPT ≥ 4 OPT, as required.

Note that β does not appear explicitly in the statement of Lemma 4.2. The (implicit) role of
β in Lemma 4.2 is that as β becomes small, Algorithm 2 uses fewer steps to construct hypergraph
H and hence the condition of the lemma is less likely to be satisfied. We next show that if m(H)
is small, then node v from line 3 is likely to have high influence. This follows because, in a small
number of edges, we do not expect to see many nodes with low influence. Since we see a large
number of nodes in total, we conclude that most of them must have high influence.
Lemma 4.3. Let c1 and c2 be the constants from the statement of Theorem 4.1 and suppose c1
log(n)
, then node v (from line 3 of Algorithm 2) satisfies
is sufficiently large. If m(H) < 4c2 nk
OP T
EG [I(v)] ≥ β · OPT with probability at least 2/3 (over randomness in H).
Proof. Let random variable X denote the number of times that a node with influence at most
log(n)
edges, the expected
β · OPT was added to a hyperedge of H. Since H has fewer than 4c2 nk
OPT
value of X is at most
4c2 nk log(n) X 1
E[X] ≤
min{EG [I(u)], β · OPT}
OPT
n
u∈V

≤ 4c2 βnk log(n).

Markov inequality then gives that Pr[X > 24c2 βnk log(n)] < 1/6. Conditioning on this event, we
have that at most 24c2 βnk log(n) of the nodes touched by BuildHypergraph (counted with multiplicity) have influence less than β · OPT. Note that drawing node v with probability proportional
to its degree is equivalent to drawing uniformly from all events in which a node is touched by
BuildHypergraph. Thus, since at least c1 c2 βnk log(n) nodes were touched in total, the probability
that node v from line 4 has influence less than β · OPT is at most 24/c1 . As long as c1 is sufficiently
large, this is at most 1/6. The union bound then allows us to conclude that v has E[I(v)] ≥ β · OPT
with probability at least 1 − (1/6 + 1/6) ≥ 2/3.

For the case k = 1, the algorithm chooses between returning S and returning {v}, based on
the maximum degree in H. The following lemma motivates this choice. The proof follows from an
application of concentration bounds: if a node is present in O(log n) hyperedges, then with high
probability we have obtained enough samples to accurately estimate its influence.
Lemma 4.4. If k = 1 then the following is true with probability at least 1− n2 . If maxu {degH (u)} >
log(n)
4c2 n log(n)
2c2 log n then m(H) > c2 nOP
.
T . Otherwise, m(H) <
OP T
12

Proof. As in the proof of Lemma 3.5, we will think of H as being built incrementally edge by edge,
J denote the degree of vertex w in H after J edges have been added. Then, for any
and we will let Dw
J
fixed J, Dw is precisely the sum of J Bernoulli random variables, each with expectation n1 EG [I(w)],
J ] = J E [I(w)].
and hence E[Dw
n G
J1 ] > 4c log n. Chernoff bounds imply
Let J1 be the smallest value such that E[Dw
2
J1
Pr[Dw
≤ 2c2 log n] < e−2 log n = 1/n2 .
J > D J1 > 2c log n. In
Suppose that this event does not occur. Then for any J ≥ J1 , we have Dw
2
w
m(H)
m(H)
particular, if E[Dw ] > 4c2 log n, we must have m(H) ≥ J1 , and hence Dw
> 2c2 log n.
J2 ] < c log n. Chernoff bounds again imply that
Let J2 be the largest value such that E[Dw
2
J2
Pr[Dw
≥ 2c2 log n] < e−2 log n = 1/n2 .
J < D J2 < 2c log n.
Suppose that this event does not occur. Then for any J ≤ J2 , we have Dw
2
w
m(H)
In particular, for any w such that E[Dw ] < c2 log n, we must have m(H) ≤ J2 , and hence
m(H)
Dw
< 2c2 log n.
Taking the union bound over all w, we conclude that with probability at least 1 − 2/n, only w
m(H)
m(H)
m(H)
≥ 2c2 log n.
for which E[Dw ] > c2 log n, and every w with E[Dw ] > 4c2 log n, will have Dw
We will condition on this event for the remainder of the proof.
m(H)
m(H)
Suppose that maxw Dw
< 2c2 log n. Then we have that maxw E[Dw ] < 4c2 log n. Since
m(H)
n log(n)
as
maxw E[Dw ] = maxw n1 m(H)EG [I(w)] = n1 m(H) · OP T , we conclude m(H) < 4c2OP
T
required.
m(H)
m(H)
Next suppose that maxw Dw
> 2c2 log n. We then have that maxw E[Dw ] > c2 log n.
m(H)
log(n)
as required.

Since, again, maxw E[Dw ] = n1 m(H) · OP T , we conclude m(H) > c2 nOP
T

We are now ready to complete the proof of Theorem 4.1.
Proof of Theorem 4.1. Lemma 4.2 and Lemma 4.3 imply that, with probability at least 2/3−1/n2 ≥
3/5 (for n ≥ 5), one of S or {v} has influence at least min{ 14 , β} · OP T , and therefore S ∪ {v} does
as well. If k > 1 then we return S ∪ {v} and we are done. Otherwise, Lemma 4.4 implies that if we
return set S then the influence of S is at least OP T /4 (by Lemma 4.2), and if we return set v then
the expected influence of v is at least β · OP T (by Lemma 4.3). Thus, in all cases, we return a set
of influence at least min{ 41 , β} · OP T . The required bound on the runtime of Algorithm 2 follows
directly from the value of R, as in the proof of Theorem 3.1.


4.1

Dynamic Runtime

Algorithm 2 assumes that the desired approximation factor, β, is provided as a parameter to the
problem. We note that a slight modification to the algorithm removes the requirement that β be
specified in advance. That is, we obtain an algorithm that can be terminated without warning, say
after O(γ · (n + m)k log(n)) steps for some γ ≤ 1, at which point it immediately returns a solution
that is an O(γ) approximation with probability at least 35 . To achieve this, we execute Algorithm 2
as though β = 1, but then modify BuildHypergraph so that, for each i ≥ 1, we pause the creation
of hypergraph H after 2i steps and complete the algorithm using the current hypergraph, which
takes time at most O(2i ). Once this is done, we save the resulting solution and resume the creation
of the hypergraph until the next power of 2. When the algorithm is terminated, we return the most
recently-computed solution; this corresponds to a solution for a hypergraph built using at least half
of the total steps taken by the algorithm at the time of termination. Theorem 4.1 then implies that
this solution has approximation O(γ) if termination occurs after O(γ · (n + m)k log(n)) steps.
13

4.2

A Lower Bound

We provide a lower bound on the time it takes for any algorithm, equipped with uniform node
sampling, to compute a β-approximation for the maximum expected influence problem under the
adjacency list network representation. In particular, for any given budget k, at least Ω(βn) queries
are required to obtain approximation factor β with fixed probability.
1
, β ≤ 1 be given. Any randomized algorithm for the maximum
Theorem 4.5. Let 0 < ǫ < 10e
β(m+n)
influence problem that has runtime of 24 min{k,1/β}
cannot return, with probability at least 1 − 1e − ǫ,
a set of nodes with approximation ratio better than β.

Proof. Note first that for a graph consisting of n singletons, an algorithm must return at least
βk nodes to obtain an approximation ratio of β. Doing so in at most β 2 n/2 queries requires that
2βk ≤ β 2 n, which implies 2k/β ≤ n. We can therefore assume 2k/β ≤ n.
The proof will use Yao’s Minimax Principle for the performance of Las Vegas (LV) randomized
algorithms on a family of inputs [39]. The lemma states that the least expected cost of deterministic
LV algorithms on a distribution over a family inputs is a lower bound on the expected cost of the
optimal randomized LV algorithm over that family of inputs. Define the cost of the algorithm as
0 if it returns a set nodes with approximation ratio better than β and 1 otherwise. As the cost of
an algorithm equals its probability of failure, we can think of it as a LV algorithm.
Assume for notational simplicity that β = 1/T where T is an integer. We will build a family
of lower bound graphs, one for each value of n (beginning from n = 1 + T ); each graph will have
n
m ≤ n, so it will suffice to demonstrate a lower bound of 12T min{k,T
}.
We now consider the behavior of a deterministic algorithm A with respect to the uniform
distribution on the constructed family of inputs. For a given value T the graph would be made
from k components of size 2T and n − 2kT singleton components (recall that 2kT = 2k/β ≤ n). If
algorithm A returns nodes from ℓ of the k components of size 2T , it achieves a total influence of
2ℓT +(k −ℓ). Thus, to attain approximation factor better than β = T1 , we must have 2ℓT +(k −ℓ) ≥
1
k
T 2kT , which implies ℓ ≥ 2T −1 for any T > 1.
Suppose k > 12T . The condition ℓ ≥ 2Tk−1 implies that at least 2Tk−1 of the large components
must be queried by the algorithm, where each random query has probability 2kT
n of hitting a
n
large component. If the algorithm makes fewer than 12T 2 queries, then the expected number of
n
k
2kT
components hit is 12T
= 6T
. The Multiplicative Chernoff bound (Lemma A.1, part 3) then
2 · n
k

1
k
components is no more than e− 6T ·2/3 ≤ e4/3
imply that the probability hitting more than 2T
<
1
1 − e − ǫ, a contradiction.
If k ≤ 12T then we need that ℓ ≥ 1, which occurs only if the algorithm queries at least one of
n
the kT vertices in the large components. With 2kT
queries, for n large enough, this happens with
1
probability smaller than e − ǫ, a contradiction.
n
We conclude that, in all cases, at least 12T min{k,T
} queries are necessary to obtain approximation
1
factor better than β = T with probability at least 1 − 1e − ǫ, as required.
nd
By Yao’s Minimax Principle this gives a lower bound of Ω( 24T min{k,T
} ) on the expected performance of any randomized algorithm, on at least one of the inputs.
Finally, the construction can be modified to apply to non-sparse networks. For any d ≤ n, we
can augment our graph by overlaying a d-regular graph with exponentially small weight on each
edge. This does not significantly impact the influence of any set, but increases the time to decide if
a node is in a large component by a factor of O(d) (as edges must be traversed until one with nonnd
exponentially-small weight is found). Thus, for each d ≤ n, we have a lower bound of 24T min{k,T
}
on the expected performance of A on a distribution of networks with m = nd edges.


14

Discussion: The lower bound construction of Theorem 4.5 is tailored to the query model considered in this paper. In particular, we do not assume that vertices are not sorted by degree, component
size, etc. However, the construction can be easily modified to be robust to various changes in the
model, by (for example) adding edges with small weight so that the exhibited network G becomes
connected and/or regular.


Acknowledgments
We thank Elchanan Mossel for helpful discussions.

References
[1] Andersen, R., Borgs, C., Chayes, J., Hopcraft, J., Mirrokni, V. S., and Teng, S.-H.
2007. Local computation of pagerank contributions. In WAW. 150–165.
[2] Andersen, R., Chung, F., and Lang, K. 2006. Local graph partitioning using pagerank
vectors. In FOCS. 475–486.
[3] Bakshy, E., Karrer, B., and Adamic, L. A. 2009. Social influence and the diffusion of
user-created content. In ACM EC. 325–334.
[4] Ben-Zwi, O., Hermelin, D., Lokshtanov, D., and Newman, I. 2011. Treewidth governs
the complexity of target set selection. Discrete Opt. 8, 1, 87–96.
[5] Bharathi, S., Kempe, D., and Salek, M. 2007. Competitive influence maximization in
social networks. In WINE. 306–311.
[6] Borgs, C., Brautbar, M., Chayes, J. T., and Teng, S.-H. 2012. A sublinear time
algorithm for pagerank computations. In WAW. 41–53.
[7] Brautbar, M. and Kearns, M. 2010. Local algorithms for finding interesting individuals in
large networks. In ICS. 188–199.
[8] Brown, J. J. and Reingen, P. H. 1987. Social ties and word of mouth referral behavior.
Journal of Consumer Research 14, 3, 350–362.
[9] Centola, D. and Macy, M. 2007. Complex contagions and the weakness of long ties. American Journal of Sociology 113, 3, 702–734.
[10] Cha, M., Mislove, A., and Gummadi, P. K. 2009. A measurement-driven analysis of
information propagation in the flickr social network. In WWW. 721–730.
[11] Chen, N. 2008. On the approximability of influence in social networks. In SODA. 1029–1037.
[12] Chen, W., Wang, C., and Wang, Y. 2010a. Scalable influence maximization for prevalent
viral marketing in large-scale social networks. In KDD. 1029–1038.
[13] Chen, W., Wang, Y., and Yang, S. 2009. Efficient influence maximization in social networks. In KDD. 199–208.
[14] Chen, W., Yuan, Y., and Zhang, L. 2010b. Scalable influence maximization in social
networks under the linear threshold model. In ICDM. 88–97.
15

[15] Dodds, P. and Watts, D. 2007. Universal behavior in a generalized model of contagion.
Phys Rev Lett 92, 21, 218701.
[16] Domingos, P. and Richardson, M. 2001. Mining the network value of customers. In KDD.
57–66.
[17] Goldenberg, J., Libai, B., and Mulle, E. 2001. Talk of the network: A complex systems
look at the underlying process of word-of-mouth. Mark. Let., 221–223.
[18] Goldreich, O. 2010. Introduction to testing graph properties. In Property Testing. 105–141.
[19] Gomez-Rodriguez, M., Leskovec, J., and Krause, A. 2012. Inferring networks of diffusion and influence. TKDD 5, 4, 21.
[20] Goyal, S. and Kearns, M. 2012. Competitive contagion in networks. In STOC. 759–774.
[21] Granovetter, M. 1978. Threshold models of collective behavior. American Journal of
Sociology 83, 1420–1443.
[22] Jiang, Q., Song, G., Cong, G., Wang, Y., Si, W., and Xie, K. 2011. Simulated annealing
based influence maximization in social networks. In AAAI.
[23] Kempe, D., Kleinberg, J., and Tardos, E. 2003. Maximizing the spread of influence
through a social network. In KDD. 137–146.
[24] Kempe, D., Kleinberg, J. M., and Tardos, É. 2005. Influential nodes in a diffusion model
for social networks. In ICALP. 1127–1138.
[25] Kimura, M. and Saito, K. 2006. Tractable models for information diffusion in social networks. In PKDD. 259–271.
[26] Leskovec, J., Adamic, L. A., and Huberman, B. A. 2007a. The dynamics of viral
marketing. TWEB 1, 1.
[27] Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J. M., and
Glance, N. S. 2007b. Cost-effective outbreak detection in networks. In KDD. 420–429.
[28] Leskovec, J., McGlohon, M., Faloutsos, C., Glance, N. S., and Hurst, M. 2007c.
Patterns of cascading behavior in large blog graphs. In SDM.
[29] Liben-Nowell, D. and Kleinberg, J. 2008. Tracing information flow on a global scale
using internet chain-letter data. PNAS 105, 12, 4633–4638.
[30] Mathioudakis, M., Bonchi, F., Castillo, C., Gionis, A., and Ukkonen, A. 2011.
Sparsification of influence networks. In KDD. 529–537.
[31] Morris, S. 2000. Contagion. Review of Economic Studies 67, 57–78.
[32] Mossel, E. and Roch, S. 2007. On the submodularity of influence in social networks. In
STOC. 128–134.
[33] Peleg, D. 2002. Local majorities, coalitions and monopolies in graphs: a review. Theor.
Comput. Sci. 282, 2, 231–257.

16

[34] Richardson, M. and Domingos, P. 2002. Mining knowledge-sharing sites for viral marketing. In KDD. 61–70.
[35] Rogers, E. 2003. Diffusion of Innovations 5th Ed. Free Press.
[36] Rubinfeld, R. and Shapira, A. 2011. Sublinear time algorithms. SIAM Journal on Discrete
Math 25, 1562–1588.
[37] Spielman, D. A. and Teng, S.-H. 2004. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In STOC. 81–90.
[38] Wang, Y., Cong, G., Song, G., and Xie, K. 2010. Community-based greedy algorithm
for mining top-k influential nodes in mobile social networks. In KDD. 1039–1048.
[39] Yao, A. C.-C. 1977. Probabilistic computations: Toward a unified measure of complexity
(extended abstract). In FOCS. 222–227.

A

Concentration Bounds

For reference, we now provide the statement of the Chernoff bounds used throughout this paper.
Lemma
P A.1. Let Xi be n i.i.d. Bernoulli random variables with expectation µ each. Define
X = ni=1 Xi . Then,
• For 0 < λ < 1: Pr[X < (1 − λ)µn] < exp(−µnλ2 /2).

• For 0 < λ < 1: Pr[X > (1 + λ)µn] < exp(−µnλ2 /4).
• For λ ≥ 1: Pr[X > (1 + λ)µn] < exp(−µnλ/3).

17

