Dynamic Influence Analysis in Evolving Networks
Naoto Ohsaka ∗#1 , Takuya Akiba †‡#2 , Yuichi Yoshida †§3 , Ken-ichi Kawarabayashi †#4∗§

The University of Tokyo, † National Institute of Informatics, ‡ JST, PRESTO
Preferred Infrastructure, Inc., # JST, ERATO, Kawarabayashi Large Graph Project

ohsaka@is.s.u-tokyo.ac.jp1 , {takiba2 , yyoshida3 , k keniti4 }@nii.ac.jp

ABSTRACT
We propose the first real-time fully-dynamic index data structure designed for influence analysis on evolving networks.
With this aim, we carefully redesign the data structure of thestate-of-the-art sketching method introduced by Borgs et al.,and construct corresponding update algorithms. Using thisindex, we present algorithms for two kinds of queries, influence estimation and influence maximization, which arestrongly motivated by practical applications, such as viral marketing. We provide a thorough theoretical analysis, which guarantees the non-degeneracy of the solution
accuracy after an arbitrary number of updates. Furthermore, we introduce a reachability-tree-based technique anda skipping method, which greatly reduce the time consumption required for edge/vertex deletions and vertex additions,
respectively, and counter-based random number generators,
which improve the space efficiency.
Experimental evaluations using real dynamic networks withtens of millions of edges demonstrate the efficiency, scalability, and accuracy of our proposed indexing scheme. Specifically, it can reflect a graph modification within a time ofseveral orders of magnitude smaller than that required toreconstruct an index from scratch, estimate the influencespread of a vertex set accurately within a millisecond, andselect highly influential vertices at least ten times faster thanstate-of-the-art static algorithms.

1.

INTRODUCTION

Recently, the increasing popularity of online social networks has resulted in the opportunity to analyze the spreadof product adoption, ideas, and news through the population, and exploit the results. A considerable amount of work
has focused on the analysis of the diffusion process [1, 2, 22],the prediction of future diffusions [7], learning the strengthof influence between a pair of individuals [13,26], estimating
the influence spread [10, 20], and finding a small seed setof individuals to maximize the spread of influence, which
has been termed influence maximization [15,19,24,29]. Oneof the central elements in such work is the mathematicalformalization of stochastic cascade models for diffusion processes. Therefore, the efficient simulation and estimationsof influence in these models is essential to such studies.
However, in reality, social networks have a highly dynamic
nature, and evolve rapidly over time [17, 18]. Consequently,
results concerning the estimation and maximization of influence can quickly become outdated. Because such diffusion
models involve complicated stochastic processes, even withstate-of-the-art scalable algorithms, to re-run them on modern massive networks from scratch requires a non-negligible
computational cost every time.
In this study, we address this issue by developing the first
fully-dynamic index data structure for analyzing influence ina large time-evolving network. Our index is fully dynamic,
i.e., it can instantly incorporate graph updates of any kind,including the addition and deletion of vertices and edges,
and propagation probability updates. By applying this updated index, two kinds of queries for diffusion analysis, influence estimation and influence maximization, can be efficiently answered on the latest graph snapshot. These aredescribed below.

1.1

The first query type that we consider is influence estimation. Given a seed set of vertices, we can use our index toquickly estimate the expected number of vertices that would
be influenced if the seed set is activated. Despite the factthat an exact computation of the answer is a #P-hard problem (under the independent cascade model), our index enables us to obtain an estimate in under a millisecond, where
the error is theoretically bounded and empirically small.
This type of query is useful for evaluating, comparing, andidentifying influential people or groups on the latest snapshot of a dynamic network. Moreover, we can keep track of
the transition of the influence spread for a person or group.
For example, Figure 1 illustrates the transition of the influences of vertices in a real-world evolving network of Flixster
dataset.1 We observe that several vertices have critical times
at which their influences rapidly grow or decline.

1.2
This work is licensed under the Creative Commons AttributionNonCommercial-NoDerivatives 4.0 International License. To view a copyof this license, visit http://creativecommons.org/licenses/by-nc-nd/4.0/. For
any use beyond those covered by this license, obtain permission by emailing
info@vldb.org.
Proceedings of the VLDB Endowment, Vol. 9, No. 12
Copyright 2016 VLDB Endowment 2150-8097/16/08.

Influence estimation

Influence maximization

Another type of query that can be efficiently answered using our index is influence maximization. Given an integer k,this returns the seed vertex set of size k comprising the mostinfluential vertices on the latest snapshot. This query is motivated by the recent cost-effective marketing strategy called
11077

http://www.cs.ubc.ca/~jamalim/datasets/

6000
Maximum influence spread

6000

Influence spread

5000
4000
3000
2000
1000
0

6
7
8
9
0
00 006 00 007 00 008 00 009 01
n/2 ul/2 an/2 ul/2 an/2 ul/2 an/2 ul/2 an/2
J
J
J
J
J
J
J
J

Ja

Figure 1: Transition of
the influence spread of
popular vertices in areal-world network.

for two kinds of queries, influence estimation and influence maximization, and construct update algorithms(Section 4).

5000
4000
3000

1000
0

Dynamic
Static678
9000 006 00 007 00 008 00 009 01
n/2 ul/2 an/2 ul/2 an/2 ul/2 an/2 ul/2 an/2
J
J
J
J
J
J
J
J

Ja

• We introduce several techniques for improving the performance of our indexing method, i.e., a reachabilitytree-based technique for edge/vertex deletions, a skipping
method for vertex additions, and counter-based random
number generators for the space efficiency (Section 6).

Figure 2: Transition of
the approximated maximum influence spread ofa seed set of size 100.

viral marketing, where products are promoted by presenting
free or discounted items to a selected group of highly influential individuals, with the aim of achieving a large number of
product adoptions through “word-of-mouth” effects [9, 25].
Owing to the success and growth of viral marketing, theinfluence maximization problem on static graphs has been
intensively studied [3–5, 8, 14–16, 19, 24, 28–30]. However, incontrast to these methods, which compute the answer fromscratch for each query, we can quickly obtain the answer on
the latest snapshot using our dynamic index.
Figure 2 illustrates the transition of the (approximated)maximum influence spread of a seed vertex set of size 100
computed by our method using the real evolving network of
Flixster dataset. Remarkable difference can be observed between the static setting (i.e., the outdated solution) and the
dynamic setting (i.e., the updated solution), which suggests
the usefulness of dynamic methods.

1.3• We provide a thorough theoretical analysis, which guarantees the non-degeneracy of our update algorithms andsolution accuracy of our query algorithms (Section 5).

2000

Our solution

The key idea underlying our proposed index is to focus theintermediate data structures that are used in state-of-theart influence maximization algorithms [3, 28, 29]. Conceptually, we can say that whereas these are thrown away after
each computation in such algorithms, we maintain and reuse
them after their construction. However, as the original data
structure itself does not contain sufficient information for
an efficient and correct dynamic update, our main challenge
is the careful redesign of the data structure. We examine
the necessary information that should be stored, and prove
the non-degeneracy of our estimation accuracy after an arbitrary number of updates. Moreover, we further improvethe update time by maintaining reachability trees and employing a skipping method, and the space efficiency by using
counter-based random number generators.
Through our experiments using real dynamic networks
with tens of millions of edges, we confirm the scalability,
efficiency, and accuracy of the proposed index. It can update the index within a time of several orders of magnitude smaller than that required to reconstruct an index
from scratch. Our speed-up techniques for dynamic updates
achieve several orders of magnitude improvements over naive
implementations, and the index size is reduced by a factor
of up to 50. Furthermore, using our index we can obtainan accurate estimation of the influence spread within a millisecond, and select highly influential vertices at least ten
times faster than state-of-the-art static algorithms.
The contributions of this study are summarized as follows.
• We carefully redesign the data structure of the sketching method introduced by [3], present query algorithms• We experimentally demonstrate the scalability and efficiency of our indexing method, the effectiveness of the
proposed techniques compared to naive implementations,and the accuracy and efficiency of our query algorithms
for diffusion analysis (Section 7).
The remainder of this paper is organized as follows. In
Section 2, we describe related work on influence analysis.
In Section 3, we provide definitions, notations, and basealgorithms to be used in this paper. Section 4 is devoted to
explaining our dynamic indexing scheme. In Section 5, we
present a theoretical analysis of our method. In Section 6,
we introduce several techniques that further improve theperformance of our method. We present our experimental
results in Section 7, and our conclusions in Section 8.

2.

RELATED WORK

2.1

