Influence Maximization in Big Networks: An Incremental Algorithm for Streaming Subgraph Influence Spread Estimation

1 Introduction

Social networks is of vital importance in information diffusion and viral marketing. Influence maximization in social networks is defined as finding a subset of nodes that can trigger the largest number of users propagating the given information. The problem can be formulated as a discrete optimization problem under the independent cascade model (IC) and the linear threshold model (LT) [Kempe et al., 2003]. It has been proved NP-hard, and a greedy algorithm is favored. However, heavy Monte-Carlo simulations are needed to estimate the influence spreads of different seed sets at each iteration. As social networks increase in size continuously, greedy algorithms are inapplicable of processing big networks.

Many efforts have been made to explore scalable algorithms in big netowrks. An intuitive idea is to use heuristic algorithms, i.e. DegreeDiscount [Chen et al., 2009], PMIA [Chen et al., 2010], IRIE [Jung et al., 2011], GroupPageRank [Liu et al., 2014]. However, these algorithms are not robust with respect to network structures. On the other hand, many advanced greedy algorithms, i.e. [Leskovec et al., 2007], [Goyal et al., 2011], [Zhou et al., ], have been proposed to speedup seed selection. These methods focus on pruning unnecessary Monte-Carlo simulations in selecting new influential nodes. Unfortunately, these algorithms are still incapable of processing big networks with hundreds of millions of nodes because of unavoidable cost of simulating influence cascades. Moreover, all these greedy methods are designed on static networks and cannot be generalized to dynamic networks which commonly occur in reality.

In this paper, we propose an incremental algorithm for estimating the expected influence spread of seed nodes and evaluate the performance under influence maximization. Specifically, the algorithm breaks down a big network into a large number of small subgraphs, and then processes these subgraphs as data streams. The results on subgraphs are joined to recover the global result in the whole network. The nature of incremental processing also enables it to handle dynamic networks where network structures change over time.

The main challenge of the problem is that small subgraphs derived from a big network are not independent. For example, as in Figure 1, the two subgraphs on the right hand side share nodes 4, 5, 7 and even worse, two subgraphs may share common edges. In this case, MC simulation results on subgraphs (defined as snapshots) may not be directly addable or even conflict with each other. In this work, we assume that edges between different subgraphs are disjoint and each subgraph is converted as a class of Strongly Connected Components (SCCs). SCCs on subgraphs are joined to form snapshots or SCCs of the whole network, and different combinations of simulations on subgraphs generate independent samples. In experiments, we demonstrate that the solution outperforms heuristics and existing MC simulation based methods.

The merits of the proposed incremental algorithm are summarized as follows:

• A big network is broken down into subgraphs and the "coin flip" technique [Kempe et al., 2003] is applied to generate snapshots on each subgraph. Subgraphs can be processed in parallel.
• Snapshots on subgraphs are converted to be a class of

Strongly Connected Components (SCCs). Snapshots on different subgraphs are joined to restore the global result of the original network.

• The number of snapshot joins increases polynomially with the number of subgraphs, which significantly reduces the complexity of MC simulations.
• Snapshots are incrementally maintained and updated such that replicated simulations can be avoided when changing seed sets.

2 RelatedWork

Data intensive applications such as data streams motivate incremental learning algorithms. Incremental learning is advantageous when dealing with very large or non-stationary data. Existing incremental learning algorithms can be categorized into two groups: approximate incremental learning [Kivinen et al., 2004] and exact incremental learning [Laskov et al., 2006]. Typical examples include the incremental SVM [Poggio, 2001] and PCA models [Balsubramani et al., 2013]. However, these models were proposed to handle vectorial training data with the Identical and Independent Distributions (IID) assumption. Incrementally learning from subgraph data without the IID assumption has not been addressed before.

