TIM consists of two phases as follows:
1.Parameter Estimation. This phase computes a lower-bound of the maximum expected spread among all size-k node sets, and then uses the lower-bound to derive a parameter θ.
2.Node Selection. This phase samples θ random RR sets from G, and then derives a size-k node set Sk that covers a large number of RR sets. After that, it returns Sk as the final result.
Node Selection
Algorithm 1 NodeSelection (G, k, θ)
1: Initialize a set R = ∅.
2: Generate θ random RR sets and insert them into R.
3: Initialize a node set Sk = ∅.
4: for j = 1 to k do
5: Identify the node vj that covers the most RR sets in R.
6: Add vj into Sk.
7: Remove from R all RR sets that are covered by vj.
8: return Sk.
The generation of each RR set is implemented as a randomized bread-first search(BFS) on G.
Performance Bounds.
w(R) = ∑v∈R (the indegree of v in G)
Observe that if an edge is examined in the generation of R, then it must point to a node in R. Let EPT be the expected width of a random RR set. It can be verified that Algorithm 1 runs in O(θ * EPT) times.
Lemma 2. Let S be a fixed set of nodes, and v be a fixed node. Suppose that we generate an RR set R for v on a graph g that is constructed from G by removing each edge e with 1 - p(e) probability. Let ρ1 be the probability that S overlaps with R,and ρ2 be the probability that S, when used as a seed set, can activate v in an influence propagation process on G. Then,ρ1 = ρ2.
R : the set of all RR sets. FR(S) : the fraction of RR sets in R covered by S.
Based on Lemma 2, we can prove that: COROLLARY 1.E[n * FR(S)] = E[Ⅰ(S)].
Let OPT be the maximum expected spread of any size-k node set in G.Based on Chernoff bounds,we have this conclusion:
Lemma 3. Suppose that θ satisfies
θ ≥ (8 + 2ε)n * (l * log n + log(n, k) + log 2)/(OPT * ε^2). (2)
Then, for any set S of at most k nodes, the following inequality holds with at least 1 - n^(-l)/(n, k) probability:
|n * FR(S) - E[Ⅰ(S)]| < ε/2 * OPT.
Based on Lemma 3,we prove that :
Theorem 1. Given a θ that satisfied (2), Algorithm 1 returns a (1 - 1/e - ε)-approximate solution with at least 1 - n^(-l) probability.
We define λ = (8 + 2ε)n * (l * log n + log(n, k) + log 2)/ε^2, and we rewrite (2) as
θ ≥ λ/OPT. (5)
Parameter Estimation
Algorithm 2 KptEstimation(G, k)
1: for i = 1 to logn - 1 do
2: Let ci = (6 * l * logn + 6 * log(logn)) * 2^i.
3: Let sum = 0.
4: for j = 1 to ci do
5: Generate a random RR set R.
6: k(R) = 1 - (1 - w(R)/m)^k.
7: sum = sum + k(R).
8: if sum/ci > 1/2^i then
9: return KPT* = n * sum/(2 * ci)
10: return KPT* = 1
Our objective is to identify an θ that makes θ * EPT reasonably small, while still ensuring θ ≥ λ/OPT.We first define a probability distribution V* over the nodes in G,such that the probability mass for each node is proportional to its in-degress in G.We hava the following lemma:
Lemma 4. n/m * EPT = E[Ⅰ({v*})]
In other words,if we randomly sample a node from V* and calculate its expected spread s, then on average we have s = n/m * EPT. This implies that n/m * EPT ≤ OPT.
Suppose that we are able to identify a number t such that t = Ω(n/m * EPT) and t ≤ OPT. Then,by setting θ = λ/t, we can guarantee that Algorithm 1 is correct and has an expected time complexity of Ο(θ * EPT) = O(m/n * λ) = Ο((k + l)(m + n)logn/ε^2). (6)
Choice of t.
if t = n/m * EPT , then θ may be too large,whitch in turn leads to inferior efficiency.
Suppose that we take k samples from V*, and use them to form a node set S*. (Note that S* may contain fewer than k nodes due to the elimination of duplicate samples.) Let KPT be the mean of the expected spread of S*.It can be verified that
n/m * EPT ≤ KPT ≤ OPT, (7)
and that KPT increases with k. We also hava the following lemma:
Lemma 5.Let R be a random RR set and w(R) be the width of R. Define
k(R) = 1 - (1 - w(R)/m)^k. (8)
Then, KPT = n * E[k(R)], where the expectation is taken over the random choices of R.
By Lemma 5, we can estimate KPT by first measuring n*k(R) on a set of random RR sets, and then taking the average of the measurements. By Chernoff bounds,if we are to obtain an estimate of KPT with δ ∈ (0, 1) relative error with at least 1 - 1/n^l probability, then the number of measurements should be Ω(l * n * logn /(δ^2 * KPT)). We resolve this dilemma with an adaptive sampling approach.
Estimation of KPT.
We first generate a relatively small number of RR sets, and use them to derive an estimation of KPT with a bounded absolute error. If th estimated value of KPT is much larger then the error bound, we infer that the estimation is accurate enough, and we terminate the algorithm. On the other hand, if the estimated value of KPT is not large compared with the error bound, then we generate more RR sets to obtain a new estimation of KPT with a reduced absolute error.
Theoretical Analysis.
Based on Chernoff bounds,we have the following result:
Theorem 2. When n ≥ 2 and l ≥ 1/2, Algorithm 2 returns KPT* ∈ [KPT/4, OPT] with at least 1 - 1/n^l probability, and runs in Ο(l * (m+n) * log n) expected time. Furthermore, E[1/KPT*] < 12/KPT.
In summary, our TIM algorithm works as follows.Given G, k, and two parameters ε and ι, TIM first feeds G and k as input to Algorithm 2, and obtains a number KPT* in return. After that, TIM computes θ = λ/KPT*, where λ is as defined in Equation 4 and is a function of k, ι, n, and ε. Finally, TIM gives G, k, and θ as input to Algorithm 1, whose output Sk* is the final result of influence maximization.
TIM runs in Ο((k + l)(m + n)logn/ε^2) expected time, and returns a (1 - 1/e - ε)-approximate solution with at least 1 - 2*n^(-l) probability.This success probability can easily increased to 1 - n^(-l), by scaling l up by a factor of 1 + log2/logn. Finally, we note that the time complexity of TIM is near-optimal under the IC model, as it is only a logn factor larger then the Ω(m+n) lower-bound proved by Borgs et al.
