# dynamic_influence_maximization__ae7b7334.pdf

Dynamic inﬂuence maximization

Binghui Peng Columbia University bp2601@columbia.edu

We initiate a systematic study on dynamic inﬂuence 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 inﬂuence 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 1/e ϵ)-approximation to the optimal solution and has k poly(log n, ϵ 1) amortized running time, which matches the state-of-art ofﬂine algorithm with only poly-logarithmic overhead. In the fully dynamic model, users join in and leave, inﬂuence 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 n1 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 efﬁcient (1 1/e ϵ)-approximation algorithm for it. Our lower bound leverages the recent developed distributed PCP framework.

1 Introduction

Inﬂuence maximization (IM) is the algorithmic task of given a social network and a stochastic diffusion model, ﬁnding a seed set of at most k nodes with the largest expected inﬂuence spread over the network [35]. Inﬂuence maximization and its variants have been extensively studied in the literature over past decades [35, 13, 29, 45, 49, 38, 4, 22, 8], and it has applications in viral market, rumor control, advertising, etc.

Social inﬂuence can be highly dynamic and the propagation tendencies between users can alter dramatically over time. For example, in a Twitter network, new users join in and existing users drop out in real time, pop stars arise instantly for breaking news and trending topics; in a DBLP network, scientiﬁc 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 elastic nature of social networks. As a consequence, their seeding set could become outdated rapidly in a constantly involving social network. To mitigate the issue, one designs a dynamic inﬂuence maximization algorithm, which maintains a feasible seed set with high inﬂuence impact over time, and at the same time, saturates low average computation cost per update of the social network.

In this paper, we initiate a systematic study on the dynamic inﬂuence maximization (DIM) problem . Two types of evolution models are of interests to us. In an incremental model1, the social networks keep growing: new users join in and new social relationship is built up or strengthened over time. The motivating example is the DBLP network, where co-authorship gets expanded over time. Another justiﬁcation is the preferential attachment involving model of social network [12, 41]. In a fully

1These terms are standard notions in the dynamic algorithm literature, e.g., see [30, 1]

35th Conference on Neural Information Processing Systems (Neur IPS 2021).

dynamic model, the social network involves over time, users can join in and leave out, social links emerge and disappear, inﬂuence impacts get strengthened or weakened. The motivating examples are social media networks like Twitter or Facebook, and the advertising market.

There are some pioneer works on the topic of dynamic inﬂuence 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 Ω(n), 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-art IM algorithm upon every update. Hence, the central question over the ﬁeld is that, can we achieve the optimal approximation guarantee with no signiﬁcant 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 ϵ)-approximation ratio in amortized running time of k poly(log n, ϵ 1), which matches the state-of-art ofﬂine algorithm up to poly-logarithmic factors (Theorem 3.1). While in the fully dynamic algorithm, assuming the Strong Exponential Time Hypothesis (SETH), we prove no algorithm can achieve 2 (log n)1 o(1)

approximation unless the amortized running time is n1 o(1) (Theorem 4.3 and Theorem 4.4). This computational barrier draws a 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 a slightly reduced running time than the naive approach of 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 efﬁcient dynamic algorithm to the later problem. Both the adaptive sampling strategy and the combinatorial algorithm could be of independent interests to the inﬂuence maximization community and the submodular maximization community. For the computaional hardness result, we exploit a novel application of the recent developed distribution PCP framework for ﬁne grained complexity.

Related work Inﬂuence maximization as a discrete optimization task is ﬁrst proposed in the seminal work of Kempe et 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, inﬂuence maximization and its variant has been extensively studied in the literature, including scalable algorithms [21, 13, 51, 50], adaptive algorithms [29, 28, 45, 19, 49, 6], learning algorithms [22, 8, 39, 32], etc. For detailed coverage over the area, we refer interested readers to the survey of [18, 40].

Efﬁcient and scalable inﬂuence maximization has been the central focus of the research. Inﬂuence 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. [13], who propose the Reverse inﬂuence sampling (RIS) approach and their algorithm has running time O((m + n)kϵ 3 log2 n). The running time has been improved to O((m + n)kϵ 2 log n) and made practical in [51, 50].