In the domain of network influence maximization, most existing models cannot handle big networks with hundreds of millions of nodes due to heavy Monte-Carlo computation. The typical algorithm Cost-Effective Lazy Forward (CELF) [Leskovec et al., 2007] greatly reduce the number of influence spread estimations and is 700 times speed-up against previous greedy algorithms. Unfortunately, these improved greedy algorithms are still inefficient due to too many MonteCarlo simulations for influence spread estimation. StaticGreedyDU [Cheng et al., 2013] reuses snapshots generated from a given graph and reduces the number of simulations by two orders of magnitude, meanwhile the performance is almost the same as the original greedy algorithm. Recent work [Ohsaka et al., 2014] includes a Pruned BFS method and community-based methods, i.e. [Wang et al., 2010], [Chen et al., 2014]. Unlike these work, our method scales well to big networks by breaking down the big network into small subgraphs for fast spread estimation.

3 Preliminaries

Let G = (V,E) be an undirected graph with a node set V of size |V | and an edge set E of size |E|. Without loss of generality, we use the independent cascade (IC) model as the propagation model. A node subset S ⊆ V is called a seed set if we first activate nodes in S. Given a seed set S, its influence spread σ(S) is defined as the expected number of nodes eventually activated. Formally, the influence maximization problem is to find the optimal seed set S∗ such that S∗ = argmaxS⊆V ;|S|=kσ(S), where |S| stands for the number of elements in S, and k is a predefined integer.

To solve the influence estimation problem, one needs to estimate σ(S) for any given S. However, exact computation of σ(·) is #P-hard [Chen et al., 2010], so in practice MonteCarlo simulations are employed to estimate σ(S):

• Propagation Simulation. The influence spread is obtained by directly simulating the random process propagating from a given seed set S. Let Ai denote the set of nodes newly activated in the i-th iteration and we have A0 = S. In the i + 1-th iteration, each node u ∈ Ai has a single chance to activate its each inactive neighbor v with probability puv. If v is activated, it is added to Ai+1. The process stops when AT+1 = ∅ the first time for some T. And | ˜X(S)| = |A0 ∪ A1 ∪ · · ·AT | is the influence spread of this single simulation. We run such simulations for many times and obtain the estimated expected influence spread σ(S) by averaging over all simulations.
• Snapshot Simulation. Based on "coin flip" [Kempe et al., 2003], we flip coins in advance to produce a snapshot X = (V,E′ ), which is a sampled subgraph of G, where an edge uv is either kept with the probability puv or removed, such that E′ ⊆ E. Thus, in this specific snapshot X the influence spread for the given seed set S, denoted as |X(S)|, equals to the number of nodes reachable from S. We generate a large number of snapshots and obtain the estimated expected influence spread σ(S) by averaging over all the generated snapshots.

The above two simulation methods are equivalent, because | ˜X(S)| and |X(S)| share the same probability distribution [Kempe et al., 2003]. In this work, we use snapshot simulations because we need to frequently estimate the influence spread of different seed sets when choosing new seeds to S∗ .

4 ProblemFormulation

The basic idea of the paper is to break down a big network into small subgraphs and analyze the reachability of nodes on each subgraph independently. The results from each subgraph are joined to restore the results on the original network.

We use Figure 1 to explain the incremental subgraph algorithm. Figure 1(a) is the original network that each edge is associated with a propagation probability puv, u, v ∈ {1, 2, · · · , 8}. For simplicity, assume the edges in the graph are split into two disjoint sets and two subgraphs are obtained as shown in Figures 1(b) and (c). The propagation probability puv on each edge in the subgraphs is inherited from the original network. This way, the original graph is broken down into two small and tractable subgraphs and incremental learning can be applied to the subgraphs.

Consider that the original network G = (V,E) is broken down into N subgraphs G1 = (V1,E1),G2 =

(V2,E2), · · · ,GN = (VN,EN) with V1∪V2∪· · ·∪VN = V , E1 ∪ E2 ∪ · · · ∪ EN = E, and Ei ∩ Ej = ∅, 1 ⩽ i, j ⩽ N. In dynamic networks with increasing nodes and edges, we keep increasing nodes and edges as new streaming subgraphs denoted by GN+1 = (VN+1,EN+1), · · · . Then, we use the "coin flip" method on each subgraph Gi for M times and generate M snapshots. Denote these snapshots on Gi as X(i) 1 ,X(i) 2 , · · · ,X(i) M . Then, our problem turns to given a seed set in a big network, incrementally learning snapshots generated from N subgraphs to estimate the influence spread of the seed set in the original big network.