Influence maximization and influence estimation in static networks

Motivated by the work of Domingos and Richardson [9,25], Kempe et al. [15] formulated influence maximization
as a discrete optimization problem, involving the extractionof a vertex set of a given size that maximizes the influencespread. They proved the NP-hardness of the influence maximization problem, and the monotonicity and submodularityof the influence spread function under two well-establishedinformation diffusion models, called the independent cascadeand linear threshold. Thus, the greedy strategy guarantees
an approximation ratio of 1 − 1/e. The drawback of thisstrategy is that no efficient method to compute the influence spread is known, and this was later proven to be #Phard [4]. Kempe et al. [15] resorted to using the Monte-Carlosimulation to approximate the influence spread, which is effective but too slow for large graphs. This motivates thedevelopment of efficient influence estimation methods that
improve the scalability of Kempe et al.’s greedy algorithm.
Here, we classify existing methods of influence maximization on static graphs, some of which can be also used to estimate the influence spread, into the following three types:
simulation-based, heuristic-based, and sketch-based.
Simulation-based methods simulate the diffusion processrepeatedly in order to accurately estimate the influence spreadwith a theoretical guarantee. To enhance the scalability,
existing approaches have introduced several techniques forpruning unnecessary influence computations [19], as well asa sample average approximation approach [5, 8, 16, 24].
Heuristic-based methods avoid the use of Monte-Carlosimulations by restricting the spread of influence into communities [30], the most probable influence paths [4], and1078

other groups, or approximating the influence spread using
linear systems [14]. Such heuristics are more scalable thansimulation-based methods, but they often produce solutionsof poor quality, owing to an absence of accuracy guarantees.
Sketch-based methods resolved the inefficiency of MonteCarlo simulations without sacrificing accuracy guarantees.
Instead of simulating the diffusion process directly, the method
introduced by Borgs et al. [3], called reverse influence sampling (RIS), conducts reverse simulations to build sketches
consisting a family of vertex sets to efficiently estimate theinfluence spread. RIS has been proven to run in nearly linear
time, and to return a constant-factor approximate solution.
Subsequently, several techniques for reducing the number ofsketches have been developed [28, 29].
Despite such efforts, direct applications of these static
methods for tracking the influence of a certain vertex or
highly influential vertices in highly evolving networks arecomputationally expensive, because they require at least linear time in the graph size.

2.2

Influence maximization in dynamic networks

There have been a few studies that have considered influence maximization in a dynamic setting. Zhuang et al. [31]considered a related but different problem, in which a graphdynamically changes, but only a small number of vertices
can be probed and only at certain times. Hence, information is only available on a small part of the current network.
The objective is to maximize the influence spread in thecurrent network. Note that in our problem, we have fullknowledge on how the graph has been changed, and ourprimary concern is to efficiently maintain the index.
Chen et al. [6] considered the problem of tracking a seed
set that maximizes the influence spread when a graph dynamically changes, and proposed a method that iteratively
updates the current seed set. It should be noted that their
method does not incorporate vertex additions and deletions.
Furthermore, our method concerns not only influence maximization, but also influence estimations for any vertex set.

3.

PRELIMINARIES

3.1

Notations

For an integer k, we use [k] to denote the set {1, 2, . . . , k}.
For a finite set S, s ←R S means that we sample s from S
uniformly at random.
Let G = (V, E, p) be a directed influence graph, where V
is a vertex set of size n, E is an edge set of size m, and p :E → [0, 1] is a propagation probability function representing
the magnitude of influence between a pair of vertices. For−
a vertex v in G, we use d+
G (v) and dG (v) to denote the outdegree and the in-degree of v, respectively. When G is clear
from the context, we will omit the subscripts.

3.2

Problem definition of influence estimationand influence maximization

In this paper, we adopt the most standard information
diffusion model, called the independent cascade (IC) model,
which was formulated by Goldenberg et al. [11, 12]. In the
IC model, given a graph G = (V, E, p) and a vertex set
S ⊆ V , called a seed set, we first activate the vertices in S.
Then, the process evolves in discrete steps according to thefollowing randomized rule. When a vertex u becomes active

for the first time at the step t, it is given a single chance toactivate each current inactive vertex v among its neighbors.
It will succeed with probability puv . If u succeeds, thenv will become active in the step t + 1. Whether or not u
succeeds, it cannot make any further attempts to activate v
in subsequent steps. This process continues until no further
activation is possible. The influence spread of a seed set
S under the IC model, denoted by σ(S), is defined as the
expected total number of active vertices for S.
We formally define the influence estimation problem andthe influence maximization problem as follows.
Problem 1 (Influence estimation). Given a graph
G = (V, E, p) and a vertex set S ⊆ V , this problem asks tocompute the influence spread σ(S) of S.
Problem 2 (Influence maximization). Given a graph
G = (V, E, p) and an integer k, this problem asks to find avertex set S ⊆ V of size k that maximizes σ(S).
Note that it has been proven that the influence estimation problem is #P-hard [4], and the influence maximization
problem is NP-hard [15].

3.3

Naive method for influence estimation

Because the exact computation of σ(·) is #P-hard [4],previous studies have employed Monte-Carlo simulations forthis purpose [5, 8, 15, 19, 30]. That is, we simulate the diffusion process several times, and then compute the average number of activated vertices. The time complexity ofMonte-Carlo simulations is O(mr), where r is the number ofsimulations. As this naive method requires linear time justto estimate the influence of a single set, we cannot adopt
this method in the dynamic setting.

3.4

Naive method for influence maximization

Although the influence maximization problem has been
proven to be NP-hard [15], a natural greedy algorithm canachieve a constant approximation to the optimum solution,owing to the non-negativity, monotonicity, and submodularity of σ(·). We say that a set function f : 2V → R ismonotone if f (S) ≤ f (T ) for all S ⊆ T , and submodular if
f (S ∪ {v}) − f (S) ≥ f (T ∪ {v}) − f (T ) for all S ⊆ T andv ∈ V \T . The greedy algorithm, introduced by [15], repeatedly adds the vertex with the maximum marginal influence
into S until k vertices have been added. The following theorems guarantee that the greedy algorithm approximates the
optimum solution within a factor of 1 − 1/e, by evaluating
the influence spread function σ(·) kn times.
Theorem 3.1. [15] For the IC model, the influence spreadfunction σ(·) is non-negative, monotone, and submodular.
Theorem 3.2. [23] For a non-negative, monotone, andsubmodular function f , let S be a set of size k obtained using
the greedy strategy. Then, f (S) ≥ (1 − 1/e)f (S ∗ ), where S ∗is the optimum solution.
Although we cannot evaluate σ(·) exactly, we can estimate
it using the Monte-Carlo simulations described in the previous section. By doing so, although the approximation guarantee does not deteriorate greatly, the time complexity isO(knmr), which is prohibitively large for even static graphs.

1079

3.5

The RIS sketching method

Θ( 13 (n + m) log n). Note that the space complexity of ourindex is roughly bounded by O(W ).
For a vertex v, let Iv denote the set of indices i ∈ [|I|] withv ∈ V (Hi ), and for a vertex set S, let IS denote theS set ofindices i ∈ [|I|] with S ∩ V (Hi ) 6= ∅. That is, IS = v∈S Iv .
Our index stores Iv for every vertex v, so that we can quickly
fetch the sketches that include a particular vertex.
We note that the sketch adopted in RIS [3] cannot support
dynamic updates efficiently, because it only stores the vertex
set V (Hi ). On the other hand, we will show that we canupdate sketches when the graph dynamically changes.

