Dynamic influence maximization
Authors: Binghui Peng
Venue: NeurIPS 2021 Poster (2021)
Keywords: Influence maximization
submodular maximization
dynamic algorithm

Abstract: We initiate a systematic study on {\em dynamic influence maximization} (DIM). In the DIM problem, one maintains a seed set $S$ of at most $k$ nodes in a dynamically involving social network, with the goal of maximizing the expected influence spread while minimizing the amortized updating cost. We consider two evolution models. In the {\em incremental model}, the social network gets enlarged over time and one only introduces new users and establishes new social links, we design an algorithm that achieves $(1-1/e-\epsilon)$-approximation to the optimal solution and has $k \cdot\mathsf{poly}(\log n, \epsilon^{-1})$ amortized running time, which matches the state-of-art offline algorithm with only poly-logarithmic overhead. In the fully dynamic model, users join in and leave, influence propagation gets strengthened or weakened in real time, we prove that under the Strong Exponential Time Hypothesis (SETH), no algorithm can achieve $2^{-(\log n)^{1-o(1)}}$-approximation unless the amortized running time is $n^{1-o(1)}$.  On the technical side, we exploit novel adaptive sampling approaches that reduce DIM to the dynamic MAX-k coverage problem, and design an efficient $(1-1/e-\epsilon)$-approximation algorithm for it. Our lower bound leverages the recent developed distributed PCP framework.

Dynamic influence maximization
Binghui Peng Columbia University bp2601 @columbia..c.moommmooooo edu
Abstract
We initiate systematic study dynamic inffuence maximization (DIM). In the DIM problem, one maintains seed set S of at most k nodes in a dynamically involving social network, with the goal of maximizing the expected influence spread while minimizing the amortized updating cost. We consider two evolution models. In the incremental model, the social network gets enlarged over time and one only introduces new users and establishes new social links, we design an algorithm that achieves (1 -l//e--)-prooxmmatii k poly(log ² amortized running time, which matches the state-of-art offline algorithm with only poly-logarithmic overhead. In the fully dynamic model, users join in and leave, influence propagation gets strengthened or weakened in real time, we prove that under the Strong Exponential Time Hypothesis (SETH), no algorithm can achieve 2- (log -013) -approximation unless the amortized running time is n' 1-o(1) On the technical side, we exploit novel adaptive sampling approaches that reduce DIM to the dynamic MAX-k coverage problem, and design efficient (1 - 1/e - appaproximaaiion algorithm for Our lower bound leverages the recent developed distributed PCP framework.
the optimal solution and has
Introduction
Influence maximization (IM) is the algorithmic task of given social network and stochastic diffusion model, finding a seed set of at most nodes with the largest expected influence spread the network [35]. Influence maximization and its variants have been extensively studied in the 8), and has applications in viral market,
literature over past decades [35] B 29
rumor control, advertising, etc.
Social influence can be highly dynamic and the propagation tendencies between users can alter dramatically over time. For example, in Twitter network, users join in and existing users drop out real time, pop stars arise instantly for breaking news and trending topics; in a DBLP network, scientific co-authorship is built up and expands gradually over time. The classic IM algorithms make crucial assumptions on a stationary social network and they fail to capture the clastic nature of social networks. As consequence, their seeding could become outdated rapidly in constantly involving social network. To mitigate the issue, one designs a dynamic influence maximization algorithm, which maintains a feasible seed with high influence impact over time, and at the same time, saturates low average computation cost per update of the social network.
In this paper, we initiate systematic study on the dynamic influence maximization (DIM) problem Two types of evolution models are of interests to us. In an incremental mode !I] the social networks keep growing: new users join in and new social relationship built up or strengthened over time. The motivating example is the DBLP network, where co-authorship gets expanded over time. Another justification is the preferential attachment involving model of social network
In fully
'Teee terms are standard notions in the dynamic algorithm literature, e.g., see 30
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