There are some initial efforts on the problem of dynamic inﬂuence maximization [52, 44, 24, 3, 42]. All of them provide heuristics and none of them has rigorous theoretical guarantee on both the approximation ratio and the amortized running time. Chen et al. [24] propose Upper Bound Interchange (UBI) method with 1/2-approximation ratio. Ohsaka et al. [44] design a RIS based algorithm that achieves (1 1/e)-approximation. Inspired by recent advance on streaming submodular maximization, Wang et al. [52] give a practical efﬁcient 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 as Ω(n). The failure on their theoretical guarantees are not accidental, as our hardness result indicates that Ω(n1 ϵ) amortized running time is essential to achieve any meaningful approximation. Meanwhile, our algorithm for incremental model substantially deviates from these approaches and provides rigorous guarantee on amortized running time.

Inﬂuence maximization is closely related to submodular maximization [15, 5, 33, 11, 10, 7, 14, 9, 25, 27, 26, 16, 25, 34, 43, 37, 23], a central area of discrete optimization. Ours is especially related to the dynamic submodular maximization problem, which has been recently studied in [43, 37, 23]. The work of [43] and [37] gives (1/2 ϵ)-approximation to the fully dynamic submodular under cardinality constraints, with amortized query complexity O(k2 log2 n ϵ 3) and O(log8 n ϵ 6). The approximation ratio of 1/2 is known to be tight, as Chen and Peng [23] prove that any dynamic algorithm achieves 1

2 + ϵ approximation must have amortized query complexity of at least neΩ(ϵ)/k3. The dynamic submodular maximization is studied under the query model and measured in query complexity, while we consider time complexity in dynamic inﬂuence 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 inﬂuence graph G = (V, E, p), where V (|V | = n) is the set of nodes and E V V (|E| = m) describes the set of directed edges. There is a probability pu,v associated with each directed edge (u, v) E. In the information diffusion process, each activated node u has one chance to activate its out-going neighbor v, with independent success probability pu,v. The live-edge graph L = (V, L(E)) is a random subgraph of G, where each edge (u, v) E is included in L(E) with an independent probability pu,v. The diffusion process can also be seen as follow. At time τ = 0, a live-edge graph L is sampled and nodes in seed set S V are activated. At every discrete time τ = 1, 2, . . ., if a node u 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.

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 set of edge. There is a weight wu,v > 0 associate with each edge (u, v) E and the weight satisﬁes P

u Nin(v) wu,v 1 for every node v, where Nin(v) contains all incoming neighbors of node v. In the information diffusion process, a threshold tv is sampled uniformly and independently from [0, 1] for each node v, and a node v becomes active if its active in-coming neighbors have their weights exceed the threshold tv. In the LT model, the live-edge graph L = (V, L(E)) can be obtained as follow. Each node v samples an incoming neighbor from Nin(v), where the node u is sampled with probability wu,v and the edge (u, v) is included in L(E). With probability 1 P

u Nin(v) wu,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 inﬂuence is spread along the graph.

Inﬂuence maximization Given a seed set S, the inﬂuence spread of S, denoted as σ(S), is the expected number of nodes activated from seed set S, i.e., σ(S) = EL G[|Γ(S, L)|], and Γ(S, L) is the set of nodes reachable from S in graph L. In the inﬂuence maximization problem, our goal is to ﬁnd a seed set S of size at most k that maximizes the expected inﬂuence, i.e., ﬁnding S arg max S V,|S| k σ(S).

The reverse reachable set [13] has been the key concept for all near-linear time IM algorithms [13, 51, 50].

Deﬁnition 2.1 (Reverse Reachable Set). Under the IC model and the LT model, a reverse reachable (RR) set with a root node v, denoted Rv, is the random set of nodes that node v reaches in one reverse propagation. Concretely, Rv can be derived by randomly sampling a live-edge graph L = (V, L(E)) and include all nodes in V that can reach v 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 t, one of the following four types of changes could happen. (1) Introduction of a new user. This corresponds to insert a new node to inﬂuence graph; (2) Establishment of a new relationship. It is equivalent to insert a new directed edge