Borgs et al. [3] addressed the inefficiency of these naive
methods by introducing a sketching method. Because wewill provide the details in Section 4, we will only present an
overview of their method here.
First, we repeatedly construct subgraphs as follows. In
the i-th step, we choose a target vertex zi ∈ V and an
activation function xi : E → [0, 1] uniformly at random.
We call an edge uv ∈ E active with respect to xi if xi (uv) ≤puv , and inactive with respect to xi otherwise. We regard
a non-edge uv 6∈ E as inactive irrespective of xi . We writexu ;i v to indicate that there is a directed path from u to v
consisting only of active edges with respect to xi . Then, we
compute a subgraph Hi that consists of vertices v such thatxv ;i zi by performing a reverse BFS from zi . We cease thisprocess when the total number of traversed edge exceedsΘ( 13 (n + m) log n), where  is an error parameter.
Intuitively, influential vertices seem likely to appear in
Hi ’s. For a vertex set S ⊆ V , let d0 (S) be the number ofsubgraphs Hi such that S ∩ V (Hi ) 6= ∅. It is not hard to seethat d0 (S) is proportional to the expected number of vertices
influenced by some vertex in S. More precisely, we estimate
the influence spread of S by n · d0 (S)/t, where t is the total
number of generated subgraphs. With high probability, thisvalue is a (1 ± )-approximation to σ(S) [3].
We can also solve the influence maximization problem, as
follows. We begin with an empty set S, and then add thevertex t that has the maximum marginal degree, i.e., t =argmaxv∈V \S d0 (S ∪{v})−d0 (S), into S until k vertices havebeen added. The resulting set is a (1−1/e−)-approximation
to the optimum set with high probability [3].
The advantage of this sketching method is that no matter
what k is, the total time complexity is bounded by O( 13 (n+m) log n), which is much smaller than the time complexity
O(knmr) of the naive method. However, it is too expensive
to apply this sketching method from scratch every time thegraph changes. In the next section, we will develop a methodthat efficiently updates the sketch when the graph changes.

4.

4.2

4.3

4.3.1

PROPOSED METHOD

Index structure

Let us begin with our index structure for a static graph
G = (V, E, p). Let  > 0 be a precision parameter. Our
index consists of a set of tuples I = {(zi , xi , Hi )}i , wherezi ∈ V is a target vertex, xi : E → [0, 1] is an activation
function, and Hi is a subgraph of G consisting of active
edges with respect to x. Here, every vertex in V (Hi ) is able
to reach zi in Hi . We call each (zi , xi , Hi ) a sketch.
The number of sketches in I is determined as follows: The
weight of P
a subgraph H, denoted by w(H), is defined as|V (H)| + v∈V (H) d− (v), which equals the space requiredtoalways keep the condition that
P store H. Then, we willP
i∈[|I|−1] w(Hi ) < W andi∈[|I|] w(Hi ) ≥ W , where W =Supporting queries

In this subsection, we will describe how we approach influence estimation and influence maximization queries using
the index constructed in the previous subsection.

In this section, we will present our efficient indexing method
for influence analysis in evolving graphs. First, we will explain what we store in our index, and how it is constructedfrom a static graph. Then, we will demonstrate how to compute the influences of vertex sets and extract a set of highly
influential vertices using the index. Finally, we will explain
how the index is dynamically updated.

4.1

Index construction

Here, we describe how we construct our index from a static
graph. Given a graph G = (V, E, p), we begin with an empty
index I = ∅, and we repeatedly create new sketches and addthem into I for as long as the total weight of the current
index is less than W . A sketch is constructed using the following reverse-BFS-like method: First, we sample a target
vertex zi ∈ V uniformly at random, and add it to an empty
queue. We also sample xi : E → [0, 1] uniformly at random.
If the queue is not empty, then we remove a vertex v fromthe queue. If this is the first time that v is visited, then foreach active edge uv, we add u to the queue. Finally, we set
V (Hi ) to the visited vertices and E(Hi ) to the visited active
edges. Building a sketch (zi , xi , Hi ) requires O(w(Hi )) time,
and thus the entire index construction requires O(W ) time.

Influence estimation

We will start with influence estimation. The number ofvertices that a vertex v influences can be approximated byn · |Iv |/|I|. Because we actually simulate the propagation
process several times and take the average, the expectedvalue is exactly equal to the influence σ({v}). Similarly, fora vertex set S, the number of vertices that S influences canbe approximated by n · |IS |/|I|.
Given a single vertex v, we can compute n · |Iv |/|I| in constant time, as we have Iv stored in our index. For a vertex
set S of size greater than one, by storing each V (Hi ) usinga hash so that we can check v ∈ V (Hi ) in constant time,
the time complexity of EstimateInfluence is bounded by
O(|S| · |I|). However, we can improve the running time byusing S
Iv stored in our index. That is, we compute IS as
IS P= v∈S Iv . This technique reduces the running time toO( v∈S |Iv |), and we will demonstrate that |Iv | is muchsmaller than |I| by means of our thorough experiments.
See EstimateInfluence in Algorithm 1 for further details.
Because our method is equivalent to the (non-indexing)
method by Borgs et al. [3], we inherit the same guarantee of
its accuracy. To summarize, the following guarantee holds.
Theorem 4.1. By choosing W = Θ( 13 (n + m) log n),
EstimateInfluence(I, S) estimates σ(S) with an additive
error of  with probability at least 1− n1 over the choice of zi ’s
and xP
i ’s. The time complexity of EstimateInfluence(I, S)
is O( v∈S |Iv |).

4.3.2

1080

Influence maximization

Algorithm 1 Influence queries.
1: procedure EstimateInfluence(I, S)
2:
if S = {v} then3:
return n · |Iv |/|I|.
4:
else
S
5:
return n · v∈S Iv /|I|.

Algorithm 2 Auxiliary functions.
1: procedure Expand(I, i, z)
2:Q ← a queue with only one element z.
3:
Hi ← Hi ∪ {z}.
4:while Q 6= ∅ do
5:
Dequeue v from Q.
6:for all uv ∈ E do
7:
if xi (uv) < puv then8:
E(Hi ) ← E(Hi ) ∪ {uv}.
9:if v 6∈ V (Hi ) then10:
Enqueue u onto Q.
11:
V (Hi ) ← V (Hi ) ∪ {u}.

6: procedure MaximizeInfluence(I, k)
7:
S ← ∅.
8:for i = 1 to k do
9:vi ← argmaxv∈V \S dI−S (S ∪ {vi }).
10:
S ← S ∪ {vi }.
11:
return S.

12: procedure Shrink(I, i)
13:Hi ← the subgraph consisting of vertices that can reachzi by passing through active edges.

Next, we consider the problem of finding a vertex set
S of size k that maximizes the expected number of vertices influenced by S, where k is the input parameter. The
greedy algorithm is a standard approach for this problem,
and Borgs et al. [3] reduced this greedy algorithm to thegreedy strategy on a set of subgraphs. We will describe theirprocedure in our language. For a vertex v, define the degreedI (v) of v in I as the number of i ∈ [|I|] with v ∈ V (Hi ).
In other words, dI (v) = |Iv | initially. We choose the vertex with the maximum degree in I and denote this by v1 .
Then, examining each sketch (zi , xi , Hi ), we remove it if
v1 ∈ V (Hi ). Next, we choose the vertex with the maximum degree in the resulting index, and denote this by v2 .
Then, examining each sketch (zi , xi , Hi ), we remove it if
v2 ∈ V (Hi ). We repeat this process k times, and then output the vertex set {v1 , v2 , . . . , vk }. The details are provided
in MaximizeInfluence in Algorithm 1. Here, I −S denotes
the index obtained by removing all of the sketches (zi , xi , Hi )with S ∩ V (Hi ) 6= ∅. To boost the empirical performance,
we also employ the lazy evaluation technique [21].

14: procedure Adjust(I)15:
W ← Θ( 13 (n + m) log n).
P
16:
while
w(Hi ) < W do
1≤i≤|I|

17:
18:
19:

1≤i≤|I|−1

20:

4.4

Supporting dynamic update operations

In this subsection, we explain how we update our index
efficiently. We consider five operations: vertex additions,vertex deletions, edge additions, edge deletions, and propagation probability updates. First, we present three subroutines used in our update operations, and then we describe
how we update the index when the graph changes. The details are provided in Algorithms 2, 3, and 4. The correctness
will be demonstrated in Section 5.

4.4.1

Auxiliary subroutines

Expand(I, i, z): Suppose that we have added an edge zw orincreased the propagation probability of an edge zw. Then,

Discard the last element from I.

for each i ∈ [|I|] with w ∈ V (Hi ), we want to add vertices
from which we can newly reach the vertex zi to Hi . To thisend, we perform a reverse BFS from z, and add the traversed
vertices to Hi . Note that all of the newly added vertices canreach z.

Theorem 4.2. Let W = Θ( 13 (n+m) log n). Then, MaximizeInfluence(I, k) returns a set S of size k, such that
σ(S) ≥ (1 − 1/e − )σ(S ∗ ) with probability at least 1 − n1 overthe choice of zi ’s and xi ’s, where S ∗ = argmaxS⊆V :|S|=k σ(S).
The time
P complexity of MaximizeInfluence(I, k) is boundedby O( i∈[|I|] |V (Hi )|).
Proof. Because this method is equivalent to the (nonindexing) method by Borgs et al. [3], we inherit the sameguarantee of its accuracy.
Now, we consider the time complexity. When we add avertex v to the output, we need to decrement the degrees ofvertices u ∈ V (Hi ) for each i ∈ Iv . However, this decrementation occurs only once
P for each sketch. Hence, the total
time complexity is O( i∈[|I|] |V (Hi )|).