5 The Incremental Algorithm

5.1 Expression of Influence

First, each snapshot Xr of the original network can be represented by a m-dimensional binary vector r = (ruv)uv∈E, where ruv = 1 if edge uv is activated in a coin flipping; otherwise, ruv = 0. We call r a representation vector of Xr. The closed set of all possible snapshot representation vectors is denoted by R as follows,

Under the IC model assumption, the probability distribution on R is given by

If the original graph is broken down into N subgraphs, the snapshot we get by restricting Xr on subgraph Gi is denoted by X(i) r = Xr|Gi with the representation vector r(i) = (ruv)uv∈Ei . Obviously, the marginal distribution of r(i) is q(r(i) ) = ∏uv∈Ei (puv)ruv (1 - puv)1-ruv , which similarly describes the distribution of snapshots on subgraph Gi. These distributions satisfy the following equation q(r) = q(r(1) )q(r(2) )·· · ··q(r(N) ). Therefore, subgraphs can be processed incrementally by using the network decomposition.

We introduce the symbol "⊕" as the join operator in the equation Xr = X(1) r ⊕X(2) r ⊕· · ·⊕X(N) r , which means that Xr can be broken down into N snapshots X(i) r , 1 ⩽ i ⩽ N, where X(i) r is the snapshot corresponding to subgraph Gi. Conversely, if snapshots X(i) r , 1 ⩽ i ⩽ N are increasingly obtained from subgraphs, we can join them to restore the snapshot Xr of the original network. Hence the equation Xr = X(1) r ⊕ X(2) r ⊕ · · · ⊕ X(N) r interprets the relationship between Xr and X(i) r . Let N(S;Xr) denote the set of nodes reachable from the seed set S in a specific snapshot Xr. The expected influence spread σ(S) of the seed set S can be described as follows,

We can observe from the above equation that σ(S) is determined by |N(S;Xr)| = |N(S;X(1) r ⊕X(2) r ⊕· · ·⊕X(N) r )|. Thus, we explain how to use the snapshots generated from these N subgraphs to estimate the expected influence spread of a given seed set in the original network.

Algorithm 1: The join of SCC classes.

Input: C1 = {C11,C12, · · · ,C1α1 } and C2 = {C21,C22, · · · ,C2α2 } Output: A class of SCCs after joining of C1 and C2 1 function join(C1, C2) 2 for j = 1, 2, · · · , |C2| = α2 do 3 s = 1, C ← ∅, C ← ∅; 4 for i = 1, 2, · · · , |C1| do 5 if C1i ∩ C2j ̸= ∅ then 6 if C2j ⊆ C1i then return C1; 7 else C ← C ∪ C1i; 8 else 9 Cs ← C1i; C ← {C, Cs}; s ← s + 1 10 C ← {C,C}; C1 ← C 11 return C1

For any snapshot X in the network G = (V, E), we have u → v if node v is reachable from node u on the snapshot X. We say the two nodes u and v are equivalent (u ↔ v) if and only if both u → v and v → u are satisfied. Also, we define that each node u is equivalent to itself, u ↔ u.

Based on the definitions, a set of nodes C = C(u;X) = {v|v ↔ u on X, v ∈ V } is called a Strongly Connected Component (SCC) of X represented by the node u. The set C is either a node {u} or equivalent nodes. This way, the snapshot X can be described by a class of SCCs C = {C(u;X), u ∈ E} = {C1, C2, · · · }, where C1, C2, · · · are disjoint sets, and C1 ∪ C2 ∪ · · · = E. Also, SCCs are used for memory-saving and efficient calculation.

As we aim to find the most influential nodes, single sets in class C can be removed. Then, C = {C1,C2, · · · ,Cα} with |Ci| ≥ 2, ∀i ∈ {1, 2, · · · , α}. And the elements of N(S; Xr) can be described as follows,