to the graph2; (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 to remove an existing node in the inﬂuence graph.

In the incremental model, we only allow the ﬁrst 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 fully 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 inﬂuence, 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 inﬂuence. which means the decrease of propagation probability pe under IC model or the decrease of the weight we under LT model.

Dynamic inﬂuence maximization Let Gt = (Vt, St) be the social network at time t. Deﬁne the expected inﬂuence to be σt(S) = EL Gt[|Γ(S, L)|]. The goal of the dynamic inﬂuence maximization problem is to maintain a seed set St of size at most k that maximizes the expected inﬂuence at every time step t. That is to say, we aim to ﬁnd S t arg max St Vt,|St| k σ(St) for all t. The (expected) amortized running time of an algorithm is deﬁned as the (expected) average running time per update.

Dynamic MAX-k coverage The (dynamic) inﬂuence maximization problem is closely related to the (dynamic) MAX-k coverage problem. In a MAX-k coverage problem, there is a collection of n sets A deﬁned on the ground element [m]. The goal is to ﬁnd k sets A1, , Ak such that their coverage is maximized, i.e. ﬁnding arg max A1,...,Ak A | i [k] Ai|. The problem can also be formulated in terms of a bipartite graph G = (VL, VR, E), named coverage graph, where VL (|VL| = n) corresponds to set in A and VR (|VR| = m) corresponds to element in [m], for any i [n], j [m], there is an edge between VL,i and VR,j if and only if j Ai, here VL,i is the i-th node in VL and VR,j is the j-th node in VR. In the dynamic MAX-k coverage problem, nodes and edges arrive or leave one after another. Let V VL. At any time step t, we use ft(S) to denote the number of neighbors of nodes in S. Our goal is to maintain a set of node S t VL that maximizes the coverage for every time step t. That is, ﬁnding S t = arg max St VL,|St| k ft(St).

Submodular functions Let V be a ﬁnite ground set and f : 2V R be a set function. Given two sets X, Y V , the marginal gain of Y with respect to X is deﬁned as f X(Y ) := f(X Y ) f(X) The function f is monotone, if for any element e V and any set X V , it holds that f X(e) 0. The function f is submodular, if for any two sets X, Y satisfy X Y V and any element e V \Y , one has f X(e) f Y (e). The inﬂuence 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 inﬂuence maximization on a growing social network

We study the dynamic inﬂuence maximization problem in the incremental model. Our main result is to show that it is possible to maintain an (1 1/e ϵ)-approximate solution in k poly(ϵ 1, log n) amortized time. The amortized running time is near optimal and matches the state-of-art ofﬂine algorithm up to poly-logarithmic factors.

Theorem 3.1. In the incremental model, there is a randomized algorithm for the dynamic inﬂuence maximization under both Independent Cascade model and the Linear Threshold model. With probability 1 δ, the algorithm maintains an (1 1/e ϵ)-approximately optimal solution in all time steps, with amortized running time O(kϵ 3 log4(n/δ)).

Technique overview We provide a streamlined technique overview over our approach. All existing near-linear time IM algorithms [13, 51, 50] make use of the reverse inﬂuence sampling (RIS) technique and adopt the following two-stage framework. In the ﬁrst 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 a 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.

2In order to adding a new directed edge (u, v), one also speciﬁes the probability pu,v under IC model or the weight wu,v under LT model.

Following the RIS framework, we ﬁrst reduce the dynamic inﬂuence maximization problem to a dynamic MAX-k coverage problem (see Section 3.1). The ﬁrst obstacle in dynamic setting is that it is hard to dynamically maintain an uniform distribution over nodes, and hence, one can not uniformly sample the RR sets. We circumvent it with a simple yet elegant idea, instead of uniformly sampling RR sets, we include and sample each node s RR set independently with a uniformly ﬁxed 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 if it is too small, the sampled coverage graph won t yield a good approximation to the inﬂuence spread function. We use a simple trick. We ﬁrst uniformly sample RR sets within some suitable amount of steps (the ESTIMATE procedure), and by doing so, we have an accurate estimate on the sampling probability (Lemma 3.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 to execute it. More importantly, the sampling probability should not be a ﬁxed one throughout the dynamic stream, since the average cost to sample a 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 is especially problematic for independent sampling, as each incremental update on RR sets does not follow identical distribution. Second, we certainly don t 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 ﬁrst issue by maintaining two pieces of coverage graph Hest and Hcv. Especially, we use Hest to estimate the average cost for sampling a RR set, and use Hcv to approximate the inﬂuence 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 3.5), (2) Hcv gives good approximation on the inﬂuence spread function (Lemma 3.9), and at the same time, (3) conditioning on the ﬁrst event, the computation cost for Hcv 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 an extra O(log 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 O(log n) times.

We next give an efﬁcient dynamic algorithm for dynamic MAX-k coverage (Section 3.2). The ofﬂine 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 ofﬂine greedy algorithm is that we don t know which element has the maximum marginal contribution until we see all elements, and in the dynamic setting, we can t afford to wait till the end. We get around it with two adaptations. First, we divide the algorithm into O(ϵ 1 log n) threads3 and for each thread, we make a guess on the optimal value (the i-th guess is (1 + ϵ)i 1). Second, instead of selecting element with the maximum margin, we maintain a threshold (OPTi f(Si))/k and add any element whose marginal lies above the threshold, where Si is the current solution set maintained in the i-th thread. We prove this still gives (1 1/e)-approximation (Lemma 3.13). The key challenge is that once we add a new element to the solution set, the threshold changes and we need to go over all existing element again. We carefully maintain a dynamic data structure and prove the amortized running time for each thread is O(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 αapproximate solution to the dynamic MAX-k coverage, with amortized running time of Tmc. Then there is an algorithm, with probability at least 1 δ, maintains an (α 2ϵ)-approximate solution for dynamic inﬂuence maximization and has amortized running time at most O(Tmckϵ 2 log3(n/δ)).

The reduction is described in Algorithm 1-5, we provide some explanations here. From a high level, the execution of the algorithm is divided into phases. It 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 + n), there are at most O(log n) phases. Within each phase, the algorithm is divided into

3We remark this approach has been used for submodular maximization under various setting [5, 10, 37].

iterations. At the beginning of each iteration, the algorithm runs the ESTIMATE procedure in order to estimate the total number of RR set it needs to sample. It then ﬁxes a sampling probability p and samples two graphs, Hcv and Hest, dynamically. As explained before, Hest is used to measure the number of steps one takes for sampling RR sets, and Hcv is used to approximate the inﬂuence spread function. We stop sampling Hest and Hcv and start a new iteration whenever the number of step for constructing Hest exceeds 16Rm0.

Due to space limits, we defer detailed proof to the full version of this paper and outline a sketch below.

Algorithm 1 INITIALIZE

1: m 0, m0 0, n 0, n0 0. 2: V , E , Hcv , Hest . 3: R 0, p 0.

Algorithm 2 ESTIMATE

1: K 0. 2: repeat 3: Sample a RR set uniformly over V . 4: K K + 1. 5: until Rm0 steps have been taken 6: return K

Algorithm 3 BUILDGRAPH

1: Hcv (V, , ), Hest (V, , ), 2: R cϵ 2k log(n0/δ) . 3: K ESTIMATE(). 4: p K

n0 . 5: for node v V do 6: Sample the RR set Rv,est with prob p. 7: Sample the RR set Rv,cv with prob p. 8: for node u Rv,cv do 9: INSERT-EDGE-COV(u, v) to Hcv. 10: end for 11: end for

Algorithm 4 INSERT-NODE(u)

1: V V {u}, n n + 1. 2: if n 2n0 then 3: m0 m, n0 n. 4: BUILDGRAPH(). 5: else 6: VL,est VL,est {u} . 7: VL,cv VL,cv {u}. 8: VR,est VR,est {u} with prob p. 9: VR,cv VR,cv {u} with prob p. 10: end if

Algorithm 5 INSERT-EDGE(u, v)

1: E E {(u, v)}, m m + 1 2: if m 2m0 then 3: m0 m, n0 n. 4: BUILDGRAPH(). 5: else 6: for node v VR,est do 7: Augment the RR set Rv ,est to Rnew v ,est. 8: Rv ,est Rnew v ,est. 9: if the total steps of building Hest exceed 16Rm0 then 10: m0 m, n0 n. 11: Restart and BUILDGRAPH(). 12: end if 13: end for 14: for node v VR,cv do 15: Augment the RR set Rv ,cv to Rnew v ,cv. 16: INSERT-EDGE-COV(u , v ) to Hcv for all u Rnew v ,cv\Rv ,cv. 17: Rv ,cv Rnew v ,cv. 18: end for 19: end if

We ﬁrst focus on one single iteration of the algorithm. Recall that in each iteration, the number of nodes satisﬁes n [n0, 2n0) and the number of edge satisﬁes m [m0, 2m0), and the number of steps for sampling Hest never exceeds 16Rm0.

Bounds at initialization We prove the ESTIMATE procedure makes a good estimate on the sampling probability at the beginning of each iteration. Let AVG m0 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 1 2δ nck/8 , the number of RR sets ESTIMATE samples satisﬁes (1 ϵ) R AVG K (1 + ϵ) R AVG.

The initial steps to built Hest and Hcv are within [(1 ϵ)2Rm0, (1 + ϵ)Rm0] with high probability.

Lemma 3.4. Conditioning on the event of Lemma 3.3, with probability at least 1 4δ nck/8 , the total number of initial steps for building Hest and Hest are within [(1 ϵ)2R, (1 + ϵ)2R], .

Bounds on adaptive sampling We dynamically sample and augment RR sets after we initiate Hest and Hcv. Consider the t-th edge to arrive, let Zt,i 2m0 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 BUILDGRAPH did not sample the i-th node and its RR set, then we simply take Zt,i = 0. Slightly abuse of notation, we write Zj to denote the j-th random variable in the sequence Z0,1, . . . , Z0,n0, Z1,1, . . ., and we know {Zj}j 1 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.

Lemma 3.5. Let J1 be the smallest number such that PJ1 i=1 E[Zi] (1 ϵ)8R, and J2 be the largest number that PJ2 i=1 E[Zi] (1 + ϵ)8R. With probability at least 1 2δ nck/3 , we have J1 J J2.

With high probability, the total number of edge checked for Hcv is bounded by 16(1 + ϵ)2Rm0.

Lemma 3.6. Conditioning on the event of Lemma 3.5, with probability at least 1 δ nck , the total number of edges checked by INSERT-EDGE for Hcv is at most 16(1 + ϵ)2Rm0.

Approximation guarantee We prove that the coverage function induced on Hcv yields a good approximation on the inﬂuence spread function. At any time step t, let Vt be the set of node at time step t. For any node v Vt and node set S Vt, let xt,v,S = 1 if S Rv,cv = , and xt,v,S = 0 otherwise. That is, xt,v,S = 1 iff S has non-zero intersection with the RR set of node v at time step t. We note that if a node v was not sampled by INSERT-NODE and BUILDGRAPH, and hence does not appear in VR,cv, we set xt,v,S = 0.

Deﬁnition 3.7 (Normalized coverage function). Deﬁne fcv,t : 2Vt R+ to be the normalized coverage function. fcv,t(S) = n0

v Vt xt,v,S.

The normalized coverage function fcv,t is an unbiased estimator on the inﬂuence spread function and it achieves good approximation with high probability.

Lemma 3.8. At any time step t and S Vt, we have E[fcv,t(S)] = σt(S), where σt is the inﬂuence spread function at time t.

Lemma 3.9. After initializing Hest and Hcv, at any time step t. Let S Vt, |S| k. Assume the condition in Lemma 3.3 holds, then we have

Pr [fcv,t(S) > E[fcv,t(S)] + ϵ OPTt] δ nck/6 , and, (1)

Pr [fcv,t(S) < E[fcv,t(S)] ϵ OPTt] δ nck . (2)

The expectation is taken over the randomness of the construction of Hcv, and OPTt is deﬁned as the maximum (expected) inﬂuence 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 c 2 and let f : 2V R+ be an arbitrary set function. Let D be a distribution over functions g such that for all S V , Prg D[|f(S) g(S)| γ] δ nck . Let Sg be an α-approximate solution for function g, i.e. g(Sg) α max S V,|S| k g(S), then we have

f(Sg) α max S V,|S| k f(S) 2γ δ nck/2 .

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 at least by a factor of 2, with high probability.

Lemma 3.11. With probability at least 1 4δ nck/16 , there are at most O(log n) iterations in a phase.

Proof Sketch of Lemma 3.2. For correctness, by Lemma 3.8 and Lemma 3.9, the normalized coverage function fcv,t (deﬁned on Hcv) guarantees |fcv,t(S) E[fcv,t(S)]| = |fcv,t(S) σt(S)| ϵ OPTt

Algorithm 6 INITIALIZE

1: OPTi (1 + ϵ)i, Si = , i I

Algorithm 7 REVOKE(i)

1: if there exists a node u such that f Si(u) OPTi f(Si)

k and |S| < k then 2: Si Si {u}. 3: REVOKE(i). 4: end if

Algorithm 8 INSERT-EDGE-COV(u, v)

1: for i I do 2: if f Si(u) OPTi f(Si)

k and |S| < k then 3: Si Si {u}. 4: REVOKE(i). 5: end if 6: end for

for every time step t. Combining with Lemma 3.10, an α-approximate solution to the dynamic MAX-k coverage problem translates to a solution set St that satisﬁes f(S) (α 2ϵ) OPTt.

For amortized running time. There are O(log n) phases, and by Lemma 3.11, there are at most O(log n) iterations in each phase. Within each iteration, the ESTIMATE procedure and the construction of Hest takes O(m0ckϵ 2 log n) steps in total and O(kϵ 2 log n) per update. By Lemma 3.4 and Lemma 3.6, with high probability, the construction of Hcv takes 16(1 + ϵ)2Rm0 steps in total and O(kϵ 2 log n) steps per updates. Hence, there are O(km0ϵ 2 log n) updates to the dynamic MAX-k coverage problem on Hcv. Taking an union bound, the overall amortized running time per update is bounded by log n log n (kϵ 2 log n + kϵ 2 log n + kϵ 2 log n Tmc) O(Tmckϵ 2 log3 n).

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 I = {0, 1, . . . , ϵ 1 log n }. The algorithm maintains |I| threads and for the i-th thread, INSERT-EDGECOV and REVOKE augments the solution set Si only when the marginal value of a node u exceeds the threshold, i.e. f Si(u) OPTi f(Si)

k . In particular, the threshold decreases over time and each time it decreases, REVOKE scans over all existing nodes in VL. The algorithm returns the solution set with maximum value at each time step, i.e., return arg max Si ft(Si). 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 ϵ)-approximation at every time step and the amortized running time of the algorithm is at most O(ϵ 1 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 ϵ)-approximate to the optimal one.

Proof Sketch. Let the current optimum satisﬁes (1 + ϵ)i < OPT (1 + ϵ)i+1 for some i I. For the i-th thread, if |Si| < k, then one can prove f(Si) (1+ϵ) 1 OPT. On the otherside, if |Si| = k. Let si,j be the j-th element added to the set Si, and denote Si,j = {si,1, . . . , si,j}. Our algorithm guarantees f(Si,j+1) f(Si,j) 1

k(OPTi f(Si,j)) for all j [k]. Unravel the recursion, one has f(Si) 1 1

Lemma 3.14. The algorithm 6-8 has amortized running time O(ϵ 1 log k).

Proof Sketch. We prove that for each thread i I, the amortized running time is O(1). Let V i R VR be nodes covered by Si. Let P(t) denote the number of operations performed on the i-th thread up to time t. For each edge e = (u, v), let Xe denote whether the edge e is covered by V i R, i.e. Xe = 1 if v V i R and Xe = 0 otherwise. Similarly, for each node v VR, let Yv denote whether node v is included in V i R, i.e., Yv = 1 if v V i R and Yv = 0 otherwise. For each node u VL, let Zu denote whether node u is included in Si, i.e., Yv = 1 if v Si and Yv = 0 otherwise. Deﬁne the potential function Φ : t R+:

Φ(t) := 2|Vt| + 2|Et| + 2 X

e Et Xe + X

v VR Yv + 2 X

We prove P(t) Φ(t) always holds. This sufﬁces for our purpose as one can easily show Φ(t) 5t. The claim is executed by an induction showing P(t) P(t 1) Φ(t) Φ(t 1) holds for t.

Taking α = 1 1/e and Tmc = O(ϵ 1 log n), we wrap up the proof of Theorem 3.1.

4 Fully dynamic inﬂuence maximization

In the fully dynamic model, the social network involves over time and all four types of change exhibit. Our main delivery is a sharp computational hardness result. We prove that under the SETH, unless the amortized running time is n1 o(1), the approximation ratio can not even be 2 (log n)1 o(1). We ﬁrst provide some background on ﬁne-grain complexity. We reduce from the Strong Exponential 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 ﬁrst proposed in the seminal work of [31] and it is widely believed in the computational complexity, see [53, 47] for detailed survey.

Conjecture 4.1 (Strong Exponential Time Hypothesis (SETH), [31]). For any ϵ > 0, there exists k 3 such that k-SAT on variables can not be solved in time O(2(1 ϵ)n).

Our starting point is the following SETH-based hardness of approximation result. The result is proven in [2, 17] using the distributed PCP framework [2, 46] for hardness of approximation results in P.

Theorem 4.2 ([2, 17, 1]). Let ϵ > 0, m = no(1) and t = 2(log n)1 o(1). 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(n2 ϵ) :

YES instance. There exists two sets A A, B B such that B A;

NO instance. For every A A, B B we have |A B| < |B|/t.

Figure 1: The hard instance for fully dynamic inﬂuence maximization.

Theorem 4.3. Assuming SETH, in the fully dynamic inﬂuence maximization problem under IC model, no algorithm can achieve 2 (log n)1 o(1) approximation unless the amortized running time is n1 o(1).

Proof Sketch. Let m = no(1), t = 2(log n)1 o(1), k = 1. Given an instance A, B of the problem in Theorem 4.2, we reduce it to DIM. We assume |Bτ| t for all τ [n] as we can duplicate the ground element for t times. Consider the following inﬂuence graph G = (V, E, p), where the inﬂuence probability on all edges are 1. The node set V is partitioned into V = V1 V2 V3, |V1| = n, |V2| = m, |V3| = m2t. Intuitively, the i-th node v1,i of V1 corresponds to the set Ai A, and the j-th node v2,j in V1 correspond to the j-th element of ground set [m]. There is a directed

edge from v1,i to v2,j, iff the j-th element is contained in the set A1. We write nodes in V3 as {V3,j,ℓ}j [m],ℓ [mt], and there is a directed edge node v2,j to v3,j,ℓ, j [m], ℓ [mt].

Consider the following update sequence of the DIM problem. The graph G is loaded ﬁrst and then followed by n consecutive epochs. In the τ-th epoch, all edges between V2 and V3 are deleted, and for each j Bτ, we add back the edge between v2,j and v3,j,ℓfor all ℓ [mt].

One can show the total number of updates is at most n1+o(1). We prove by contrary and suppose there is an algorithm for DIM that achieves 2/t-approximation in n1 ϵ time. Under the above reduction, we output YES, if for some epoch τ [n], the DIM algorithm outputs a solution with inﬂuence spread greater than 2m|Bτ|. We output NO otherwise. One can prove (1) if there exists Ai A, Bτ B such that Bτ Ai, then we output YES, and, (2) if |Ai Bτ| < |Bτ|/t for any i, τ [n], the algorithm outputx NO. Hence, we conclude under SETH, there is no 2/t-approximation algorithm unless the amortized running time is O(n1 ϵ).

The lower bound can be extended to the LT model, under the additional constraints that the algorithm only selects seeds from a prescribed set V V . This a natural assumption that has been made/discussed in previous work [20, 36, 48] for the LT model. The construction is similar to Theorem 4.4, with the exception that (1) the weight on edges between V1 and V2 are 1/n and all other edges have weight 1, (2) the node set V is partitioned into four parts V1 V2 V3 V4. |V4| = nm2t and each node in V3 is connected to n nodes in V4. Detailed proof can be found in the full version of this paper. Theorem 4.4. Assuming SETH, for the fully dynamic inﬂuence maximization problem under LT model, if the algorithm is only allowed to select seed from a prescribed set, then no algorithm can achieve 2 (log n)1 o(1) approximation unless the amortized running time is n1 o(1).

5 Discussion

We study the dynamic inﬂuence 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 ϵ)-approximation and has amortized running time k poly(log n, ϵ 1), which matches the state of art ofﬂine IM algorithm up to poly-logarithmic factor. For the fully dynamic model, we prove that under SETH, no algorithm can achieve 2 (log n)1 o(1)