z|I|+1 ←R V .
Expand(I, |I| + 1, z|I|+1 ).
P
whilew(Hi ) ≥ W do

Shrink(I, i): Suppose that we have removed an edge uv ordecreased the propagation probability of an edge uv. Then,for i ∈ [|I|] such that uv ∈ E(Hi ), we want to remove thevertices in Hi from which we can no longer reach zi anymore.
To this end, we recompute the set of vertices that can reachzi by conducting a reverse BFS from zi .
Adjust(I): While we are processing edge and vertex updates, the total weight of the index may violate the conditionon the total weight. In such a case, we create new sketchesor remove current sketches as follows. If the total weight issmaller than the threshold W , then we create a new sketch(z, x, H) by sampling z ∈ V , and calling Expand on z to
make H. On the other hand, if the total weight of sketches,
excluding the last one, is larger than or equal to W , thenwe remove the last sketch from the index.

4.4.2

Dynamic update routines

Now, we explain how we update our index when the graphchanges.
AddVertex(I, v): Suppose that we have added a new vertex v to the current graph. In such a case, we must update
the target vertices in the index to preserve the property thateach vertex in the graph is chosen uniformly at random asa target vertex.
Let V and V 0 denote the vertex set of a graph before
and after we add a new vertex v, respectively. That is,V 0 = V ∪ {v}. Suppose that we construct an index fromscratch after inserting v. Obviously, for each time we choosea sketch, the probability that the target vertex is chosenn, and the probability that the target vertex
from V is n+1
1
is v is n+1 . In order to ensure that this property holds,
we update the target vertex in the current index to v with1
probability n+1.

1081

Algorithm 3 Vertex operations.
1: procedure AddVertex(I, v)
2:
for i = 1 to |I| do
1
3:
continue with probability 1 − n+1.
4:
Hi ← ∅, zi ← v.
5:
Expand(I, i, zi ).
6:
Adjust(I).
7: procedure DeleteVertex(I, v)
8:
Remove edges incident to V from each E(Hi ).
9:
for all i ∈ Iv do
10:
if zi = v then11:
Hi ← ∅, zi ←R V .
12:Expand(I, i, zi ).
13:
else
14:
Shrink(I, i).
15:
Adjust(I).
Algorithm 4 Edge operations.
1: procedure Change(I, uv, p)2:
puv ← p.
3:
for all i ∈ Iv do
4:
P ← [[uv ∈ E(Hi )]], Q ← [[xi (uv) < p]].
5:
if ¬P ∧ Q then. inactive → active
6:
E(Hi ) ← E(Hi ) ∪ {uv}.
7:Expand(I, i, u).
8:
if P ∧ ¬Q then. active → inactive
9:
E(Hi ) ← E(Hi ) \ {uv}.
10:
Shrink(I, i).
11:
Adjust(I).
12: procedure AddEdge(I, uv, p)13:
puv ← 0.
14:
Change(I, uv, p).
15: procedure DeleteEdge(I, uv)
16:
Change(I, uv, 0).

DeleteVertex(I, v): Suppose that we have removed a vertex v from the current graph. Then, for each i ∈ [|I|], we
check whether v is contained in Hi . If this is the case, then
we update the tuple (zi , xi , Hi ) as follows: If zi = v, we
sample zi from V \ {v} uniformly at random and compute
Hi . Otherwise, we remove v and all edges incident to v from
Hi , and then we call Shrink(I, i) to shrink Hi .
Change(I, uv, p): Suppose that we have changed the propagation probability of an edge uv from p0 to p. If the stateof uv with respect to xi changes, then we need to update
subgraphs in the index I. More specifically, we carry out
the following for each i ∈ [|I|]. If p0 < xi (uv) ≤ p, then we
expand Hi by calling Expand(I, i, u). If p < xi (uv) ≤ p0 ,then we shrink Hi by calling Shrink(I, i).
AddEdge(I, uv, p): Suppose that we have added an edge uv
with propagation probability p to the current graph. First,
we add uv to the current edge set E and set puv = 0. Then,for each sketch (zi , xi , Hi ) ∈ I such that v ∈ V (Hi ), we
define xi (uv) by choosing a value from [0, 1] uniformly at
random. Finally, we update the propagation probability puv
to p, by calling Change(I, uv, p).
DeleteEdge(I, uv): Suppose that we have deleted an edge
uv from the current graph. Then, we first update the edge
probability puv to zero, by calling Change(I, uv, 0), andthen remove uv from E. Then, we remove uv from thedomain of xi for each i ∈ [|I|]. We only examine the sketches
containing v, and thus the expected number of examined|I|, which follows from Lemma 5.11.
sketches is σ({v})
n5.

THEORETICAL ANALYSIS

In this section, we will show the correctness of our indexing method and then proceed to analyze its time complexity.

5.1

Correctness

Now, we consider the correctness of our indexing method.
sta
Note that our method is randomized. We first define IW(G)
dynand IW (G) as the distribution of indices in the case that
we apply our method to a static graph G and the sequenceof dynamic updates that results in G, respectively. Our goaldynsta
is to show that IW(G) = IW
(G). If this is the case, thenqueries on the index following dynamic updates will inherit
the same guarantees that furnish Theorems 4.1 and 4.2.
Given a graph G = (V, E, p), consider the following random process that generates a sequence of pairs. For each
step, we sample a target vertex z ∈ V and an activation
function x : E → [0, 1] uniformly at random, and add thepair (z, x) to the sequence. Let X∞ (G) denote the distribution of (infinite) sequences of pairs obtained in this way. Let
H(z, x) be the subgraph consisting of vertices that can reachz under x. Furthermore, let I∞ (G) denote the distributionof tuple sequences obtained from X∞ (G) by replacing eachpair (z, x) by (z, x, H(z, x)).
We say that a distribution X of pair sequences is valid
for G if it can be obtained by sampling a random sequence
from X∞ (G) uniformly at random and taking a prefix of it(of arbitrary length). Similarly, we say that a distribution
I of tuple sequences is valid for G if it can be obtainedby sampling a random sequence from I∞ (G) uniformly at
random and taking a prefix of it.
For a positive integer W , we define IW (G) as the distribution over prefixes of tuple sequences in I∞ (G) that are obtained as follows: We sample a tuple sequence (z1 , x1 , H1 ),(z2 , x2 , H2 ), . . . from I∞ (G) and take the minimum prefixof it such that the total weight of the subgraphs is at leastW . We sample a tuple sequence (z1 , x1 , H1 ), (z2 , x2 , H2 ), . . .
from I∞ (G) and take the minimum prefix of it such thatthe total weight of the subgraphs is at least W . It is easy to
sta
sta
(G) =
(G). We will establish that IW
see that IW (G) = IWdyndyn
IW (G) by showing that IW (G) = IW (G).
dyn
For the empty graph G, we clearly have IW(G) = IW (G).
dyn
We will show that, for any graph G with IW(G) = IW (G)and a graph G0 obtained from G by a dynamic update, wedynagain have IW(G0 ) = IW (G0 ). Then, we are done by induction on the number of updates.
The following auxiliary lemma states that we can change
the length of a valid distribution to W using Adjust(·).
Lemma 5.1. Let G be a graph, and let I be a valid distribution of finite pair sequences for G. Then, I 0 = Adjust(I)is equal to IW (G), where W is a parameter used in Adjust.
Remark 5.2. By Adjust(I), we mean the distributionof sequences obtained by applying Adjust to a sequence I
sampled from I. We will use similar conventions for otherprocedures in the following.
Proof. We can obtain IW (G) from I as follows. Let
I = (z1 , H1 ), (z2 , H2 ), . . . , (z|I| , H|I| ) be a pair sequences
sampledfrom I. Then, we repeat the following process.
P
If 1≤i≤|I| w(Hi ) < W , then we sample a target vertex z
and an activation function x : E → [0, 1] uniformly at random. Then, we compute the corresponding subgraph H,

1082