Based on the above equation, we join SCCs on subgraphs to restore the result on the original network.

5.2 Join of the SCCClasses

Consider that we have transformed all the snapshot X(i) j , 1 ⩽ i ⩽ N, 1 ⩽ j ⩽ M generated from N subgraphs into classes of SCCs C (i) j = {C(i) jk , 1 ⩽ k ⩽ α(i) j , |C(i) jk | ⩾ 2}, where C (i) j is a SCC class of X(i) j . We have discussed that if the snapshots have been incrementally obtained on each subgraph, we can join them to obtain snapshots of the original network. Now, the problem turns to using the SCC classes of these N subgraphs to restore SCC classes of the original network. What we need to do next is to join the SCC classes of these subgraphs. We take N = 4 for example. Suppose we incrementally have C (1) j1 , C (2) j2 , C (3) j3 , C (4) j4 , where each C (i) ji is a SCC class of the subgraph Gi. In order to restore a SCC class of the original network, we can first join C (1) j1 , C (2) j2 to obtain C (1,2) j1,2 which is a SCC class of the subgraph G1⊕G2 ≜ (V1∪V2, E1∪E2), then C (3) j3 arrives and we increasingly join it with C (1,2) j1,2 to obtain C (1,2,3) j1,2,3 . At last, C (4) j4 arrives and we join it with C (1,2,3) j1,2,3 to obtain C (1,2,3,4) j1,2,3,4 , which is a SCC class of the original network. From this example, we can observe that the join of C (1) j1 , C (2) j2 , · · · , C (N) jN , 1 ⩽ j1, · · · , jN ⩽M can be reduced to the join of any two SCC classes.

Therefore, we define a function join(C1, C2) in Algorithm 1 to return the class after joining C1 = {C11, C12, · · · , C1α1 } and C2 = {C21,C22, · · · ,C2α2 }.

5.3 Influence Estimation

In this section, we first briefly introduce the traditional network influence estimation methods theoretically guaranteed by Theorem 1. When extending the traditional methods into streaming subgraphs, we can join the snapshots of subgraphs to restore samples of the original network. However, the join of subgraph snapshots exponentially increases with the number of subgraphs. So, we propose to select only a few number of snapshot joins. Proposition 3 explains that when the selected joins are independent and identically distributed (i.i.d.), the estimation converges fast. However, it is hard to select i.i.d. snapshot joins across subgraphs in reality. Therefore, we propose Definitions 1 and 2 to choose snapshot joins that approximately follow the i.i.d. condition. Proposition 3 shows that by using the approximation, we can use a polynomial number of snapshot joins to restore the global result.

For simplicity, |N(S;X(1) j1 ⊕ X(2) j2 ⊕ · · · ⊕ X(N) jN )| is denoted by gj1,j2,··· ,jN (S), which means that the snapshot of the original network can be obtained by incrementally joining the ji-th snapshot from the i-th subgraph, and gj1,j2,··· ,jN (S) returns the influence spread of a given seed set S. The representation vector of X(1) j1 ⊕ X(2) j2 ⊕ · · · ⊕ X(N) jN follows the distribution q(r). Hence for any 1 ⩽ j1, · · · , jN ⩽ M, gj1,j2,··· ,jN (S) is a random variable such that Egj1,j2,··· ,jN (S) = σ(S), where E is the expectation operator. Generally, M simulations are independently employed on the original network, generating M snapshots denoted by Xi = X(1) i ⊕ · · · ⊕ X(N) i , and σ(S) is empirically estimated by the following equation ̂ σ(S) = 1M ∑Mi=1 gi,i,··· ,i(S) where gi,i,··· ,i(S), 1 ≤ i ≤ M are bounded and i.i.d.. So the estimation is guaranteed by the following Theorem [Hoeffding, 1963],