approximation unless the amortized running time is n1 o(1). 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 inﬂuence maximization problem under mild assumptions, e.g. what if the graph is bipartite?

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 NSF grants CCF-1763970 AF, CCF-1910700 AF and a softbank grant, and by Xi Chen s NSF grants NSF CCF-1703925.

Broader Impact

Our work is mainly theoretical with no foreseeable ethical issues.

[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 pcp theorems for hardness of approximation in p. 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 inﬂuential node discovery in dynamic social networks. In Proceedings of the 2012 SIAM International Conference on Data Mining, pages 636 647. SIAM, 2012.

[4] Noga Alon, Iftah Gamzu, and Moshe Tennenholtz. Optimizing budget allocation among channels and inﬂuencers. 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 on the ﬂy. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 671 680, 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-seventh annual ACM-SIAM symposium on Discrete algorithms, 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 2359 2370, 2018.

[8] Eric Balkanski, Nicole Immorlica, and Yaron Singer. The importance of communities for learning to inﬂuence. 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 on 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 1138 1151, 2018.

[12] Albert-Laszlo Barabâsi, Hawoong Jeong, Zoltan Néda, Erzsebet Ravasz, Andras Schubert, and Tamas Vicsek. Evolution of the social network of scientiﬁc collaborations. Physica A: Statistical mechanics and its applications, 311(3-4):590 614, 2002.

[13] Christian Borgs, Michael Brautbar, Jennifer Chayes, and Brendan Lucier. Maximizing social inﬂuence in nearly optimal time. In Proceedings of the twenty-ﬁfth 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 maximization. In International Conference on 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 maximization 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-Zentrum fuer Informatik, 2018.

[18] Wei Chen, Laks VS Lakshmanan, and Carlos Castillo. Information and inﬂuence propagation in social networks. Synthesis Lectures on Data Management, 5(4):1 177, 2013.

[19] Wei Chen and Binghui Peng. On adaptivity gaps of inﬂuence maximization under the independent cascade model with full-adoption feedback. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.

[20] Wei Chen, Binghui Peng, Grant Schoenebeck, and Biaoshuai Tao. Adaptive greedy versus non-adaptive greedy for inﬂuence maximization. In Proceedings of the AAAI Conference on Artiﬁcial Intelligence, volume 34, pages 590 597, 2020.

[21] Wei Chen, Yajun Wang, and Siyu Yang. Efﬁcient inﬂuence 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):1746 1778, 2016.