dynamic model, the social network involves over time, users can join in and leave out, social links emerge and disappear, influence impacts get strengthened or weakened. The motivating examples are social media networks like Twitter or Facebook, and the advertising market.
There some pioneer works on the topic of dynamic influence maximization and various heuristic algorithms have been proposed in the literature [52] 44 24]. These algorithms have different kinds of approximation guarantee on the seed set, but the crucial drawback is that the amortized running time per update is no better than (2()), here n is the total number of nodes in a social network. This is extremely unsatisfactory from a theoretical view, as it indicates these algorithm do no better than re-run the state-of-at of-ar IM algorithm upon every update. Hence, the central question over the field is that, can we achieve the optimal approximation guarantee with no significant overhead on amortized running time?
Our contribution We address the above questions and provide clear resolutions. In the incremental model, we prove it is possible to maintain a seed set with (1 - 1/e - e) aapproximation ratio in amortized running time of k poly(log n, E =T),, which matches the state-of-art offline algorithm up to poly-logarithmic factors (Theorem B.I While in the fully dynamic algorithm, assuming the
Strong Exponential Time Hypothesis (SETH), we prove no algorithm can achieve 2 n)*
approximation unless the amortized running time is (11) (Theorem 4.3 and Theorem 4.4). This computational barrier draws sharp separation between these two dynamic models and delivers the following surprising message: There is no hope to achieve any meaningful approximation guarantee for DIM, even one only aims for slightly reduced running time than the naive approach of re- re-instantiating an IM algorithm upon every update.
On the technical side, our DIM algorithm in the incremental model uses novel adaptive sampling strategies and reduces the DIM problem to the dynamic MAX-k coverage problem. We provide an efficient dynamic algorithm to the later problem. Both the adaptive sampling strategy and the combinatorial algorithm could be of independent interests to the influence maximization community and the submodular maximization community. For the computaional hardness result, we exploit novel application of the recent developed distribution PCP framework for fine grained complexity.
Related work Influence maximization as a discrete optimization task is first proposed in the seminal work of Kempe al. (35), who propose the Independent Cascade (IC) model and the Linear Threshold (LT) model, prove the submodularity property and study the performance of greedy approximation algorithm. Upon then, influence maximization and its variant has been extensively studied in the literature, including scalable algorithms [21 [3 [1 50), adaptive algorithms (2] 28 45 19] 49 6). learning algorithms
[22 g 39 32]
etc. For detailed coverage over the area, we refer interested
readers to the survey of 18 40
Efficient and scalable influence maximization has been the central focus of the research. Influence maximization is known to be NP-hard to approximate within (1 - 1/e) under the Independent Cascade model (35), and APX-hard under the Linear Threshold model (48) while at the same, the
simple greedy algorithm achieves (1 1/e) approximation under both diffusion models, but with
running time ((mnk)). The breakthrough comes from Borgs et al. [[3), who propose the Reverse influence sampling (RIS) approach and their algorithm has running time O((m + -n)kee logg n). The running time has been improved to O(Im + nikee 2lo and made practical in [1 50].
There are some initial efforts on the problem of dynamic influence maximization All of them provide heuristics and none of them has rigorous theoretical guarantee on both the ap- proximation ratio and the amortized running time. Chen et al. [24
propose Upper Bound Interchange 44 design a RIS based algorithm that Inspired by recent advance on streaming submodular maximiza- tion, Wang et al. [52] give a practical efficient algorithm that maintains a constant approximated solution. However, none of the above mentioned algorithm has rigorous guarantees on the amortized running time and they can be as worse M(n). The failure on their theoretical guarantees are not accidental, as our hardness result indicates that 2(m=-9) amortized running time is essential to achieve any meaningful approximation. Meanwhile, our algorithm for incremental model sub- stantially deviates from these approaches and provides rigorous guarantee on amortized running time.
(UBI) method with 1 1/2- /2-approximation ratio. Ohsaka et al. achieves (1
2

---

Influence maximization is closely related to submodular maximization 15 5 33
10
7
[4
g
37 23 a central area of discrete optimization. Ours is especially related to the dynamic submodular maximization problem, which has been recently studied in The work of and (3 gives (1/2- >>approxximation to the fully dynamic submodular under cardinality constraints, with amortized query complexity O(k² log" 2 n e. and Olog n 2 The approximation ratio of 1/2 is known to be tight, as Chen and Peng [23] prove that any dynamic
25
27
26
16
25
43 37 23
algorithm achieves (3 + <) approximation must have amortized query complexity of at least n ((())) /k3.
The dynamic submodular maximization is studied under the query model and measured in query complexity, while we consider time complexity in dynamic influence maximization. These two are generally incomparable.
2 Preliminary
We consider the well-studied Independent Cascade (IC) model and the Linear Threshold (LT) model.
Independent Cascade model In the IC model, the social network is described by a directed influence graph G (V, E. p). where V ([V] = n) is the set of nodes and E S V V (E) m) describes the set of directed edges. There is probability Pu,e associated with each directed edge (u,v) E E. In the information diffusion process, each activated node u has one chance to activate its out-going neighbor with independent success probability Pu... The live-edge graph 7. (V, L(E)) random subgraph of G, where each edge (u, v) E E is included L(E) with an independent probability Pa,.. The diffusion process is sampled and nodes in seed set S V are activated. At every discrete time T = 1, 1, if a node was activated at time 1, then its out-going neighbors in L are activated at time The propagation continues until no more activated nodes appears at a time step.
also be seen as follow. At time
0, a live-edge graph
Linear Threshold model In the LT model, the social network is a directed graph G = (V, E, w), with V denotes the set of nodes and E denotes the of edge. There is a weight Wh., 0 associate with each edge (u,, v) E E and the weight satisfies EveNa(u) Wa,v S 1 for every node c, where (u)(v) contains all incoming neighbors of node In the information diffusion process, a threshold to sampled uniformly and independently from [0, 1] for each node v, and a node becomes active if its active in-coming neighbors have their weights exceed the threshold f.. In the LT model, the live-edge graph L = (V, L()) can be obtained as follow. Each node v samples an incoming neighbor from (v). where the node is sampled with probability Wa,v and the edge (u, v) is included in L(E). With probability 1 - Ene Nu Nu(v) Wa.v. no edge is added. The diffusion process can also be described by the live-edge graph. That is, a live-edge graph L is sampled at the beginning and the influence is spread along the graph.
Influence maximization Given a seed set S, the influence spread of S, denoted as (S)) is the expected number of nodes activated from seed set S, i.c., (SS) = EL~G|[[(S) L)], and I(S, L) the set of nodes reachable from S in graph L.. the influence maximization problem, our goal is to find seed set S of size at most & that maximizes the expected influence, i.e., finding S' E arg sax (S).
The reverse reachable set 13 has been the key concept for all near-linear time IM algorithms 13
51 50].
Definition 2.1 (Reverse Reachable Set). Under the IC model and the LT model, a reverse reachable
(RR) set with a root node v, denoted R., is the random set of nodes that node u reaches in one reverse propagation. Concretely, R. can be derived by randomly sampling a live-edge graph L = (V, and include all nodes in V that can reach y under the live-edge graph L.
Dynamics of network Social networks are subject to changes and involve over time. We consider the following dynamic model of a social network. At each time step L, one of the following four types of changes could happen. influence graph; (2) Establishment of a new relationship. It is equivalent to insert a new directed edge
(1) Introduction of a new user. This corresponds to insert a new node to
3

---

to the graph (3) Diminishing of an old relationship. It is equivalent to remove an existing edge of the graph; (4) Leave of an old user. This means remove an existing node in the influence graph.
In the incremental model, we only allow the first two types of changes. That is, we assume the social network gets enlarged over time and we only consider the introduction of new users and new relations. In the filly dynamic model, we allow all four types of changes.
The theoretical results developed in this paper also adapts to other forms of change on the social network, including (a) strengthen of influence, which means the increase of the propagation probability Pe for some edge under IC model or the increase of the weight we under LT model; (b) weaken the influence. which means the decrease of propagation probability Pe under IC model or the decrease of the weight we under LT model.
Dynamic influence maximization Let G2 = (V,, be the social network at time t. Define the expected influence to be (S) = EL~G, [S, L)]. The goal of the dynamic influence maximization problem is to maintain a seed set St of size most that maximizes the expected influence every time step t. That is to say, we aim to find S E arg maxs.gv..ss |&| (S,) for all t. The (expected) amortized running time of an algorithm defined as the (expected) average running time per update.
Dynamic MAX-K coverage The (dynamic) influence maximization problem is closely related to the (dynamic) MAX-K coverage problem. In MAX-k coverage problem, there is a collection of n sets A defined on the ground element [m.] The goal is to find & sets A....., , such that their coverage is maximized, i.c. finding arg max AI..A.... Uie(k] A.). The problem can also be formulated in terms of bipartite graph G' (Vz, VR, E), named coverage graph, where Vz. (Vr.) = 71 corresponds to set in and VR (VRl = m) corresponds to element in [m]] for any i E [m], E [mm]. there is an edge between VL,; and VR.j if and only if E A,, here VL,, is the i-th node in Vy, and VR.j is the j-th node in VR. In the dynamic MAX-k coverage problem, nodes and edges arrive leave one after another. Let V C Vz. At any time step t. we use f(S) to denote the number of neighbors of nodes in S. Our goal is to maintain a set of node Si C Vz that maximizes the coverage for every time step t. That is, finding S arg
f(()).
Submodular functions Let V be finite ground set and f: 2 + IR be a set function. Given two sets X, Y S V. the marginal gain of Y with respect to X is defined as fY) := f(X -X) f() The function f is monotone, if for any element e E V and any set X C V. it holds that fx(e) 2 0. The function í is submodular, if for any two sets X, Y satisfy X S Y S V and any element E V.Y, one has fx(e) 2 (e). The influence spread function is proved to be monotone and submodular under both the IC model and the LT model in the seminar work of (35).
3 Dynamic influence maximization on a growing social network
We study the dynamic influence maximization problem in the incremental model. Our main result is to show that it is possible to maintain an (1 - (1-1/e- -)-aprooxe solution in k poly(e -1 log n) amortized time. The amortized running time is near optimal and matches the state-of-art offline algorithm up to poly-logarithmic factors.
Theorem 3.1. In the incremental model, there is a randomized algorithm for the dynamic influence maximization under both Independent Cascade model and the Linear Threshold model. With proba- bility 1 - 5, the algorithm maintains an (1 1/e e appprooximutell optimal solution in all time steps, with amortized running time O 1og" (n/5)),
Technique overview We provide streamlined technique overview over our approach. All existing near-linear time IM algorithms [1] make use the reverse influence sampling (RIS) technique and adopt the following two-stage framework. In the first stage, the algorithm uniformly samples a few RR sets, with the guarantee that the total time steps is below some threshold. In the second stage, the algorithm solves MAX-k coverage problem on the coverage graph induced by the RR sets. Both steps are challenging to be applied in the dynamic setting and require new ideas.
'In order to adding a new directed edge (u, e). one also specifies the probability Pu,, under IC model or the weight wa,e under LT model.

---

Following the RIS framework, we first reduce the dynamic influence maximization problem to dynamic MAX-K coverage problem (see Section B.I. The first obstacle in dynamic setting is that is hard to dynamically maintain an uniform distribution over nodes, and hence, one can not uniformly sample the RR sets. We cireumvent it with a simple yet elegant idea, instead of uniformly sampling RR sets, we include and sample each node's ' RR set independently with uniformly fixed probability p. This step is easy to implement in a dynamic stream, but to make the idea work, it needs some extra technique machinery. First of all, it is not obvious how to set the sampling probability p. as if p is too large, it brings large overhead on the running time; and it is too small, the sampled coverage graph won't yield a good approximation to the influence spread function. We use simple trick. We first uniformly sample RR sets within some suitable amount of steps (the ESTIMATE procedure), and by doing so, we have accurate estimate on the sampling probability (Lemma (.3) Note that we only execute this step at beginning and it is an one-time cost. Independently sampling is friendly to dynamic algorithm, but we still need to control the total number of steps execute it. More importantly, the sampling probability should not be a fixed one throughout the dynamic stream, since the average cost to sample RR set could go up and down, and if the cost is too large, we need to decrease the sample probability. A simple rescue is to restart the above procedure once the coverage graph induced by independently sampling is too large, but this brings along two additional issues. First, the stopping time is highly correlated with the realization of RR sets, and this especially problematic for independent sampling, as each incremental update on RR sets does not follow identical distribution. Second, we certainly don't It want to restart the procedure for too many times. After all, if we need to restart upon every few updates, we gain nothing than the naive approach. We circumvent the first issue by maintaining two pieces of coverage graph Hest and Hav. Especially, we use Hest to estimate the average cost for sampling a RR set, and use Hev to approximate the influence spread function. This decouples the correlation. By Martingale concentration, we can prove that (1) Hest yields good estimation on the cost of sampling RR sets (Lemma (.55). (2) Hov gives good approximation
the influence spread function (Lemma 3.9). and at the same time, (3) conditioning on the first event, the computation cost for Hev won't be too large (Lemma 3.6 We circumvent the second issue by setting suitable threshold for constructing Hest (see Line 9 in INSERT-EDGE), and we periodically restart the algorithm each time the number of nodes or edges get doubled. The later step could lead to extra Ollog n) overhead, but it guarantees that each time the construction time of Hest goes above the threshold, the average steps for sampling a RR set increase by a factor of 2 (see Lemma 3.11. Hence, we restart the entire procedure no more than Ollo n) times.
We next give an efficient dynamic algorithm for dynamic MAX-K coverage (Section 3.2) The offline problem can be solved in linear time via greedy algorithm, but it requires several new ideas to make the dynamic variant have low amortized cost. The major issue with offline greedy algorithm that we don't t know which element has the maximum marginal contribution until we see all elements, and in the dynamic setting, we can't 't afford to wait till the end. We get around it with two adaptations. First, we divide the algorithm into O(E llog n) thread: and for each thread, make guess the optimal value (the i-th guess is (1 + e) e)- Second, instead of selecting element with the maximum margin, we maintain threshold (OPT, -f(S))) k and add any element whose marginal lies above the threshold, where S; is the current solution set maintained in the i-th thread. We prove this still gives (1 -pproxxaatiiio (Lemma 3.13). The key challenge is that once we add new element to the solution set, the threshold changes and we need to go over all existing element again. We carefully maintain dynamic data structure and prove the amortized running time for each thread is ((1) by a potential function based argument (Lemma 3.14).
3.1 Reducing DIM to dynamic MAX-K coverage
Lemma 3.2. In the incremental model, suppose there is an algorithm that maintains an a- approximate solution to the dynamic MAX-k coverage, with amortized running time Tmc. Then there is an algorithm, with probability at least 1- 6, maintains an (a - 22e -e)aapproximate solution for dynamic influence maximization and has amortized running time at most (T 2 llogg(n) (n/
The reduction is described in Algorithm 5 we provide some explanations here. From a high level, the execution of the algorithm is divided into phases. restarts whenever the number of edges or the number of nodes gets doubled from the previous phase. Since the total number of steps is at most (m + n2), there are at most (log n) phases. Within each phase, the algorithm is divided into
We remark this approach has been used for submodular maximization under various setting 5 10 37
5

---

iterations. At the beginning of each iteration, the algorithm runs the ESTIMATE procedure in order to estimate the total number of RR it needs sample. It then fixes sampling probability p and samples two graphs, Hev and Hex. dynamically. As explained before, Hest is used to measure the number of steps one takes for sampling RR sets, and Hev used approximate the influence spread function. We stop sampling Hest and Hev and start new iteration whenever the number of step for constructing Hest exceeds 16/mm-
Due to space limits, we defer detailed proof to the full version of this paper and outline a sketch below.
Algorithm 4 INSERT-NODE(U!
1: V VU (u), n 1.
2:
if' n 2 2no then
Algorithm INITIALIZE
mg < m. no f- n.
m 0, my 0, n f no t 0.
4:
BUILDGRAPIO).
2: V < 0. E + 0. Hev +- 0, Hest t 0.
else
3: + 0, p 0.
6:
VL, t VL,est U {u}
VL,ev VL,ev {u].
8: VR,est + Vn,est U {u} with prob p.
VR.ev <- Vieww U {u) with prob p.
Algorithm 2 ESTIMATE
10: end if
1: +
Algorithm 5 INSERT-EDGE(U,
2: repeat
3: Sample a RR set uniformly over V.
1: E EU {(u, U)), ) +
4: K +- K 1.
2: m 2 2mo then
5: until Rmg steps have been taken
mi < m. no f- n.
6: return K
4: BUILDGRAPITO.
else
6:
for node v' E VR, do
Algorithm 3 BUILDGRAPH
Augment the RR set Retesst to Rnew "e''stt
1: Hev (V.0.0) 0), Hest (V,0,0,
Roi t- R.
2: t- a -2 logoonn
if the total steps of building Hest
3: K + ESTIMATE().
exceed 16/mng then
4: < K
10:
mg f m, n2 t n. Restart and BUILDGRAPHO.
5: for node V do
11:
6: Sample the RR set es with prob p.
12:
end if end for
7: Sample the RR set Rv,ov with prob
13:
8: for node Ry do
14:
for node v' E Vn..vv do
9: INSERT- INSERT-EDGE-OEE (DGEE v) to Hey
15:
Augment the RR set Re to Rea
10: end for
16:
INSERT-EDGE-COVC v') Hev for all u' E Reew ,ov RRy
11: end for
17:
Rw -Rnew .cv'
18: end for
19:
end if
We first focus single iteration of the algorithm. Recall that in each iteration, the number of nodes satisfies n E [no, 2no)) and the number of edge satisfies m E [mo, 2mo)), and the number of steps for sampling Hest never exceeds 16/mg.
Bounds at initialization We prove the ESTIMATE procedure makes a good estimate on the sampling probability at the beginning of each iteration. Let AVG -mo be the expected number of steps taken of sampling a uniformly random RR set, and recall K is the number of RR sets ESTIMATE samples.
Lemma 3.3. With probability at least
28 nok the number of RR sets ESTIMATE samples satisfies
(1 e)
R < K
< (1 (1+
R
AVG
AVG
The initial steps to built Hest and Hov are within [(1 2)2 (1 + Rmo) with high probability.

---

Lemma 3.4. Conditioning on the event of Lemma 3.3 with probability at least 1 - number of initial steps for building Hest and Hest are within [[1 e)² (1 + e)
46 78 the total
Bounds on adaptive sampling We dynamically sample and augment RR sets after we initiate Hest and Hev. Consider the t-th edge to arrive, let Zr,; 2mm be the number of edges checked by INSERT-EDGE when it augments the RR set of the i-th node. Note if INSERT-NODE and BUILDGRAPE APII did not sample the i-th node and its RR set, then simply take Zr.i - O. Slightly abuse of notation, we write Zj to denote the j-th random variable in the sequence Zo...... Zo. Z1.1...., and we know { Zz1 forms a martingale. Let J be the number of steps executed by INSERT-EDGE for Hest. our next Lemma asserts that the total number of steps is around its expectation.
[[Z 2 (1 - c)8R, and J2 be the largest Lemma 3.5. Let J1 be the smallest number such that Σ
26 number that Σ B[z,] < (1 + e) With probability at least n we have J1 S JJS. J2.
With high probability, the total number of edge checked for Hev is bounded by 16(1 + Rma- Lemma 3.6. Conditioning on the event of Lemma 3.5 with probability at least 1 - S_ the total number of edges checked by INSERT-EDGE for Hev is at most 16(1 + Rmo-
Approximation guarantee We prove that the coverage function induced on Hev yields a good approximation on the influence spread function. At any time step I, let V be the set of node at time step For any node v e Vt and node set S S V/, let 2t.v.5 1 if R.vevv 0, and Ft, iff S' has non-zero intersection with the RR set of node v at time step t.
otherwise. That is, Ft,, We note that if a node was not sampled by INSERT-NODE and BUILDGRAPH, and hence does not appear in Vi..v, we set Ft,,,S 0.
Definition 3.7 (Normalized coverage function). Define fart 2 - R+ to be the normalized coverage function. Jev,((S) ()+== K Evev, Tt,w5S.
me
The normalized coverage function fev.e is an unbiased estimator on the influence spread function and it achieves good approximation with high probability.
Lemma 3.8. At any time step L and S C Vt, we have ElSeu, = =or(S), where os is the influence spread function time L.
Lemma 3.9. After initializing Hest and Hev any time step Let S S V., |S| k. Assume the condition in Lemma
3.3 holds, then we have
8
Pr (S( ((((8)))(((eeee(e) e = I
nck/6" and,
(1)
Pr (S [[Jcc,(S)) OPT,, < nk
(2)
The expectation is taken over the randomness of the construction of Hew and OPT, is defined as the maximum (expected) influence spread of a set of size k at time t.
The following Lemma indicates pointwise approximation carries over the approximation ratio.
Lemma 3.10. Let 2 and let f 2V - RR+ be an arbitrary set function. Let 'D be a distribution over functions such that for all S C V, Prg-ollf(S) - 9(S) 7 I $
पeミ. Let Sg be an
a-approximate solution for function g. i.e. g(S,) 2 maxxscv,sis g(S), then we have
8
f(S,) Sa g
Pr
max f(S) 27 < nk//2' SCV|SICK
Bounds for amortized running time We next bound the total number of iterations within each phase. The key observation is that each time the algorithm restarts, the average steps of sampling a random RR set increases least by factor of 2, with high probability.
Lemma 3.11. With probability a least //16 there are at most O(logn) iterations in a phase.
Proof Sketch of Lemma 3.2 For correctness, by Lemma 3.8 and Lemma 3.9 the normalized coverage function for (defined on Hev) guarantees (S) - (]ffv.((S)) [fo,(()) o,(S) < OPT,
7

---

Algorithm 6 INITIALIZE
Algorithm 8 LNSERT-EDDI--COV(UU v)
1: OPT, e)' 0.
1: for M do
2: if [s. (u) 2
OPT, OPT;-f(S. and |S| <
Algorithm 7 REVOKK(i)
then
1: if there exists node u such that fs, (u)
3:
-.+
OPT, -((.)) and |S| < k then
REVOKE(1).
1: S (u).
2:
5: end if
3:
REVOKE().
end for
4: end if
for every time step t. Combining with Lemma 3.10 an a-approximate solution to the dynamic MAX-k coverage problem translates to a solution set S, that satisfies f(S) 2 (ax (ax-2e) 2e) OPT,
For amortized ranning time. There are O(log n) phases, and by Lemma 3.11 there are at most Ollg n) iterations in each phase. Within each iteration, the ESTIMATE procedure and the construc- tion of Hest takes Omocke" log n) steps in total and (kk log n) per update. By Lemma 3.4 and Lemma 3.6 with high probability, the construction of Hev takes 16 + e)² Rmng steps in total and O(k log n.) steps per updates. Hence, there are O 2 log n) updates to the dynamic MAX-K coverage problem on Hev. Taking an union bound, the overall amortized running time per update is bounded by logn logg (ke log ke- log ke log n Tmc) S O(Tmcii log" n). O
3.2 Solving dynamic MAX-K coverage in near linear time
For ease of presentation, we assume an upper bound on the value of n is known and we set 7 {0, 1...., [c- log n1}. The algorithm maintains [T] threads and for the i-th thread, INSERT-EDGE- COV and REVOKE augments the solution set S; only when the marginal value of a node u exceeds the threshold, i.e. (u) 2
((S.) In particular, the threshold decreases over time and each time it decreases, REVOKE scans over all existing nodes in Vz. The algorithm returns the solution set with maximum value each time step, i.e.. return arg maxs, f(.).
k
Theorem 3.12. In the incremental model, there is an algorithm for dynamic MAX-k coverage that maintains a solution set with (1 - 1/e - e)aappooximation at every time step and the amortized running time of the algorithm is at most O log n).
The approximation guarantee and the amortized running time of Algorithm 6 8 are analysed separately. We defer detailed proof to the full version of this paper and outline a sketch below.
Lemma 3.13. The solution set is (1 - 1/e appproxmmate to the optimal one.
Proof Sketch. Let the current optimum satisfies (1 c)' OPT < (1 e)a+1 for some i I. For the i-th thread, if |Sa] < k, then one can prove f(S.) 2 (1+c)-1 OPT. On the otherside, if [|] = Let $4, be the j-th element added to the set S,, and denote S.j {s..1...., St,y.. guarantees f(S.. f(S..) & (OPT:- (S. for all j E [b:] Unravel the recursion, one has S(S.) 2 (1 Lemma 3.14. The algorithm
Our algorithm
e) OPT.
6 has amortized running time O log k).
Proof Sketch. We prove that for each thread E I, the amortized running time is O(1). Let V C VR be nodes covered by S. Let P(t) denote the number of operations performed on the i-th thread up to time t. For each edge
(u, v), let X. denote whether the edge is covered by VA i.e. X. = 1 if E Vi and X, = 0 otherwise. Similarly, for each node v E VR, let Y, denote whether node is included in V i... Y, = 1 if v V and Y. = 0 otherwise, For each node Vz, let Z, denote whether node u included in S,, i.c. Y, 1 if u E S, and Y, otherwise. Define the potential function + R+:
(t) 2|V E + Σ X + YY+2 Σ Zu.
EEE, VEVR
VEV.
8

---

We prove P(t) I (t) always holds. This suffices for our purpose as one can easily show ((t) S 5t. The claim is executed by an induction showing P(t) P( 1) S (t) + 1) holds for 0
Taking a = 1 - 1/e and Tm = O (lee--oog log n.), we wrap up the proof of Theorem 3.1
4 Fully dynamic influence maximization
In the fully dynamic model, the social network involves over time and all four types of change exhibit. Our main delivery is sharp computational hardness result. We prove that under the SETH, unless the amortized running time is n 1210(1), the approximation ratio can not even be 2 (log (logg))-o03 We first provide some background Time Hypothesis (SETH), which is a pessimistic version of P * NP that postulates that much better algorithms for k-SAT do not exist. The SETH is first proposed in the seminal work of [3 and it is widely believed in the computational complexity, see 153 for detailed survey.
fine- grain complexity. We reduce from the Strong Exponential
Conjecture 4.1 (Strong Exponential Time Hypothesis (SETH), (1). For any e > 0, there exists 2 such that k-SAT on variables can not be solved in time 0(20)))m)
Our starting point is the following SETH-based hardness of approximation result. The result is proven in [2] using the distributed PCP framework 46) for hardness of approximation results in P.
Theorem 4.2 (2
6 > 0, m n1 and 20logn)'-of n)²=-(13 Given two collections of n
sets A and B over universe [m]. Unless SETH is false, no algorithm can distinguish the following two cases in O
YES instance. There exists two sets A E A, B E B such that B C A;
NO instance. For every AE A, B B we have IAn B BB//
B
p
1/n
A
4
O
V/1
1/2
V
V
V22
1/3
V/4
(8) Hard instance IC model
(b) Hard instance for LT model
Figure The hard instance for fully dynamic influence maximization.
Theorem 4.3. Assuming SETH, in fully dynamic influence maximization problem under IC model, no algorithm can achieve 2 (log (log -o03) approximation unless the amortized running time is n 1--o(1)
2-1log
Proof Sketch. Let m (t) in Theorem 4.2] we reduce it to DIM. We assume [, 2 t for all E [n] as we can duplicate the ground element for / times. Consider the following influence graph = (V, E)p,, where the influence probability
21ogg)) o(1) ,K 1. Given an instance AA, of the problem
all edges are 1. The node set V is partitioned into V = Vi U V/2 Vs [V]| = n, [V2 m, Val m²t. Intuitively, the i-th node f1,4 of V1 corresponds to the set A, A, and the j-th node U2.j in Vi correspond the j-th element of ground set [m]. There is directed

---

edge from 01, to 02 iff the j-th element is contained in the set A1. We write nodes in V33 as (em and there is directed edge node D2,j U3.j.e. j [m]] l [mt].
Consider the following update sequence of the DIM problem. The graph G is loaded first and then followed by consecutive epochs. In the 7-th epoch, all edges between V/2 and V/3 are deleted, and for each E B,, we add back the edge between 22, and V3,j. for all { E [mt].
One can show the total number updates is at most ++((), We prove by contrary and suppose there is an algorithm for DIM that achieves 2/ tttaapprxximatin in n time. Under the above reduction, we output YES, for some epoch r E [r), the DIM algorithm outputs a solution with influence spread greater than 2m B+|- We output NO otherwise. One prove (1) if there exists A A, B, E B such that By S A, then we output YES, and, (2) A n B-1 < |Brl/t for any i, E [n], the algorithm outputx NO. Hence, we conclude under SETH, there is no 2/ 2ttaapproximation algorithm unless the amortized running time is O(n²
The lower bound can be extended the LT model, under the additional constraints that the algo- rithm only selects seeds from a prescribed set V S V. This a natural assumption that has been for the LT model. The construction is similar to Theorem 4.4 with the exception that (1) the weight on edges between V and V2 are 1 1/n and all other edges have weight (2) the node set V is partitioned into four parts V1 V2 V33 U V4. IVa = nm3 and each node in V3 is connected to nodes in V4. Detailed proof can be found in the full version of this paper.
made/discussed in previous work [20 36 48
Theorem 4.4. Assuming SETH, for the fully dynamic influence maximization problem under LT model, if the algorithm is only allowed to select seed from a prescribed set, then no algorithm can achieve 2 2 (loogn)''-ap m))-00)))))))) approximation unless the amortized running time is n o(1))
(log
5
Discussion
We study the dynamic influence maximization problem and provide sharp computational results on the incremental update model and the fully dynamic model. In the incremental model, we provide an algorithm that maintains a seed set with (1 - 1/e e -paaprooximttion and has amortized running time poly(log e n,,"),, which matches the state of art offline IM algorithm up to poly-logarithmic factor.
For the fully dynamic model, we prove that under SETH, no algorithm can achieve 2 (lug n)" -)) approximation unless the amortized running time n 1-0(), There are a few interesting questions for future investigation: (1) Further improve the amortized running time in the incremental model. In particular, is it possible to reduce the amortized running time of the dynamic MAX-K coverage procedure to O(1) (2) Investigate fully dynamic influence maximization problem under mild assumptions, e.g. what if the graph is bipartite?
10

---

Acknowledgement
Binghui Peng wishes to thank Xi Chen for useful discussions on dynamic submodular maximization, and thank Matthew Fahrbach for useful comments. Binghui Peng is supported in part by Christos Papadimitriou's s NSF grants 1CF-1766970 AF, CCF-1910700 AF and softbank grant, and by Xi Chen's NSF grants NSF CCF-1703925.
Broader Impact
Our work mainly theoretical with no foresecable ethical issues.
References
[1] Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, and Barna Saha. Dynamic set cover: improved algorithms and lower bounds. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 114-125, 2019.
[2] Amir Abboud, Aviad Rubinstein, and Ryan Williams. Distributed pep theorems for hardness of approximation in In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 25-36. IEEE, 2017.
[3] Charu C Aggarwal, Shuyang Lin, and Philip S Yu. On influential node discovery in dynamic social networks. In Proceedings of the 2012 SIAM International Conference on Data Mining, pages 636-647 647. SIAM, 2012.
[4] Noga Alon, Iftah Gamzu, and Moshe Tennenholtz. Optimizing budget allocation among channels and influencers. In Proceedings of the 21st international conference on World Wide Web, pages 381-388 2012.
[5] Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. Streaming submodular maximization: Massive data summarization the fly. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. pages 671 180, 2014.
[6] Ashwinkumar Badanidiyuru, Christos Papadimitriou, Aviad Rubinstein, Lior Seeman, and Yaron Singer. Locally adaptive optimization: Adaptive seeding for monotone submodular functions. In Proceedings of the twenty-sevnnth anmual ACM-SIAM sympostum Discrete algorithums, pages 414 429. SIAM, 2016.
[7] Eric Balkanski, Adam Breuer, and Yaron Singer. Non-monotone submodular maximization in exponentially fewer iterations. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 2370-2377, 2018
[8] Eric Balkanski, Nicole Immorlica, and Yaron Singer. The importance of communities for learning to influence. Advances in Neural Information Processing Systems, 30:5862-5871, 2017.
[9] Eric Balkanski, Aviad Rubinstein, and Yaron Singer. An exponential speedup in parallel running time for submodular maximization without loss in approximation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 283-302. SIAM, 2019.
[10] Eric Balkanski, Aviad Rubinstein, and Yaron Singer. An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model. In Proceedings of the 51st Annual ACM SIGACT Symposium Theory of Computing, pages 66-77, 2019.
[11] Eric Balkanski and Yaron Singer. The adaptive complexity of maximizing a submodular function. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1151, 2018.

---

[12] Albert-Laszil Barabási, Hawoong Jeong, Zoltan Néda, Erzsebet Ravasz, Andras Schubert, and Tamas Vicsek. Evolution of the social network of scientific collaborations. Physica A: Statistical mechanics and its applications, 31 311(3-4::900-111 2002.
[13] Christian Borgs, Michael Brautbar, Jennifer Chayes, and Brendan Lucier. Maximizing social in- fluence in nearly optimal time. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 946-957. SIAM, 2014.
[14] Adam Breuer, Eric Balkanski, and Yaron Singer. The fast algorithm for submodular maximiza- tion. In International Conference Machine Learning, pages 1134-1143, PMLR, 2020.
[15] Niv Buchbinder and Moran Feldman. Submodular functions maximization problems.. 2018.
[16] Chandra Chekuri and Kent Quanrud. Parallelizing greedy for submodular set function maxi- mization in matroids and beyond. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 78-89, 2019.
[17] Lijie Chen. On the hardness of approximate and exact (bichromatic) maximum inner product. In 33rd Computational Complexity Conference (CCC 2018). Schloss Dagstuhl-Leibniz-ZZen fuer Informatik, 2018.
[18] Wei Chen, Laks VS Lakshmanan, and Carlos Castillo. Information and influence propagation in social networks. Synthesis Lectures on Data Management, 5(4):1-177, 2013.
[19] Wei Chen and Binghui Peng. On adaptivity gaps of influence maximization under the in- dependent cascade model with full-adoption feedback. In 30th International Symposium on Algorithms and Computation 2019). Schloss Dugstuhl-LLeibniz-Zznn fuer Informatik, 2019.
[20] Wei Chen, Binghui Peng, Grant Schoenebeck, and Biaoshuai Tao. Adaptive greedy versus non-adaptive greedy for influence maximization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 590-597, 2020.
[21] Wei Chen, Yajun Wang, and Siyu Yang. Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 199-208, 2009.
[22] Wei Chen, Yajun Wang. Yang Yuan, and Qinshi Wang. Combinatorial multi-armed bandit and its extension to probabilistically triggered arms. The Journal of Machine Learning Research, 17(1):1446-177,, 2016.
[23] Xi Chen and Binghui Peng. On the complexity of dynamic submodular maximization. arXiv preprint arXiv:2 1oXiv:2//1.03/// 2021.
[24] Xiaodong Chen, Guojie Song, Xinran He, and Kunqing Xie. On influential nodes tracking in dynamic social networks. In Proceedings of the 2015 SIAM International Conference Data Mining, pages 613-621. SIAM, 2015.
[25] Alina Ene and Huy I. Nguyen. Submodular maximization with nearly-optimal approximation and adaptivity in nearly-lines time. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium Discrete Algorithms, pages 274-282. SIAM, 2019.
[26] Matthew Fahrbach, Vahab Mirrokni, and Morteza Zadimoghaddam. Non-monotone submodular maximization with nearly optimal adaptivity and query complexity. In International Conference on Machine Learning, pages 1833-1842. PMLR, 2019.
[27] Matthew Fahrbach, Vahab Mirrokni, and Morteza Zadimoghaddam. Submodular maximization with nearly optimal approximation, adaptivity and query complexity. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 255-273. SIAM, 2019.
[28] Kaito Fujii and Shinsaku Sakaue. Beyond adaptive submodularity: Approximation guarantees of greedy policy with adaptive submodularity ratio. In International Conference on Machine Learning, pages 2042-2051. PMLR, 2019.
12

---

[29] Daniel Golovin and Andreas Krause. Adaptive submodularity: Theory and upplications in active learning and stochastic optimization. Journal of Artificial Intelligence Research, 42:427-486. 2011.
[30] Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Dynamic approximate all-pairs shortest paths: Breaking the o(mn) barrier and derandomization. SIAM Journal on Computing, 4543)9947- 2016.
[31] Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. Journal of Computer and System Sciences, 62(2):367-375, 2001.
[32] Dimitris Kalimeris, Gal Kaplun, and Yaron Singer. Robust influence maximization for hy- perparametric models. In International Conference on Machine Learning, pages 3192-3200. PMLR, 2019.
[33] Ehsan Kazemi, Marko Mitrovic, Morteza Zadimoghaddam, Silvio Lattanzi, and Amin Karbasi. Submodular streaming in all its glory: Tight approximation, minimum memory and low adaptive complexity. International Conference on Machine Learning, pages 3311-3320. PMLR, 2019.
[34] Ehsan Kazemi, Morteza Zadimoghaddam, and Amin Karbasi. Scalable deletion-robust submod- ular maximization: Data summarization with privacy and fairness constraints. In International conference machine learning, pages 2544-2553. PMLR, 2018.
[35] David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137-146, 2003.
[36] Sanjeev Khanna and Brendan Lucier. Influence maximization in undirected networks. In Proceedings of the Twenty-fifit Annual ACM-SIAM Symposium on Discrete Algorithmss pages 1482-1496. SIAM, 2014.
[37] Silvio Lattanzi, Slobodan Mitrović, Ashkan NorouziFard, Jakub Tarnawski, and Morteza Zadimoghaddam. Fully dynamic algorithm for constrained submodular optimization. Advances in Neural Information Processing Systems, 2020.
[38] Jure Leskovee, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 420-429, 2007.
[39] Shuai Li, Fang Kong, Kejie Tang, Qizhi Li, and Wei Chen. Online influence maximization under linear threshold model. Advances in Neural Information Processing Systems, 33, 2020.
[40] Yuchen Li, Fan, Yanhao Wang, and Kian-Lee Tan. Influence maximization on social graphs: A survey. IEEE Transactions Knowledge and Data Engineering. 30(10): (112)):8521182. 2018.
[41] David Liben-Nowell and Jon Kleinberg. The link-prediction problem for social networks. Journal of the American society for information science and technology, 58(7)1001-1131, 2007.
[42] Xiaodong Liu, Xiangke Liao, Shanshan Li, Si Zheng, Bin Lin, Jingying Zhang, Lisong Shao, Chenlin Huang, and Liquan Xiao. On the shoulders giants: incremental influence maximiza- tion in evolving social networks. Complexity, 2017, 2017.
[43] Morteza Monemizadeh. Dynamic submodular maximization. Advances Neural Information Processing Systems, 33, 2020.
[44] Naoto Ohsaka, Takuya Akiba, Yuichi Yoshida, and Ken-ichi Kawarahayashi. Dynamic influence analysis in evolving networks. Proceedings of the VLDB Endowment, 112) 2016.
[45] Binghui Peng and Wei Chen. adaptive influence maximization with myopic feedback. Advances in Neural Information Processing Systems 32 pre-proceedings (NeurIPS 2019), 2019.
13

---

[46] Aviad Rubinstein. Hardness of approximate nearest neighbor search. In Proceedings of the 50th
Annual ACM SIGACT Symposium on Theory of Computing, pages 1260-1268, 1268, 2018.
[47] Aviad Rubinstein and Virginia Vassilevska Williams. Seth vs approximation. ACM SIGACT News, 50(4):57-76, 2019.
[48] Grant Schoenebeck and Biaoshuai Tao. Influence maximization undirected graphs: Toward closing the (1-1/e) gap. ACM Transactions on Economics and Computation (TEAC), 8(4):1-36, 2020.
[49] Lior Seeman and Yaron Singer. Adaptive seeding social networks. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 459-468, IEEE, 2013.
[50] Youze Tang, Yanchen Shi, and Xiaokui Xiao. Influence maximization in near-linear time: A martingale approach. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pages 1539-1554. 2015.
[51] Youze Tang, Xiaokui Xiao, and Yanchen Shi. Influence maximization: Near-optimal time complexity meets practical efficiency. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data, pages 75-86, 2014.
[52] Yanhao Wang, Qi Fan, and Yuchen Li. Tan, kian-lee. real-time influence maximization dynamic social streams.(2077) In Proceedings of the VLDB Endowment: 43rd International Conference on Very Large Data Bases, Munich, Germany, 2017 August 28-September, volume 1, pages 805-816, 2017.
[53] Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the ICM, volume 3, pages 3431-3472 World Scientific, 2018.
14


Reviews:
[{"review_id": "zAT_iT8KhZ", "reviewer": "Reviewer_fcLb", "summary": "This paper studies influence maximization (IM) in a dynamically evolving social network, where at each time step, one node/edge may emerge or disappear. The authors consider two evolution models: the incremental model (only node/edge insertion is allowed; e.g., the DBLP network) and the full model (both insertion and deletion are allowed; e.g., the Twitter network). \n\nUnder the incremental model, a $(1-1/e-\\epsilon)$-approximation algorithm is proposed with $k\\cdot \\textrm{poly}(\\log n, \\epsilon^{-1})$ amortized running time. This is an algorithmic breakthrough because previous dynamic IM algorithms [44, 36, 20] all need $\\Omega(n)$ amortized running time in the worst cases.\n\nUnder the full model, it is proved that no algorithm can achieve a meaningful approximation ratio within $O(n^{1-o(1)})$ amortized running time under the Strong Exponential Time Hypothesis.\n\nBoth theoretical results are proved under the classical IC and LT models.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The theoretical results in this paper are novel from my perspective. The used techniques are also different from previous dynamic IM studies and dynamic submodular optimization studies. I did not check the proof correctness in the supplementary material, but the logic and intuition explained in the main paper seem to be smooth.\n\nA few questions and concerns:\n- You claim that several previous studies on dynamic IM [44, 36, 20] need $\\Omega(n)$ amortized running time in the worst cases. Could you summarize their accurate running time in a table? Also, do they bear the same setting as yours? Do they allow node/edge deletion?\n\n- The theoretical results in this paper are novel and inspiring, but I still feel empirical evaluation is needed. Unlike the general submodular optimization problem, IM is a practical task. Under the incremental model, I would suggest comparing the empirical running time and spread of the proposed model and previous studies [44, 36, 20] if they are applicable in this setting.\n\n- In Lines 89-95, you mention the difference between your results and recent studies on dynamic submodular maximization. Specifically, their results are measured in query complexity. I feel this difference is not essential because one can multiply their complexity by the complexity of computing each query (i.e., the complexity of computing the spread given the seed set; can be accelerated using RR sets) when applying their approach to dynamic IM. Maybe the more essential difference is that in dynamic IM, $\\sigma(\\cdot)$ is changing when nodes/edges are inserted and deleted?\n\n- There are many typos in the paper. I would suggest the authors carefully check their writings again. To give some examples,\nLine 49: maintains -> maintain. Line 64: seminar -> seminal. Line 147: that is say -> that is to say.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please see the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "lYG0EGz7BI3", "reviewer": "Reviewer_isgZ", "summary": "The paper presents new algorithms and hardness results for dynamic influence maximization, where dynamics come from one of two models: (1) the incremental model, which consider only the addition of new nodes and edges in a graph, and (2) the fully dynamic model, where nodes and edges can also be removed. Previous work has considered only heuristics that satisfy certain approximation guarantees but do not come with good amortized cost for updating the see set in the dynamic case. This paper provides a (1-1/e-eps) approximation for the optimal solution with k*poly(log n, 1/eps) approximation for the incremental model. For the fully dynamic model, the paper presents a hardness of approximation result if the Strong Exponential Time Hypothesis is true.\n\nThe proof for the approximation algorithm for the incremental model is based on two major pieces. First, the paper provides a reduction from dynamic influence maximization to dynamic MAX-k coverage. Then, a new algorithm for dynamic Max-k coverage is given. This follows a previous strategy for the static version of the problem, though a significant amount of theoretical work is required to extend both parts to the dynamic case.\n\nThe work is primarily theoretical and no implementations or experimental results are given.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the contributions of the paper substantially extend previous work on influence maximization in static graphs, and the paper involves a significant theoretical effort. However, the theoretical details are quite hard to parse in many places and it's hard to tell what the algorithm is actually doing and hard to verify its correctness. This is no doubt at least partially due to my own unfamiliarity with some of the related work, as well as to the inherent complexity of making key techniques for influence maximization work in a dynamic setting. Nevertheless, even in the technical overview there are a number of statements that seem overly confusing, as well as a number of technical terms and ideas that are used without proper definition or explanation. I list several examples below, in the hopes that a re-write might make this more accessible to a wider audience.\n\n* The word \"steps\" is being used to mean many different things in explanations on page 4 and following. First, the graph is dynamically changing at different time *steps* t. But then in the technique overview (starting line 175), I believe \"steps\" also starts to be used in reference to steps taken by a random instantiation of the process for finding a reverse reachable set (though I'm not sure what a step is here!). Then \"steps\" is used to refer to the two stages of the algorithm (line 180). I'd recommend the authors take some time to re-write the technical overview and try to distinguish more carefully between steps/stages, and concretely what a step means in each setting. This may seem minor, but without clarification and some more technical precision, it's not clear to me what is going on even in the overview, let alone the pages following it.\n* The idea of a reverse reachable set is clear in the static setting (Definition 2.1), but it's not clear to me what a Reverse Reaching Set should mean in the dynamic setting or what it might mean to sample a reverse reachable set when nodes and edges are changing. These concepts are used repeatedly, but there is no concrete explanation of what this means. A more precise explanation might help here too.\n* Related to both of the above points, when we get to Algorithm 2,  what notion of \"steps\" is being used here and what does it means to sample an RR set?\n* The definition of dynamic influence maximization at the top of page 4 to me is clear. However, this relies on some notion of a time step t, but we don't see any reference to any time step t throughout the technical overview. It's unclear what steps are happening at different t values. For example, how does this factor into what it means to sample an RR set? Does sampling an RR set somehow happen across time steps t? (I'm not sure how it could, but I can't tell!). Does sampling RR sets happen at each time step? If so, how does that work?\n\nOverall, I'd recommend a re-write of at least the technical overview on page 4 and 5, with some added technical precision. The main results seem strong and the very high level overview of the approach makes sense (i.e., reduction from DIM to dynamic MAX-k coverage + new algorithm for dynamic MAX-k coverage), but beyond this I'm unable to parse what is actually going on in the technical details. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "GFKqHye3jK", "reviewer": "Reviewer_YAX6", "summary": "The paper provides a theoretical study on the dynamic influence maximization problem, that is finding the top k seed nodes in a social network that has the largest influence spread while the social network is changing (nodes and edges could be added or deleted over time). The paper considers two dynamic models: the incremental model where only node and edge additions are allowed, and fully dynamic model, where both additions and deletions are allowed. For the incremental model, the paper provides an algorithm that guarantees finding an approximately optimal seed set solution for all networks during the network evolution, while the amortized update cost is much smaller than the re-computation cost at every time step. For the fully dynamic model, the authors provide a strong negative result, showing that under a commonly adopted complexity assumption SETH, the fully dynamic influence maximization problem cannot be solved, more specifically, to achieve even slightly better than a nontrivial 1/n approximation ratio, one need almost linear amortized running time.\n\nThe contribution of the paper is on the systematic study on dynamic influence maximization. From the theory side, it is much better than existing studies on dynamic influence maximization, which is mostly heuristic based and does not provide speedup in amortized running time.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The strength of the paper is its theoretical contribution to the dynamic influence maximization problem. This is the first study I see that provide strong theoretical results on two important dynamic models. On the incremental model, it provides the first theoretical algorithm that has significant speedup in terms of the amortized running time, where the existing studies usually do not provide any theoretical results and any speedup in amortized running time. To achieve this theoretical result, the proposed algorithm is nontrivial, and it combines several techniques to address several issues that arises due to the dynamic changes in the network. For the fully dynamic model, it provides a strong inapproximation result, which is the first such hardness result and also provides inside into the hardness of this setting.\n\nIn general, the paper has good original results, built upon recent research on dynamic submodular maximization and certain hardness results. It would be very useful for the community to understand these theoretical results, and since dynamic setting is very realistic, this could be important for practical considerations too. The paper also tries to explain the algorithm and proof ideas in a clean way, and in general the paper is well structured.\n\nThe weakness of the paper is that the key algorithm explanations have several unclear points and typos, making it hard to fully understand the algorithm and its novelty. I will list these issues below in the detailed comment section. I believe most of these issues can be addressed in the next revision, and I am looking forward to the authors' feedback to answer these issues and clean up the presentation. I did not check the details of the analysis, but has reasonable confidence that the martingale based analysis is mainly correct.\n\n\nDetailed comments on the presentation issues:\n\n- Line 12. For the hardness result, the approximation ratio uses the expression that is greater than 1, while for the algorithm, it uses the approximation ratio of 1-1/e, which is less than 1. This should be made consistent.\n\n- Line 99. It uses V and E to denote the set of nodes and edges, and their size to be n and m. Since the network is dynamic, the authors should clearly state what V, E, n and m means. I believe it means the largest possible set of nodes and edges and their values. Please clarify. Also, later V is also used as the instant node set, and that could be confusing. I suggest that the authors always use $V_t$ to represent the current node set at some time t. \n\n- Line 169-170. It says the amortized running time matches the state-of-the-art offline algorithm up to poly-logarithmic factors. This statement is unclear to me. If we totally have T updates, the total running time of their dynamic algorithm should be much faster than re-run the offline algorithm at each update. The state-of-the-art offline algorithm for each update is in time $O(k(n+m) \\log n/\\epsilon^2)$. So what does it mean by matching the algorithm? I just realized the authors perhaps mean by growing a graph from an empty graph in n+m steps, their algorithm would achieve almost the same running time. Please explain this in a better way to convey the idea that their algorithm is much faster than re-run the offline algorithm at each update.\n\n- Line 220. $OPT_i$ is not explained in the context, should directly say it is $(1+\\epsilon)^i$.\n\n- Section 3.1. The explanation of the algorithm in the text as well as the algorithm pseudocode should be improved. There are number of points that are unclear to me in the first reading. The following is a list of such issues.\n\n- Line 240. Variable $R$ and $m_0$ are not explained in the context. One has to read the pseudocode to get some idea.\n\n- Algorithm 1, line 2, notation V and E is better changed to dynamic notations, such as V_t or E_t, to avoid confusing with the largest node and edge set notation. For example, in line 3 of Algorithm 2, when it says uniformly over V, I initially thought it is uniformly over the largest node set, but I guess it means uniform over the current node set V.\n\n- Algorithm 2, line 5, \"step\" is a technical term that is not explained precisely. What is exactly a step? Moreover, in earlier description (see line 131), it refers to one time step t as the step for adding a node or edge (or delete a node or edge). I believe these two steps are different, but the authors do not provide clarification. I suggest that for network change, we may call it round, and in each round, there is one network change. The time step is reserved for computational steps within a round. Please specify what one step really means. Is it that randomly selecting one reverse edge in the RR set generation process one step?\n\n- Algorithm 3, line 2. Constant c is not explained. What is its purpose?\n\n- Algorithm 3, line 4. This is to set a probability p. What if $K > n_0$ and the $p$ is not a probability? I never see an explanation here. Actually, I believe this is a very important point. If $p < 1$ and it is indeed a probability, then line 5-11 only samples one RR set for each node $v$. Is it enough? In the RIS approach for the classical IM problem, it is possible that on average each node $v$ would have many RR set samples, otherwise, the estimation may not be accurate. Therefore, I feel that there is some gap here. Is it possible that $K > n_0$ and this suggests that each node $v$ should have multiple RR set samples? \n\n- Algorithm 3, line 9, INSERT-EDGE-COV(u,v), this routine is not explained in Section 3.1 and only explained in Section 3.2, but it is important to understand this routine in order to understand Algorithm 1-5. \n\n- Algorithm 4, line 6. Notation $V_{L,est}$ is not explained, so do the notations in the next three lines. I have to guess that it means the left-side nodes in the bipartite graph H_{est}. Please clarify. Moreover, the left-side of H_{est} should be the nodes while the right-side of H_{est} should be RR sets, so technically, for line 8 and 9, it should be RR sets $\\{u\\}$ with a single node, not the single node $u$ itself.\n\n- Algorithm 5, line 7 and line 15. There is no explanation of what these augmentation operations do. Please clarify. This is actually the important incremental step of the model. Is it just simply revisiting all the RR sets to consider adding the edge $(u,v)$? How to control the time complexity? This time complexity is also related to the time step estimation in line 9. \n\n- Algorithm 5, line 15 and 16. Why the subscript est appears in the notations? Is it a typo, and should it be cv? Also, for all $v$ \\in R^{new}_{v,cv} \\setminus R_{v,cv} looks strange to me, since $v$ appears both on the left and as the subscripts in the right-hand side.\n\n- Line 306. It is strange to return a value. I think it should return argmax among $S_i$, where $i \\in I$.\n\n- Algorithm 6 to 8. Function $f$ is used in these algorithms. What is exactly the $f$? Should it be $f_{cv}$ derived from the coverage graph $\\mathcal{H}_{cv}$?\n\n- Line 490. \"Xi Chen\" should be \"Wei Chen\"\n\nOverall, the above listed issues are mostly presentation issues. If the authors can satisfactorily address all these issues in the rebuttal, my rating on the paper could be further increased.\n\nThere are also a few other studies on dynamic influence maximization. Although they are not directly related to the theoretical study of the current paper, they are early studies in this area that should be cited:\n\n- Aggarwal C, Lin S, and Yu P S. On influential node discovery in dynamic social networks. In Proceedings of SIAM International Conference on Data Mining (SDM), Anaheim, USA, Apr 2012\n\n- Liu X, Liao X, Li S, Zhang J, Shao L, Huang C, and Xiao L. On the shoulders of giants: incremental influence maximization in evolving social networks. Complexity 2017\n\n============ Post rebuttal comments ==================\n\nThe authors feedback has addressed my comments and concerns, which are mostly on the presentation and clarity of the paper. In particular, the treatment of p in Algorithm 3 is clear now --- it is not just a probability, and could allow multiple samples. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The work is purely theoretical, and no perceived negative societal impact exists.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "CyZbyYhwH1y", "reviewer": "Reviewer_tdZf", "summary": "The authors propose an efficient algorithm for dynamic influence maximization in the incremental setting where only nodes and edges in the graph can be added over time.  For the fully dynamic setting where the nodes and edges can be deleted as well, they give a hardness result.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written and easy to follow.  Even as the results for the incremental version are interesting, the incremental setting does not accurately represent a social network.   The result of Wang et. al, 2017 gives a \\eps (1 - \\beta)/2 approximation by keeping O(log N/\\beta) sampled nodes  in a sliding window of size N.  Even as the use of a sliding window in their paper suffers from the same drawback of supporting only additions to the network, they do present an algorithm that looks similar to the algorithm for the dynamic max-k coverage  in this paper.  A clearer comparison with the earlier work will help position this work.\n\nRead the authors' feedback and updating my score slightly higher.  My concerns about the incremental setting still remain.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose a new efficient algorithm for influence maximization in the incremental setting.  The theoretical contribution is interesting and novel and the problem is interesting and well-studied. The main limitation of the current write-up is its writing but that should be addressed by implementing the reviewers’ suggestions. Overall, the paper is a nice contribution and I suggest to accept it.
Decision: Accept (Poster)