Theorem1 (Hoeffding's inequality). Let Y1, · · · , YM be independent variables span over the interval [a, b], and SM ≜ Y1 + · · · + YM. Then, for all ε > 0,

In the traditional problem setting, components of the subscript of gi,i,··· ,i(S) are the same, because simulations are employed on a single network G and subscript (i, i, · · · , i) denotes the i-th snapshot simulation on G. Furthermore, snapshots on subgraphs are not obtained by independent simulations but by restricting snapshots of the original network on subgraphs. In contrast, our incremental algorithm considers that snapshots of subgraphs are generated independently and then joined to the previous results. Specifically, we first generate M snapshots X(1) j1 , 1 ⩽ j1 ⩽

M on subgraph G1, then the subgraph G2 arrives where we generate another M snapshots X(2) j2 , 1 ⩽ j2 ⩽ M. We join them to the snapshots of G1 and obtain snapshots X(1) j1 ⊕ X(2) j2 . The process continues until the N-th subgraph is joined. This way, we generate M N random variables gj1,j2,··· ,jN (S), 1 ⩽ j1, j2, · · · , jN ⩽ M such that Egj1,j2,··· ,jN (S) = σ(S). Unfortunately, it is not reasonable to take SΣ ≜ 1/M N ∑Mj1=1 · · · ∑MjN=1 gj1,j2,··· ,jN (S) as an estimation of σ(S). On the one hand, the number of snapshot joins M N exponentially increases with respect to the number of subgraphs. On the other hand, many snapshot joins are redundant when estimating the expected influence spread. To better explain these two points, we first rewrite SΣ as the average summation of M N-1 groups such that each group is the average summation of M independent and identically distributed random variables, i.e., SΣ = 1/M N-1 ∑MN-1 β=1 [1/M ∑Mα=1 gj (α,β) 1 ,··· ,j (α,β) N (S)] = 1/M N-1 ∑MN-1 β=1 Tβ, where gj (α,β) 1 ,··· ,j (α,β) N (S), 1 ⩽ α ⩽ M in Tβ are i.i.d.. Figure 2(a) shows the join of three snapshots of the original network and the first join snapshot is obtained by incrementally join X(1) 1 ,X(2) 1 ,X(3) 1 ,X(4) 1 . This join snapshot corresponds to the random variable g1,1,1,1(S). Similarly, the rest two corresponding random variables are g2,2,2,2(S) and g3,3,3,3(S). It is clear that these three are i.i.d. and the average summation is T1 = 1/3 [g1,1,1,1(S) + g2,2,2,2(S) + g3,3,3,3(S)]. Hence, Figure 2(a) corresponds to T1. Similarly, Figure 2(b), 2(c), 2(d) correspond to T2, T3, T4 respectively. Note that not all Tj are shown in the figure. Each Tj can be treated as some SM in Theorem 1 and Eq. (4) is satisfied, i.e., P(|Tj - σ(S)| ≥ ε) ⩽ 2 exp (- 2Mε2 (b-a)2 ). Therefore, each Tj has the same convergence rate as the traditional method. Next, our goal is to choose a portion of Tj to estimate the influence spread in order to obtain higher convergence rate. If the same convergence rate is required, our method needs fewer simulations on each subgraph than the traditional method. Moreover, our method can deal with dynamic networks.

For this goal, we first introduce the following proposition.

Proposition 2. If T1, · · · , Tk are independent and identically distributed random variables, then 1/k ∑ki=1 Ti has a higher convergence rate than the righthand side of Eq. (4).

Proof. By applying the independence and Hoeffding's lemma [Hoeffding, 1963], we have, for any t > 0

The first inequality is based on the Chebyshev's inequality. The second equality is guaranteed by the independence assumption of T1, · · · , Tk. The second inequality is due to the Hoeffding's lemma. The last inequality is the upper bound of the previous term after maximization with respect to t. The last item of the above equation shows that a higher convergence rate is obtained.

From the above proposition, the strategy is to choose those Tj that tend to be independent. Besides, the influence spread of a particular seed set is not only dependent on different snapshots X(i) j of subgraphs but also on different joins of them, which determines the network topology of the snapshot of the original graph. Hence, we define (j1, · · · , jN) as a join path with N - 1 stages (j1, j2), (j2, j3), · · · , (jN-1, jN).

Definition 1. We call two join paths (i1, i2, · · · , iN) and (j1, j2, · · · , jN) are orthogonal if there is no overlapping stage, i.e., (iα, iα+1) ̸= (jα, jα+1) for all 1 ⩽ α ⩽ N - 1.

Definition 2. Let Tβ1 = 1/M ∑Mα=1 gj (α,β1) 1 ,··· ,j (α,β1) N and Tβ2 = 1/M ∑Mα′=1 gj (α′,β2) 1 ,··· ,j (α′,β2) N .Tβ1 and Tβ2 are called join-independent if for any given α and α′ such that 1 ⩽ α′ , α ⩽ M, (j (α,β1) 1 , · · · , j (α,β1) N ) and (j (α′ ,β2) 1 , · · · , j (α′ ,β2) N ) are orthogonal.

For example, in Figure 2, T1, T2, T3 are pairwise joinindependent and there are paths in T1 and T4 with two overlapping stages. Now, we introduce the set T = {Tβ|Tβ1 , Tβ2 are join-independent, ∀Tβ1 , Tβ2 ∈ T }. We use Tβ ∈ T to estimate the influence spread. The following proposition shows how many Tβ are selected.

Proposition 3. Let T be the set of Tβ that are join-dependent pairwise, i.e., T = {Tβ|Tβ1 , Tβ2 are join-independent,∀Tβ1 , Tβ2 ∈ T }, then we have |T | =M.

Proof. All the paths in Tβ ∈ T form a set of paths P. Each candidate T corresponds to a unique P. All candidates T (or P) have the same cardinality. It can be verified that the set P0 = {(i, j, i, j, · · · ), 1 ⩽ i, j ⩽ M} is a portion of candidates P. So, we have |P| = |P0| = M 2 , which means |T | = M for Tβ ∈ T with M paths.

Algorithm 2: The Subgraph Incremental Algorithm.

Input: G = (V,E),G1 = (V1,E1), · · · ,GN = (VN , EN ), k, R, propagation probability p Output: the optimal seed set S that maximizes the influence on the original network 1 for i = 1, 2, · · · ,N do 2 for j = 1, 2, · · · ,M do 3 sample each edge with probability p on the i-th subgraph to obtain a snapshot X(i) j ; 4 use the DFS graph search to get a class of SCCs C (i) j ; 5 for i = 1, 2, · · · ,M do 6 for j = 1, 2, · · · ,M do 7 calculate Cij using the function join(·, ·) 8 S ←∅; 9 while |S| < k do 10 for v ∈ V \S do 11 σ(v|S) ← 0; 12 for i = 1, 2, · · · ,M do 13 for j = 1, 2, · · · ,M do 14 if v ↔ S then return σ(v|S); 15 else σ(v|S) ← σ(v|S) + |Cij (v)|; 16 t ← argmaxv∈V \S 1 M2 σ(v|S); 17 S ←S ∪ {t} 18 return S

Therefore, we regard ̂ σ(S) = 1/M ∑Tβ∈T Tβ as the estimation of the influence spread given the seed set S on the original graph. Though there may be many such T , from the proof of Proposition 3 it is easily can be seen that there exists some T0 such that the set all the paths in Tβ ∈ T0 equals P0. Hence one specific expression of ̂ σ(S) can be given by ̂ σ(S) = 1/M ∑Mi=1 ∑Mj=1 gi,j,i,j,···(S), where a polynomial number M 2 of snapshot joins are used.

5.4 Influence Maximization

In this section, we evaluate our estimation of the influence spread in the process of influence maximization. Greedy algorithm [Kempe et al., 2003] is adopted to select seed nodes, starting with an empty seed set S, and then add the node u with the maximummarginal influence in every iteration, i.e., u = argmaxv∈V \Sσ(S∪v)-σ(S), into S until the threshold k (|S| = k) is met. Because the influence spread function is non-negative, monotone and submodular, the accuracy of the optimum solution is guaranteed by f(S) ⩾ (1 - 1/e)f(S∗ ), where S∗ is the optimal solution [Nemhauser et al., 1978]]. We summarize the above in Algorithm 2.