P
and add the pair (z, H) to I. If
1≤i≤|I|−1 w(Hi ) ≥ W ,then we remove the last element from I. This is exactly
corresponds to what is carried out in Adjust, and it follows
that I 0 = IW (G).
In the following, we will show that our update routines
in Algorithms 3 and 4 transform a valid distribution for theoriginal graph to a valid distribution for the new graph.
Lemma 5.3. Let G be a graph, e ∈ E(G), and p ∈ [0, 1].
Let G0 be the graph obtained from G by changing the propagation probability of e to p. If I is a valid distribution of tuple
sequences for G, then the distribution I 0 = Change(I, e, p)
is a valid distribution of tuple sequences for G0 .
Proof. Let X and X 0 be the distributions of the pairsequences corresponding to I and I 0 , respectively. Then, it
is clear that X = X 0 . Because X is a valid sequence for G,
it follows that X 0 is also a valid sequence for G0 . Hence, I 0
is a valid distribution for G0 .
Lemma 5.4. Let G be a graph and G0 be the graph obtained from G by adding a new vertex v 6∈ V (G). If I is avalid distribution for G, then I 0 = AddVertex(I, v) is avalid distribution for G0 .
Proof. Let X and X 0 be the distributions of the pairsequences corresponding to I and I 0 , respectively. Then, we
can obtain X 0 from X as follows. Let (z1 , x1 ), (z2 , x2 ), . . . bea sequence sampled from X . Then, we replace each of zi by
v with probability 1 − 1/|V (G0 )|. We can observe that X 0
is a valid sequence for G0 , and it follows that I 0 is a valid
distribution for G0 .
Lemma 5.5. Let G be a graph and G0 be the graph obtained from G by removing a vertex v ∈ V (G). If I is avalid distribution for G, then I 0 = DeleteVertex(I, v) isa valid distribution for G0 .
Proof. Let X and X 0 be the distributions of the pairsequences corresponding to I and I 0 , respectively. Then, we
can obtain X 0 from X as follows. Let (z1 , x1 ), (z2 , x2 ), . . . bea sequence sampled from X . If zi = v, then we again replacezi from V (G)−v uniformly at random again. We can observethat X 0 is a valid distribution for G0 , and it follows that I 0
is a valid distribution for G0 .
Similarly, we obtain the following two lemmas. As theproofs are quite similar to the ones of Lemmas 5.4 and 5.5,
we omit them due to the lack of space.
Lemma 5.6. Let G be a graph and G0 be a graph obtained
from G by adding a new edge uv 6∈ E(G). If I is a valid
distribution for G, then I 0 = AddEdge(I, uv) is a valid
distribution for G0 .
Lemma 5.7. Let G be a graph and G0 be the graph obtained from G by removing an edge uv ∈ E(G). If I is avalid distribution for G, then I 0 = DeleteEdge(I, uv) is avalid distribution for G0 .
dyn
Theorem 5.8. IW(G) = IW (G).

Proof. From Lemmas 5.4, 5.5, 5.6, and 5.7, we have thatthe distribution of indices obtained by our dynamic updateprocedures is always a valid distribution of tuple sequences
for the current graph. Because we apply Adjust at the endof each update, the distribution of indices is given exactly
by IW (G) by Lemma 5.1.

By Theorems 5.8, 4.1, and 4.2, we obtain the following.
Theorem 5.9. Let W = Θ( 13 (n + m) log n), and let I be
the index obtained by a sequence of dynamic updates. Then,
EstimateInfluence(I, S) estimates σ(S) with an additive
error of  with probability at least 1 − n1 over the choice ofzi ’s and xi ’s.
Theorem 5.10. Let W = Θ( 13 (n + m) log n), and let I
be the index obtained by a sequence of dynamic updates.
MaximizeInfluence(I, k) returns a set S of size k, suchthat σ(S) ≥ (1 − 1/e − )σ(S ∗ ) with probability at least 1 − n1
over the choice of zi ’s and xi ’s, where S ∗ = argmaxS⊆V :|S|=k σ(S).

5.2Time complexity

Now, we turn our focus to analyzing the time complexityof our indexing method. We note that it is difficult to precisely bound the time complexity of dynamic update operations because it depends on the sizes of cascades and hence
the structure of the input graph. Instead, we will analyze
the number of sketches examined in each update operation.
To this end, we will apply the following lemma, the correctness of which is obvious from the construction of Hi .
Lemma 5.11. For a vertex set S and a randomly sampled,sketch (zi , xi , Hi ), it holds that Pr[V (Hi ) ∩ S 6= ∅] = σ(S)nwhere the probability is over the choice of zi and xi .
Theorem 5.12. AddVertex examines |I| sketches. DeleteVertex, Change, AddEdge, and DeleteEdge examine σ({v})/n · |I| sketches on average.
Proof. The first claim is obvious, as the number of sketches
is |I|. Suppose that DeleteVertex(I, v), Change(I, uv, p),
AddEdge(I, uv, p), or DeleteEdge(I, uv, p) was called. Then,
we only examine the sketches containing v and thus the expected number of examined sketches is σ({v})|I|, followingnfrom Lemma 5.11.

6.

TECHNIQUES FOR IMPROVING THE
PERFORMANCE

Here, we introduce several techniques to improve the performance of our indexing method.

6.1

A reachability-tree-based pruning technique

Although we have demonstrated that the number of updated sketches resulting from vertex deletions and update
operations on edges is small, naive implementations of these
are computationally expensive, because a whole subgraph isscanned for each relevant sketch in the Shrink procedure.
In this section, we will address this issue by introducing atechnique, called the reachability-tree-based technique.
A key observation is that the removal of a single edge
or vertex rarely effects the reachability among the vertices
in a sketch, because real-world social networks are highly
connected. To exploit this observation, for each sketch wewill store a directed reachability tree Ti in Hi rooted at zi .
Therefore, each sketch is now a tuple (zi , xi , Hi , Ti ).

6.1.1

Definition of reachability trees

Let us begin with the definition of the reachability tree.
The reachability tree for a sketch (zi , xi , Hi ) is a directed tree
on the vertex set V (Hi ) towards the root zi , constructed byusing active (directed) edges in E(Hi ) with regard to xi .
Each vertex in V (Hi ) is able to reach zi along with Ti .

1083

6.1.2

Speeding up the Shrink procedure

6.1.3

Maintaining reachability trees

Algorithm 5 Improved operations.
1: procedure Shrink-after-Edge-Removal(I, i, uv)
Next, we will explain how we can apply the reachability2:
if uv 6∈ E(Ti ) then return
tree to speed up the Shrink procedure.
3:
T 0 ← the subtree rooted at u.
Suppose that an edge uv is inactivated in the Change pro4:
R ← vertices in T 0 adjacent to V (Hi ) \ T 0 .
cedure. Then, we need to update each sketch (zi , xi , Hi , Ti )5:
R0 ← the set of vertices in T 0 that can reach R.
for w ∈ T 0 \ R0 do
with uv ∈ E(Hi ) by calling the procedure Shrink(I, i) (Line 10). 6:
7:
Remove w and edges entering w from Hi and Ti , resp.
Previously, we updated Hi by performing a reverse BFS
from zi . Because we now have Ti , we can update Hi more
8: procedure Shrink-after-Vertex-Removal(I, i, v)
9:T 0 ← the subtree rooted at v.
efficiently. We present the details as follows.
10:
R ← vertices in T 0 adjacent to V (Hi ) \ T 0 .
If uv 6∈ E(Ti ), then u can still reach zi along with Ti
11:
R0 ← the set of vertices in T 0 that can reach R.
after the removal of uv. Thus, we do nothing. Otherwise,
12:
for w ∈ T 0 \ R0 do
the vertices in V (Ti (u)) are the only candidates that may
13:
Remove w and edges entering w from Hi and Ti , resp.
no longer reach zi , where Ti (u) denotes the subtree rooted
14: procedure AddVertex’(I, v)
at u. Thus, we check whether the vertices in V (Ti (u)) can1, i ← 0.
15:
α ← n+1
reach V (Hi ) \ V (Ti (u)). With this aim, we first explicitly
16:
while
i < |I| do
compute the set V (Ti (u)). Then, we compute the set R of11
17:
x ←R [0, 1], k ← dlog 1−x/ log 1−αe, i ← i + k.
vertices in V (Ti (u)) adjacent to V (Hi ) \ V (Ti (u)). Finally,
18:
if
i
≤
|I|
then
we compute the set of vertices in V (Ti (u)) that can reach R,
19:
Hi ← ∅, zi ← v.
using a reverse BFS from R. Then, we remove the vertices
20:
Expand(I, i, zi ).
that can no longer reach R from V (Hi ) and update Hi and21:
Adjust(I).
Ti . The pseudocode is presented as Shrink-after-EdgeRemoval in Algorithm 5.
In addition, we can speed up Shrink(I, i) at Line 14 in the
Because we are only required to seeing sketches for which
DeleteVertex procedure in a similar manner. The pseuwechange the target vertex, the expected number of sketches
docode is presented as Shrink-after-Vertex-Removal in|I|
we look at is n+1, which is much smaller than |I|.
Algorithm 5.