[23] Xi Chen and Binghui Peng. On the complexity of dynamic submodular maximization. ar Xiv preprint ar Xiv:2111.03198, 2021.

[24] Xiaodong Chen, Guojie Song, Xinran He, and Kunqing Xie. On inﬂuential nodes tracking in dynamic social networks. In Proceedings of the 2015 SIAM International Conference on Data Mining, pages 613 621. SIAM, 2015.

[25] Alina Ene and Huy L Nguyen. Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on 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.

[29] Daniel Golovin and Andreas Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artiﬁcial 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, 45(3):947 1006, 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 inﬂuence maximization for hyperparametric 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. In International Conference on Machine Learning, pages 3311 3320. PMLR, 2019.

[34] Ehsan Kazemi, Morteza Zadimoghaddam, and Amin Karbasi. Scalable deletion-robust submodular maximization: Data summarization with privacy and fairness constraints. In International conference on machine learning, pages 2544 2553. PMLR, 2018.

[35] David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of inﬂuence 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. Inﬂuence maximization in undirected networks. In Proceedings of the Twenty-ﬁfth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1482 1496. SIAM, 2014.

[37] Silvio Lattanzi, Slobodan Mitrovi c, Ashkan Norouzi Fard, Jakub Tarnawski, and Morteza Zadimoghaddam. Fully dynamic algorithm for constrained submodular optimization. Advances in Neural Information Processing Systems, 2020.