Note that ̂ σ(S) is used in each iteration when the marginal influence is calculated ̂ σ(S ∪ v) - ̂ σ(S) = 1/M 2 ∑Mi=1 ∑Mj=1 [gi,j,i,j,···(S ∪ v) - gi,j,i,j,···(S)] = 1/M 2 ∑Mi=1 ∑Mj=1{|N(S ∪ v;X(1) i ⊕ X(2) j ⊕ · · · )| - |N (S; X(1) i ⊕X(2) j ⊕· · · )|} = 1/M 2 ∑Mi=1 ∑Mj=1 [1-I(S ↔ v)]|Ci,j(v)|, where I(S ↔ v) = 1 if ∃ s ∈ S such that s ↔ v, Ci,j(v) denotes the SCC including v on the snapshot

6 Experiments

We conduct experiments on four real-world data sets. All algorithms are implemented in C++ and run on a Windows 7 system with 2.3GHz CPU and 4GB memory.

6.1 Data Sets

We use four network datasets from snap.stanford.edu/data/ for testing and comparisons. The number of nodes and edges in each network is summarized in Table 1.

• ego-Facebook: This data set consists of 'circles' (or 'friends lists') from Facebook. It was collected from survey participants using the Facebook app.
• ca-HepPh and ca-CondMat: These two data sets are obtained from the e-print arXiv. If authors i and j publish a paper together, the network contains an edge connecting nodes i to j.
• email-Enron: Nodes of the network are email addresses and if an address i sent at least one email to address j, the graph contains an undirected edge from i to j.