Now, we discuss how we maintain reachability trees. First,
when creating a new sketch (zi , xi , Hi , Ti ), Ti is a tree consisting of a single vertex zi . When updating Ti in an existing
sketch (zi , xi , Hi , Ti ), we have the following four cases.
Suppose that an edge uv with uv ∈ E(Hi ) is inactivated.
Let Hi0 be the new subgraph computed by calling Shrinkafter-Edge-Removal(I, i, uv). Note that the vertices in
R0 = V (Hi0 ) ∩ V (Ti (u)) are obtained by performing a reverse BFS from R (see Shrink-after-Edge-Removal forthe definitions of R and R0 ). Hence, by removing the subtree V (Ti (u)) from Ti and concatenating the tree formed bythis reverse BFS, we obtain a new reachability tree for Hi0 .
Suppose that an edge uv with v ∈ V (Hi ) is activated. Then,we perform a reverse BFS from u, and add the edge uv andthe obtained subtree rooted at u to Ti . When deleting avertex v with v ∈ V (Hi ), we can update Ti , in a similarmanner as in the case where an edge is inactivated. When
adding a vertex, we are not required to do anything.

6.2

A skipping method for vertex addition

When adding a vertex, we are required to change the tar1
. However,get vertex of each sketch with probability n+1
running through all of the sketches in I is a costly procedure.
We can avoid this issue by applying the following technique.
Let k be the first index for which we change the target vertex zk . Then, for each positive integer t, we have Pr[k =1. Hence, we can sample kt] = (1 − α)t−1 α, where α = n+1
by first sampling x ∈ [0, 1] uniformly
and then
P at random,t−1
taking the minimum k such thatα ≥ x.
t∈[k] (1 − α)11This is equivalent to k ≥ log 1−x/ log 1−α. We choose minimum such k with these properties, and change the target
vertex of the k-th sketch to v. Then, we repeat the sameprocedure for the remainder of the index. See AddVertex’in Algorithm 5 for complete details.

6.3

Random number generators

We have assumed that each sketch (zi , xi , Hi , Ti ) stores afunction xi : E → [0, 1]. This is undesirable because storingxi requires O(m) space.
To address this issue, we use a pseudorandom generator
called Random123 [27]. Random123 is counter-based, thatis, it maps an integer to a (pseudo)random value. Insteadof explicitly storing xi (uv) for each i ∈ [|I|] and uv ∈ E,
for each time that we need xi (uv), we call Random123 withan integer representation of the pair (i, uv), and we use theobtained value after normalizing it to be in [0, 1].

7.

EXPERIMENTS

In this section, we will demonstrate the efficiency and effectiveness of our indexing method by performing experiments on real-world networks. We conducted the experiments on a Linux server, with Intel Xeon E5-2690 2.90GHz
CPU and 256GB memory. All algorithms were implemented
in C++ and compiled using g++v4.6.3 with the -O2 option.

7.1

Experimental settings

Datasets: We selected seven real-world dynamic networks
with timestamps, from the Koblenz Network Collection.2
We ordered edges in ascending time order. The basic information regarding each dataset is presented in Table 1 andthe degree distribution of each dataset is plotted in Figure 3.
Probability settings: As these networks do not contain information concerning the propagation probabilities of edges,
we assign an edge probability puv for each edge uv to a probability chosen from {0.1, 0.01, 0.001} uniformly at random
under the trivalency (TR) model [4], or 1/d− (v) under theweighted cascade (WC) model [15].
21084http://konect.uni-koblenz.de/networks/

Table 1: Datasets.
Dataset

n

m

Digg
Enron
Epinions
Facebook
DBLP
YouTubeFlickr30,39887,273
131,828
63,731
1,314,050
3,223,585
2,302,925

85,247
320,154
840,799
1,634,070
10,724,828
18,750,748
33,140,017

TypeCommunication (directed)
Communication (directed)
Social (directed)
Social (undirected)
Coauthorship (undirected)
Social (undirected)
Social (directed)

Cumulative frequency

107

Digg
Enron
Epinions
Facebook
DBLP
YouTubeFlickr

106
105
104
103
102
101
0

10

100

Figure 3:

101

102
103
In-degree

104

105

Degree distribution of each dataset.

Algorithms: Our method is parameterized by W , which
represents the threshold of the total weight. In order toapply the same parameter for various networks, we introduce
the parameter β, which determines W in a manner suchthat W = β(n + m) log n. Unless otherwise specified, we set
β = 32. This choice will be justified in Section 7.4 in termsof accuracy.
For the purpose of our comparison, we use the following
algorithms in our experiments.

a few hours to construct the index. However, we note thatwithout our dynamic method, this amount of time is required to estimate or maximize the influence spread. We
here note that the difference in the index size under the
WC model comes from the differences in the degree distribution. For example, YouTube has more vertices with highin-degree than DBLP. Thus, for each sketch construction,
the total weight of the index for YouTube increases fasterthan DBLP. As a result, the obtained index for YouTube
has a small number of sketches (1 million), which requires
only 3.9GB, while the index for DBLP has a larger numberof sketches (37 millions) and consumes 34.8GB. Table 3 reports the index sizes both with and without counter-based
random number generators introduced in Section 6.3. Notethat without random number generators, we need to store
all the edges incident to vertices in each of Hi ’s. With random number generators, the space consumption is reduced
by a factor from 4 to 50. Figure 4 depicts the change of theindexing time and index size with the value of β from 2 to2048. Both of these values are scaled to β.

7.3• Vertex additions: The average running time for adding
1,000 new isolated vertices to the index constructed using
the whole network.
• Vertex deletions: The average running time for deleting 1,000 uniformly chosen vertices from the index constructed using the whole network.

• RIS [3]: A reverse influence sampling method on which
our method is based. We set the total number of traversed edges to be 32(n + m) log n.

• Propagation probability updates: The average running
time for updating the propagation probabilities of 1,000
uniformly chosen edges of the index constructed using
the whole network. The update is conducted as follows.
Suppose that an edge e with propagation probability pe ischosen. When using the TR model, we randomly choose
a probability from {0.1, 0.01, 0.001} \ {pe } as the newedge probability of e. When using the WC model, we
randomly assign pe × 2 or pe /2 to e.

• TIM+3 [29]: A sketch-based method with the two-phasestrategy. We set the parameters as ` = 1 and  = 0.5.
• IMM4 [28]: A sketch-based method that uses martingales. We set the parameters as ` = 1 and  = 0.5.
• PMC5 [24]: A simulation-based method using pruned
Monte-Carlo simulations for the IC model. The number of subgraphs is set to 200, as in [24].

• Edge additions: The average running time for adding thefinal 1,000 edges to the index constructed using all of theedges except for the final 1,000 edges.

6• IRIE [14]: A heuristic-based method that uses a linear
system. We set the parameters as α = 0.7 and θ = 1/320.

• Edge deletions: The average running time for deleting
1,000 edges in the reverse of the order that they wereadded, from the index constructed using the whole network.

• Degree: A baseline method that chooses the topmost kvertices in decreasing order of degrees.
• MC [15]: A simulation-based influence estimation methodthat simulates the diffusion process 10,000 times, andcalculates the average number of activated vertices.

7.2

Index construction

For each network, we constructed our index using the entire network. The indexing times and index sizes are presented in Table 2. From this, we can observe the scalability
and efficiency of our method. For the larger three networks,
which incorporate tens of millions of edges, it only requires3

http://sourceforge.net/projects/timplus/
http://sourceforge.net/projects/im-imm/
5
https://github.com/todo314/pruned-monte-carlo/
6
The code is provided by Kyomin Jung, an author of [14].
4

Dynamic updates

In this section, we evaluate the efficiency of our methods
in terms of dynamic updates. Specifically, we have measured
the running time of each operation as follows.

Table 2 presents the average running times of the dynamic
update operations. Each vertex addition and edge deletion
is processed within a few milliseconds. An edge addition requires several ten milliseconds for the three largest networks,
under the TR setting, and requires a few milliseconds under
the WC setting. The reason for this is that under the TR
model, sketches are likely to expand more following the addition of edges in comparison with the WC model. Vertex
deletion exhibits a similar tendency to edge addition, where
it becomes slower for the probability setting of TR. Figure 4
suggests that the average processing times of dynamic operations are roughly proportional to the value of β, because
the expected size of I is proportional to β.