[38] Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne Van Briesen, 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 inﬂuence maximization under linear threshold model. Advances in Neural Information Processing Systems, 33, 2020.

[40] Yuchen Li, Ju Fan, Yanhao Wang, and Kian-Lee Tan. Inﬂuence maximization on social graphs: A survey. IEEE Transactions on Knowledge and Data Engineering, 30(10):1852 1872, 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):1019 1031, 2007.

[42] Xiaodong Liu, Xiangke Liao, Shanshan Li, Si Zheng, Bin Lin, Jingying Zhang, Lisong Shao, Chenlin Huang, and Liquan Xiao. On the shoulders of giants: incremental inﬂuence maximization in evolving social networks. Complexity, 2017, 2017.

[43] Morteza Monemizadeh. Dynamic submodular maximization. Advances in Neural Information Processing Systems, 33, 2020.

[44] Naoto Ohsaka, Takuya Akiba, Yuichi Yoshida, and Ken-ichi Kawarabayashi. Dynamic inﬂuence analysis in evolving networks. Proceedings of the VLDB Endowment, 9(12):1077 1088, 2016.

[45] Binghui Peng and Wei Chen. adaptive inﬂuence maximization with myopic feedback. Advances in Neural Information Processing Systems 32 pre-proceedings (Neur IPS 2019), 2019.

[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, 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. Inﬂuence maximization on 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 in 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. Inﬂuence 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. Inﬂuence maximization: Near-optimal time complexity meets practical efﬁciency. 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 inﬂuence maximization on dynamic social streams.(2017). 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 ﬁne-grained questions in algorithms and complexity. In Proceedings of the ICM, volume 3, pages 3431 3472. World Scientiﬁc, 2018.