6.2 BenchmarkMethods

We compare the incremental algorithm with five algorithms. The propagation probability of each edge is set to p = puv = 0.01, uv ∈ E.

• CELF: We set M = 10, 000 in the Monte-Carlo simulations to estimate the spread of a seed set.
• StaticGreedy: StaticGreedy reuses the generated snapshots to reduce the number of simulations. The number of snapshots is set to M = 10, 000.
• DegreeDiscount: This algorithm is developed for the IC model with the uniform propagation probability.
• PMIA: It uses maximization paths for influence spread estimation. The value of the parameter θ is set to 1/320.
• PageRank: We implement the power method with a damping factor of 0.85 and set the k highest-ranked nodes as seeds. The algorithm stops by the threshold value of 10-6 with the L1-norm.

6.3 Experimental Results

In our experiments, to obtain the influence spread of the heuristic algorithms for each seed set, we run 10,000 simulations and take the average spread as the influence spread, which matches the accuracy of greedy algorithms.

Influence spread. Figure 3 shows the influence spreads of different algorithms on the real-world networks with respect to the seed set size k. k increases from 1 to 50. From the figure, we can observe that our method performs the best in all settings. Together with CELF and StaticGreedy, our method is also independent of the network structures. Moreover, only M = 100 snapshots on each subgraph are generated to estimate the influence spreads in the process of selecting the most influential nodes. The results show much fewer MC simulations than the other greedy methods.

Running time. Figure 4 shows the running time under the optimal seed set of size 50 on the four datasets. Undoubtedly, heuristic methods, including DigreeDiscount, PMIA and PageRank, are the fastest. CELF is the slowest because too many MC simulations are employed during the estimation of influence spreads. We can observe that the speed of our algorithm is as fast as the StaticGreedy algorithm which is a popularly used scalable algorithm.

From these result, we can conclude that our algorithm is robust to network structures, performs the best compared with existing algorithms, and scale well to large networks.

7 Conclusions

In this paper, we presented an incremental algorithm for solving the big network influence maximization problem. Our idea is to break down the original graph into small subgraphs which can be sequentially processed as subgraph streams. Experimental results show that the algorithm is robust to network structures, performs the best compared with existing algorithms, and scale well to large networks.

Acknowledgments

This work was supported by the NSFC (No. 61370025), and the Strategic Leading Science and Technology Projects of CAS (No.XDA06030200), 973 project (No. 2013CB329605) and Australia ARC Discovery Project (DP140102206).