1085

Table 2: Indexing time, index size, and average processing times of dynamic updates.
DatasetModel

Indexing
time

Index
size

Vertexaddition

Vertexdeletion

ProbabilitychangeEdgeadditionEdge
deletion

Digg

TR
WC

36.3 s20.3 s

3.0 GB
1.4 GB

2.6 ms
1.6 ms

2.9 ms
4.0 ms0.59 ms
0.92 ms

0.32 ms
0.81 ms

0.39 ms
1.3 ms

Enron

TR
WC

27.3 s
16.5 s

0.6 GB
0.6 GB

0.46 ms
0.33 ms

8.1 ms
4.6 ms

3.4 ms
1.4 ms

1.2 ms0.39 ms

1.2 ms
0.94 ms

Epinions

TRWC

89.1 s62.2 s

1.4 GB
1.1 GB

0.80 ms
0.69 ms

14.8 ms
8.3 ms

5.8 ms
1.7 ms

4.1 ms
1.0 ms

1.0 ms
1.8 msFacebookTRWC

165.0 s135.2 s2.1 GB
1.6 GB

2.7 ms
2.7 ms95.8 ms
61.0 ms

11.1 ms
3.6 ms

6.9 ms
1.2 ms0.75 ms
2.3 ms

DBLP

TR
WC

2,965.9 s
3,395.7 s

27.7 GB34.8 GB5.2 ms
4.0 ms

124.0 ms
18.1 ms

85.7 ms
2.7 ms42.5 ms
0.87 ms

2.1 ms
1.3 msYouTubeTRWC

5,000.4 s
1,985.5 s

44.6 GB
3.9 GB

0.01 ms
0.65 ms

92.2 ms
5.7 ms236.2 ms
1.5 ms31.8 ms
0.14 ms

0.26 ms
0.04 ms

FlickrTRWC

5,467.6 s
4,253.7 s

31.3 GB12.2 GB

0.00 ms
2.1 ms459.0 ms
53.8 ms

125.2 ms
4.8 ms

89.6 ms
0.19 ms

2.4 ms0.08 ms

Table 3: Effectiveness of the proposed techniques compared to naive implementations.
Edge deletion

Vertex deletion

Vertex addition

Index size

DatasetModel

Sec. 6.1

Naive

Sec. 6.1

Naive

Sec. 6.2

Naive

Sec. 6.3

Naive

EpinionsTRWC

1.0 ms
1.8 ms163.1 ms
1.4 ms

14.8 ms
8.3 ms575.3 ms
7.4 ms0.80 ms
0.69 ms

1.6 ms
6.4 ms

1.4 GB
1.1 GB

5.5 GB
7.0 GB

YouTubeTRWC

0.26 ms
0.04 ms

597.9 ms
0.05 ms

92.2 ms
5.7 ms> 10,000.0 ms
4.4 ms0.01 ms
0.65 ms

5.6 ms
5.9 ms

44.6 GB
3.9 GB

250.0 GB179.7 GBTR
2.4 ms 1,705.5 ms 459.0 ms > 10,000.0 ms 0.00 ms
6.5 msWC
0.08 ms
0.10 ms
53.8 ms
41.2 ms
2.1 ms 33.6 ms∗ We report twice the index size for β = 16 as an approximation of that for β = 32.

31.3 GB12.2 GB∗ ≈ 282.0 GB∗ ≈ 292.1 GB

Flickr

10

0

10

-1

Average processing time [s]

1

TR
WC

103
102
101
0

10

2

1

2

2

2

3

2

4

5

2
2
Value of β

6

2

7

2

8

2

9

(a) Indexing time

10

2

1

2

2

2

3

2

4

5

2
2
Value of β

6

2

7

2

8

2

100

Vertex addition
Vertex deletion

10-1
10-2
10-3
-4

10

9

2

(b) Index size

Average processing time [s]

104

TR
WC

Memory usage [GB]Indexing time [s]

102

1

2

2

2

3

2

4

5

2
2
Value of β

6

2

7

2

8

2

9

(c) Vertex operations (TR)100

Probability change
Edge addition
Edge deletion

10-1
10-2
-3

10

-4

10

-5

10

2

1

2

2

2

3

2

4

5

2
2
Value of β

6

2

7

2

7.4

Influence estimation

Now, we will show that our method efficiently and accurately estimates the influence spread using the index constructed from a given graph. As the exact computationof the influence spread is #P-hard, we regard the estimate

given using MC as the ground truth of the influence spread.
First, we focus on the influence estimation for a single vertex. For each network, we randomly sampled 1,000 vertices,and then estimated the influence spread for each vertex. Table 4 presents the average estimation time for each method.
The average query time for our method is of the order ofa few microseconds, which is several orders of magnitude
faster than both RIS and MC. Therefore, once we construct
our index, we can perform efficient tracking of influential
vertices. Figure 5 indicates that the average estimation time
is robust against changes in β, because it requires only constant time, as described in Section 4.3.1.
Figure 7 illustrates the accuracy of our method, where
each point corresponds to a seed set consisting of a single
vertex, and the x and y coordinates represent the influence

1086

2

(d) Edge operations (TR)Figure 4: The change of indexing time, index size, and average processing times of dynamic updates with
the increase of β on Epinions.
Next, we analyze the effectiveness of the proposed speedup techniques introduced in Section 6.1 and 6.2. Table 3
presents the average running times of dynamic updates bothwith and without the proposed pruning techniques. The
proposed techniques improve the performances of edge deletion, vertex deletion, and vertex addition, making them up
to 2,000, 100, and 500 times faster, respectively. Notice that
our techniques for deletion operations have more effectiveness for larger networks.

89

Table 4: Average running time for estimating theinfluence spread of a single vertex.
Static methods

DatasetModel

Indexing

Query

MC

RIS

Epinions

TRWC

89.1 s62.2 s

0.97 µs
0.96 µs

6.3 s
0.01 s

8.7 s
9.3 s

1

TR
WC

22

23

48.0 s0.02 s267.1 s298.1 s24 25 26
Value of β

27

28

29

Figure 5: Average times
for estimating influenceof a single vertex with β
on Epinions.

0.6
0.4

TR
WC
21

22

23

24 25 26
Value of β

27

28

29

0

21

22

23

24 25 26
Value of β

27

28

29

(a) Root mean squared error (b) Rank correlation coefficient

100

TR
WC

10-6

10-7 12

1.62 µs
1.41 µs
Average estimation time [s]Average estimating time [s]10-52,965.9 s
3,395.7 s

0.8

0.2
0.1

DBLP

1
TR
WC
Value of ρ

Root mean squared error

This work

10

Figure 8: Accuracy improvements of influence estimation with the increase of β on Epinions.

-1

10

10-2
10-3
10-4

TR
WC
TR naive
WC naive

10-5
10-6

1

2

4

8
16
Seed size k

32

7.5
64

Figure 6: Average times
for estimating influenceof a vertex set of various
sizes on Epinions.

(a) Epinions (TR, β = 1) (b) Epinions (TR, β = 32)
Figure 7: Correlation between the ground truth andinfluence estimation calculated by our method.

spreads computed by MC and our method, respectively. It
can be seen that as β increases, our method becomes moreaccurate. Even when β = 1, our method is stable, in thesense that all the points are close to the diagonal (i.e., theline of y = x) and we do not have any outliers. This property is desirable, because such outliers would result in hugeerrors when we want to maximize the influence spread. We
here justify our choice of parameter β. We plotted the root
mean squared error and Spearman’s rank correlation coefficient between the influence estimations of our method withvarious values of β and those from MC, as presented in Figure 8. Higher values of β yield more accurate influence estimations, but the improvements are limited when β > 32.
Because the efficiency of index construction and dynamic
updates depends on the value of β, we adopted β = 32 as asweet spot between accuracy and efficiency.
Next, we evaluate the efficiency of the influence estimation
for a set of multiple vertices. We randomly generated 1,000
vertex sets of a specific size, and then estimated the influencespread for each vertex set. Figure 6 presents the average
estimation times for a vertex set of sizes ranging from 1 to
64. The estimation times are scaled to the seed set size, andunder one millisecond is required for a seed set of size 64,
which is 10–100 times faster than the required times without
our speed-up technique.

Influence maximization

Finally, we will demonstrate that our method processes influence maximization queries efficiently and accurately using
the index constructed from a given graph.
Figure 9 summarizes the running times required to compute seed sets of sizes 1, 10, 20, . . . , 100 after reflecting allof the edges in each network. Note that the running times
do not include the times needed to read the input graphfrom a secondary storage location. Both TIM+ and IMM
did not finish within two hours on Flickr (TR, k ≥ 1). Our
method returns a seed set within 20 seconds for all of the settings, whereas other state-of-the-art static methods requirea time of at least one order of magnitude longer. It should
be noted that finding a seed set of the same quality that our
method delivers from scratch requires ten times longer, as
the performance of RIS demonstrates. We can also observe
the robustness of our method against the seed size k, while
TIM+ , IMM, and IRIE become slower as k increases.
Figure 10 presents the influence spread for seed sets ofsizes 1, 10, 20, . . . , 100, as computed using each method. As
we can see, our method and RIS deliver almost the same
quality. This is not a coincidence, because we have a theoretical guarantee that both our method and RIS generate indices sampled from the same distribution. TIM+ , IMM, andPMC also gave seed sets of a similar quality to our method,
and this is because they also have accuracy guarantees. IRIE
and Degree perform comparatively badly on Enron (TR).

8.

CONCLUSIONSIn this paper, we proposed the first fully-dynamic index
data structure for influence analysis on an evolving network.
Our indexing method can instantly incorporate graph updates of any kind, and it can efficiently answer the two kindsof queries, influence estimation and influence maximization,on the latest graph snapshot. Our thorough theoretical analysis guarantees the non-degeneracy of our update algorithms
and solution accuracy for our query algorithms. Moreover,
we developed several speed-up techniques that drasticallyreduce both the time and space consumptions.
Experimental results on real dynamic networks demonstrated that our method is able to update the index several orders of magnitude faster than reconstructing an index from scratch owing to the proposed speed-up techniques.
Furthermore, comparing with existing static methods for influence estimation and influence maximization, we verified
the efficiency and accuracy of our query algorithms.

1087

TIM+

103

103

102
101
100
-1

10

IMM

102
101
100
-1

10

10-2

10-2
0

20

40
60
Seed size k

80(a) Enron (TR)

100

0

20

40
60
Seed size k

80

100

in-Aid for JSPS Research Fellow (No. 16J09440). T. A.
was supported by JSPS Grant-in-Aid for Research Activity Startup (No. 15H06828) and JST, PRESTO. Y. Y. was
supported by JSPS Grant-in-Aid for Young Scientists (B)(No. 26730009), MEXT Grant-in-Aid for Scientific Researchon Innovative Areas (No. 24106003), and JST, ERATO,
Kawarabayashi Large Graph Project.

9.

REFERENCES[1] E. Adar and L. A. Adamic. Tracking information epidemics
in blogspace. In WI, pages 207–214, 2005.
[2] A. Anagnostopoulos, R. Kumar, and M. Mahdian.
Influence and correlation in social networks. In KDD, pages
7–15, 2008.
[3] C. Borgs, M. Brautbar, J. Chayes, and B. Lucier.
Maximizing social influence in nearly optimal time. In
SODA, pages 946–957, 2014.
[4] W. Chen, C. Wang, and Y. Wang. Scalable influencemaximization for prevalent viral marketing in large-scalesocial networks. In KDD, pages 1029–1038, 2010.
[5] W. Chen, Y. Wang, and S. Yang. Efficient influencemaximization in social networks. In KDD, pages 199–208,
2009.
[6] X. Chen, G. Song, X. He, and K. Xie. On influential nodes
tracking in dynamic social networks. In SDM, pages
613–621, 2015.
[7] J. Cheng, L. Adamic, P. A. Dow, J. M. Kleinberg, andJ. Leskovec. Can cascades be predicted? In WWW, pages
925–936, 2014.
[8] S. Cheng, H. Shen, J. Huang, G. Zhang, and X. Cheng.
StaticGreedy: Solving the scalability-accuracy dilemma in
influence maximization. In CIKM, pages 509–518, 2013.
[9] P. Domingos and M. Richardson. Mining the network valueof customers. In KDD, pages 57–66, 2001.
[10] N. Du, L. Song, M. Gomez-Rodriguez, and H. Zha. Scalable
influence estimation in continuous-time diffusion networks.
In NIPS, pages 3147–3155, 2013.
[11] J. Goldenberg, B. Libai, and E. Muller. Talk of the
network: A complex systems look at the underlying process
of word-of-mouth. Marketing Letters, 12(3):211–223, 2001.
[12] J. Goldenberg, B. Libai, and E. Muller. Using complex
systems analysis to advance marketing theory development:
Modeling heterogeneity effects on new product growththrough stochastic cellular automata. Academy ofMarketing Science Review, 9(3):1–18, 2001.
[13] A. Goyal, F. Bonchi, and L. V. Lakshmanan. Learning
influence probabilities in social networks. In WSDM, pages
241–250, 2010.
[14] K. Jung, W. Heo, and W. Chen. IRIE: Scalable and robust
influence maximization in social networks. In ICDM, pages
918–923, 2012.

Degree195000190000185000180000204060Seed size k(a) Enron (TR)Figure 9: Running times for extracting a seed setof size from 1 to 100 for each algorithm.

IRIE
2000000(b) Flickr (TR)Acknowledgments. N. O. was supported by JSPS Grant-

PMC
4400
4200
4000
3800
3600
3400
3200
3000
2800
2600

Influence spread

104
Influence spread

RIS

Running time [s]Running time [s]This work
104

80

100

0

20

40
60
Seed size k

80

100

(b) Flickr (TR)Figure 10: The influence spreads of a seed set ofsize from 1 to 100 computed by each algorithm.
[15] D. Kempe, J. Kleinberg, and É. Tardos. Maximizing the
spread of influence through a social network. In KDD,
pages 137–146, 2003.
[16] M. Kimura, K. Saito, and R. Nakano. Extracting influential
nodes for information diffusion on a social network. In
AAAI, pages 1371–1376, 2007.
[17] R. Kumar, J. Novak, and A. Tomkins. Structure andevolution of online social networks. In Link Mining:
Models, Algorithms, and Applications, pages 337–357.
Springer, 2010.
[18] J. Leskovec, J. Kleinberg, and C. Faloutsos. Graphevolution: Densification and shrinking diameters. ACM
Transactions on Knowledge Discovery from Data, 1(1):2,
2007.
[19] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos,
J. VanBriesen, and N. Glance. Cost-effective outbreak
detection in networks. In KDD, pages 420–429, 2007.
[20] B. Lucier, J. Oren, and Y. Singer. Influence at scale:
Distributed computation of complex contagion in networks.
In KDD, pages 735–744, 2015.
[21] M. Minoux. Accelerated greedy algorithms for maximizing
submodular set functions. Optimization Techniques,
7:234–243, 1978.
[22] S. A. Myers, C. Zhu, and J. Leskovec. Information diffusionand external influence in networks. In KDD, pages 33–41,
2012.
[23] G. Nemhauser, L. Wolsey, and M. Fisher. An analysis of
the approximations for maximizing submodular set
functions. Mathematical Programming, 14:265–294, 1978.
[24] N. Ohsaka, T. Akiba, Y. Yoshida, and K. Kawarabayashi.
Fast and accurate influence maximization on large networks
with pruned monte-carlo simulations. In AAAI, pages
138–144, 2014.
[25] M. Richardson and P. Domingos. Mining knowledge-sharing
sites for viral marketing. In KDD, pages 61–70, 2002.
[26] K. Saito, R. Nakano, and M. Kimura. Prediction of
information diffusion probabilities for independent cascade
model. In KES, pages 67–75, 2008.
[27] J. K. Salmon, M. A. Moraes, R. O. Dror, and D. E. Shaw.
Parallel random numbers: as easy as 1, 2, 3. In SC, pages
1–12, 2011.
[28] Y. Tang, Y. Shi, and X. Xiao. Influence maximization innear-linear time: A martingale approach. In SIGMOD,
pages 1539–1554, 2015.
[29] Y. Tang, X. Xiao, and Y. Shi. Influence maximization:
Near-optimal time complexity meets practical efficiency. In
SIGMOD, pages 75–86, 2014.
[30] Y. Wang, G. Cong, G. Song, and K. Xie. Community-based
greedy algorithm for mining top-k influential nodes inmobile social networks. In KDD, pages 1039–1048, 2010.
[31] H. Zhuang, Y. Sun, J. Tang, J. Zhang, and X. Sun.
Influence maximization in dynamic social networks. In
ICDM, pages 1313–1318, 2013.

1088