key: cord-0291914-5xcp6t6g authors: Guo, Jianxiong; Wu, Weili title: Adaptive Influence Maximization: If Influential Node Unwilling to Be the Seed date: 2020-05-17 journal: nan DOI: 10.1145/3447396 sha: 493fda54aa57edfabbde4cb4bc9772228bb9ee96 doc_id: 291914 cord_uid: 5xcp6t6g Influence maximization problem attempts to find a small subset of nodes that makes the expected influence spread maximized, which has been researched intensively before. They all assumed that each user in the seed set we select is activated successfully and then spread the influence. However, in the real scenario, not all users in the seed set are willing to be an influencer. Based on that, we consider each user associated with a probability with which we can activate her as a seed, and we can attempt to activate her many times. In this paper, we study the adaptive influence maximization with multiple activations (Adaptive-IMMA) problem, where we select a node in each iteration, observe whether she accepts to be a seed, if yes, wait to observe the influence diffusion process; If no, we can attempt to activate her again with a higher cost or select another node as a seed. We model the multiple activations mathematically and define it on the domain of integer lattice. We propose a new concept, adaptive dr-submodularity, and show our Adaptive-IMMA is the problem that maximizing an adaptive monotone and dr-submodular function under the expected knapsack constraint. Adaptive dr-submodular maximization problem is never covered by any existing studies. Thus, we summarize its properties and study its approximability comprehensively, which is a non-trivial generalization of existing analysis about adaptive submodularity. Besides, to overcome the difficulty to estimate the expected influence spread, we combine our adaptive greedy policy with sampling techniques without losing the approximation ratio but reducing the time complexity. Finally, we conduct experiments on several real datasets to evaluate the effectiveness and efficiency of our proposed policies. Online social networks (OSNs) were blossoming prosperously in recent decades and have become the main means of communication between people such as Wechat, Facebook, Twitter, and LinkedIn. More and more people participate to discuss the topics that they are interested in on these social platforms. Many companies or advertisers exploit the relations established in OSNs to spread their products, opinions, or innovations. They provide those influential individuals (called "seed nodes") with free or discounted samples, in order to create widespread influence across the whole network via word-of-mouth effect [7] [20] . Based on that, influence maximization (IM) problem [17] was formulated, which selects a subset of users (called "seed set") for an information cascade to maximize the expected follow-up adoptions (influence spread). It is a general model for a number of realistic scenarios, such as viral marketing. In [17] , they created two discrete influence diffusion models, independent cascade model (IC-model) and linear threshold model (LT-model), where IC-model relies on peer-to-peer communication but LT-model computes the total influence from user's neighbors. Then, they proved that the IM problem is NP-hard and provided a (1 − 1/ )approximate algorithm by simple the greedy strategy in the framework of submodularity. After this groundbreaking work, a sequence of derivative problems appeared and were solved under the different constraints and scenarios [2] [3] [11] [12] , such as profit maximization [13] , community partition, and rumor blocking (detection). Despite these developments, the existing researches on the IM problem have a crucial drawback. When selecting a seed set at the beginning, they all seem to take it for granted that every user in their selected seed set can be activated successfully to become an active seed and then spread the influence as they wish. However, there are some users unwilling, even impossible, to be the influencers. For example, the hottest topic at the moment, Coronavirus in Wuhan, China. Some non-profit organizations or official media are trying to make celebrities speak out to ease the panic among the people. However, due to self-interest or other factors, some celebrities are not willing to be their "seed nodes". Then, we have two options, one is trying to persuade those who stand on the opposite side sentimentally and rationally, the other is giving up and look for other potential "seed nodes". Based on that, we design a new IM with multiple activations (IMMA) problem, where a node can be activated to be an influencer with a probability when we select it as a seed and we can attempt to activate it many times. For the same node, each attempt is referred to as a "trial" and each trial has a cost. If the first trial fails, we can conduct the second trial, the third trial, etc., but their cost is higher than the first. Most existing techniques on the IM problem concentrate on non-adaptive strategies, which are required to select all seed nodes at once without observing actual node status and diffusion process. In other words, we need to point out the seed set and the number of trials for each node in this seed set in one batch. As a result, it may return a seed that cannot be activated actually or assign too many trials to this node. For example, we give a seed three trials and it is activated in the first trial, so the remaining two waste our budget. Thus, the non-adaptive seeding strategy is not the best choice to solve our IMMA problem. Golovin et al. [8] studies the IM problem under the adaptive strategy, they select the ( + 1)-th node after observing the influence diffusion of the first nodes until all seed nodes are chosen. Based on that, the Adaptive-IMMA problem is proposed in this paper, which selects a seed and attempts to activate it in each iteration. If successful, wait to observe its influence process; If failed, record this failed trial. Those nodes on which all the trials are unsuccessful can be considered as seed again in a later step. Golovin et al. [8] provided a (1 − 1/ )-approximate algorithm by an adaptive greedy policy for the adaptive IM problem in the framework of adaptive monotonicity and adaptive submodularity. However, for our Adaptive-IMMA problem, its solution is a seeding vector ∈ Z + , not a seed set ⊆ , where each component ( ) means how many activation attempts we give to user . It will be executed sequentially. For example, ( ) = , we will do trial ⟨ , 1⟩, trial ⟨ , 2⟩ until trial ⟨ , ⟩ on user . The domain of the objective function is defined on integer lattice, not generally on set. Thus, traditional analytical methods based on adaptive submodularity cannot be applied to analyze our problem. The submodularity shows us with diminishing marginal gain property in set function. For functions defined on integer lattice, such a property exists as well, called dr-submodularity. Based on that, we define the concepts of adaptive monotonicity on integer lattice and adaptive dr-submodularity formally, which are extended from adaptive submodularity on set function [8] and dr-submodularity on integer lattice [22] . Then, we formulate the objective function of our Adaptive-IMMA problem and prove it is adaptive monotone on integer lattice as well as adaptive dr-submodular. Each trial ⟨ , ⟩ is associated with a cost (⟨ , ⟩) and the costs of different trials are different. Given a randomized policy ( ), the total budget is an expected knapsack constraint such that the total cost of the seeding vector returned by ( ) is less than expectedly. Then, we study the approximate performance of adaptive greedy policy for maximizing adaptive monotone and adaptive dr-submodular functions under the expected knapsack constraint, which is a non-trivial generalization of existing analysis about the approximate performance of adaptive submodular functions. Assume (⟨ , ⟩) ≤ (⟨ , + 1⟩), it returns an acceptable solution with (1 − 1/ )-approximate ratio. Besides, it is #P-hard to compute the expected influence spread given a seed set under the IC-model [4] and LT-model [6] . The complexity of our objective function is higher. In order to overcome this shortcoming, we design an unbiased estimator of the conditional expected marginal gain for our problem based on the reverse influence sampling (RIS) [1] . Adapted from state-ofthe-art EPIC algorithm [16] for the IM problem, combined it with our adaptive greedy policy, we formulate a sampled adaptive greedy policy and achieve a (1 − exp(−1 + )) expected approximation guarantee. Its time complexity is reduced significantly. Finally, we conduct several experiments to evaluate the superiority of our adaptive policies over their corresponding non-adaptive algorithms and the sampled adaptive greedy policy over other heuristic adaptive policies, which support the effectiveness and efficiency of our approaches strongly. Influence maximization (IM): The IM problem has been studied extensively. Kempe et al. [17] formulated IM as a combinatorial optimization problem, proposed the triggering model, including IC-model and LT-model, and gave us a greedy algorithm with (1 − 1/ − )-approximation. It was implemented by Monte-Carlo (MC) simulations with high time complexity. Chen et al. [4] [6] followed Kempe's work and proved its #P-hardness to compute the expected influence spread. Thus, the running time was too slow to apply to larger real networks. After those seminal works, a lot of researchers made an effort to improve its time complexity. Brogs et al. [1] proposed the concept of reverse influence sampling (RIS) to estimate the expected influence spread, which is scalable in practice and guaranteed theoretically at the same time. Then, a series of more efficient randomized algorithms were arisen, such as TIM/TIM+ [30] , IMM [29] , SSA/D-SSA [19] , and OPIM-C [27] . Recently, Han et al. [14] provided us with an EPIC algorithm with an expected approximation guarantee. Then, the EPIC was improved further based on the OPIM-C [27] , which is the most efficient algorithm to solve the IM problem until now [16] . They were scalable algorithms for the IM problem and can be adapted to other relative problems. However, all of these are used to solve the IM problem under the non-adaptive setting. Dr-submodular maximization and its applications in social networks: Defined on integer lattice, dr-submodular maximization problem is a hot topic that attracts a lot of researchers recently. Soma et al. [22] formalized dr-submodularity on integer lattice inspired by the diminishing return property on set and addressed a submodular cover problem. Soma et al. [24] studied the monotone dr-submodular maximization problem on integer lattice systematically, where they proposed a series of (1 − 1/ − )-approximate algorithms for the cardinality constraint, the knapsack constraint, and the polymatroid constraint. Applied to solve problems social networks, Chen et al. [5] gave a lattice IM problem defined on integer lattice, whose objective function is monotone and dr-submodular. Then, they proposed azi scalable algorithm with (1 − 1/ − ) approximation ratio that is adapted from the IMM [29] . Guo et al. [10] proposed a continuous activity maximization problem and provided a solution framework for maximizing a monotone but not dr-submodular function by the sandwich approximation approach. Other literature and results about dr-submodular maximization and its applications are shown in [9] [23] [15] . Adaptive influence maximization: Golovin et al. [8] extended the submodularity to adaptive settings and obtained the same approximation ratio for the adaptive IM problem because its objective function is adaptive monotone and adaptive submodular under the full-adoption feedback model where only one node can be selected in each iteration. However, the objective function of the adaptive IM problem is not adaptive submodular under the myopic feedback model [8] or the partial feedback model [32] [28] . Tong et al. [31] gave us a systematic framework about the adaptive IM problem when it is not adaptive submodular, where they designed a seeding strategy and showed the approximation analysis by introducing the concept of regret ratio. Unfortunately, all these works were based on a fact that the expected influence spread can be computed accurately in polynomial time, which is an unrealistic assumption. To improve its scalability, Han et al. [14] proposed an AdaptGreedy framework instantiated by scalable IM algorithms to solve the adaptive IM problem where it can select a batch of seed nodes in each iteration, which returns a worst-case approximation guarantee with high probability. Sun et al. [25] studied a multi-round influence maximization (MRIM) problem where information diffuses in multiple rounds independently from different seed sets. They considered MRIM problem under the adaptive setting and designed an adaptive algorithm with (1 − exp(1/ − 1) − ) approximation instantiated by the IMM [29] . Tang et al. [26] considered the seed minimization problem under the adaptive setting and proposed an ASTI algorithm that offers an expected approximation ratio. Recently, Huang et al. [16] pointed out there are some mistakes in the approximation analysis of adaptive policies in [14] [25] . They fixed the previous AdaptGreedy framework in [14] and proved it has a (1 − exp( ( − 1))) expected approximation guarantee instantiated by their improved EPIC in [16] . Neverthelessbut, none of them considered a problem that is adaptive dr-submodular, especially under the expected knapsack constraint. This is the main contribution in this paper. In this section, we define the problem of our adaptive influence maximization on multiple activations formally and introduce some preliminary knowledges. A social network can be denoted by a directed graph = ( , ) where = { 1 , 2 , · · · , } is the node (user) set with | | = , = { 1 , 2 , · · · , } is the edge set with | | = , which describes the relationship between users. For any edge = ( , ) ∈ , is an outgoing neighbor of and is an incoming neighbor of . For any node ∈ , we denote by − ( ) its set of incoming neighbors and + ( ) its set of outgoing neighbors. Each edge ( , ) is associated with a diffusion probability ∈ (0, 1]. Thus, the influence diffusion on this network is stochastic. Let ⊆ be a given node set, the influence diffusion initiated by can be described as a discrete-time stochastic process under the IC-model [17] . Let ⊆ be the active node set at time step . At time step 0 , all nodes in are active, namely 0 := . We call 0 the seed set, and node in this set is the seed of this cascade. At time step , ≥ 1, we set := −1 first; then, for those nodes activated first at time step −1 , ∈ ( −1 \ −2 ), it activates its each inactive outgoing neighbor with the probability by one chance. If activates at successfully, we add into . The influence diffusion terminates when no more inactive nodes can be activated. The above influence diffusion process can be interpreted by sampling a graph realization. Given a directed network = ( , ), we can decide whether an edge ( , ) ∈ is live or blocked with probability . To remove these blocked edges, the remaining graph is a subgraph of . This subgraph is called "graph realization". These edges existed in are known as live edges, or else called blocked edges. For each edge ( , ) ∈ , it exists in a graph realization with probability under the IC-model. There are 2 possible graph realizations altogether under the IC-model. Let G be the set of all possible graph realizations with |G| = 2 , and be a graph realization sampled from G, denoted by ← G, with probability as follows: Remark 1. In most references, they usually called "graph realization" as "realization" or "possible world". They all refer to an instance of a probabilistic social network. We will discuss a different concept "realization" later. To avoid ambiguity, we use "graph realization" here. The problem and algorithms discussed later in this paper are based on the IC-model, because the adaptive IM problem can be adaptive submodular only under the IC-model. Given a seed set ⊆ and a graph realization ∈ G, the size of final active set that can be reached by the seed set under the graph realization is denoted by ( ). Thus, the expected influence spread ( ) under the IC-model can be defined as follows: where it is the weighted expectation of influence spread over all possible graph realizations. The influence maximization (IM) problem aims to find a seed set ⊆ , such that | | ≤ , to maximize the expected influence spread ( ). From the above, in this non-adaptive setting, the seed set is selected once without the knowldge of what graph realization happens in the actual diffusion process. Thus, the actual influence spread of may be much worse than our expectation. Instead, in an adaptive manner, we select a node from at a time and wait to observe the actual diffusion result. Relied on this observation, we select the next node that could activate those inactive nodes as much as possible. It is called full-adoption feedback model [8] . In other words, when we select a node as seed, we are able to know the status of all edges going out from those nodes that can be reached by through live edges in current graph realization. Golovin et al. [8] introduced two important concepts, adaptive monotonicity and adaptive submodularity, and showed that the simple adaptive greedy policy has a (1 − 1/ )-approximation guarantee. In the traditional IM problem, it assumes that each user in the seed set we select is activated successfully and then spread our given information cascade. However, in the real scenario, not all users in the seed set are willing to be an influencer. Based on that, we consider a user can be activated as a seed with a certain probability and we can attempt to activate her many times. For each user ∈ , there is a probability ∈ (0, 1] with which she can be activated successfully when we select her as a seed. Let Z + be the collection of non-negative integer vector, each component is indexed by a node in . For a vector ∈ Z + , if ( ) = , it means that we select user and try to activate her as a seed times. Given a social graph = ( , ), we have a total budget ∈ R + , a vector ∈ Z + , and a cost function : × Z + → R + . Here, for each user ∈ , we assume she can be tried to activate as a seed at most ( ) times, and it costs (⟨ , ⟩) when the -th trial of activating user as a seed happens. Given a seeding vector and a graph realization ∈ G, the expected number of active nodes ( ) under the graph realization can be defined as follows: Similar to Equation (2), we have where ( ) is the expected influence spread over all possible graph realizations given a seeding vector . The IM on multiple activations (IMMA) problem is formulated, which seeks a seeding vector ∈ Z + that maximizes ( ) subject to ( ) ≤ and ≤ . Here, we denote ( ) by Each trial is independent. In the adaptive setting, the IMMA problem can be transformed to find a policy , where we select seed nodes step by step. The parameter setting is the same as before. A seeding vector is initialized to = 0 ∈ Z + . When selecting an inactive user ∈ with ( ) < ( ), we increase ( ) by 1 and attempt to activate to be an active seed with probability . At this moment, we need to observe two states as follows: (1) Node state: whether user can be activated to be an active seed successfully; and (2) Edge state: If becomes an active seed, wait to observe the influence diffusion process (related edges is live or blocked) until no new nodes can be activated. We repeated this process until no remaining budget exists. Next, we define the states of the given network. Given a social graph = ( , ), for each node ∈ , the state of can be denoted by ∈ {0, 1, ?} ( ) , where ( ) = 1 means user is activated as a seed successfully in the -th trial, or not succeed, ( ) = 0. ( ) =? if the result of -th trial is unknown. Similar, for each edge ( , ) ∈ , the state of ( , ) can be denoted by ∈ {0, 1, ?}, where = 1 means edge ( , ) is live, and = 0 means edge ( , ) is blocked. =? if the state of ( , ) is unknown. At the beginning, the states of all nodes and edges are ?. After defining the state variables, we have a function mapping like where is called a realization (full realization), where the states of all items are known. We say that ( ) ∈ {0, 1} ( ) is the state of user ∈ , ( ) ( ) ∈ {0, 1} is the state of the -th trial for user , and (( , )) ∈ {0, 1} is the state of edge ( , ) ∈ under the realization . Let Φ be the set of all possible realizations. We define as a realization sampled from Φ, denoted by In this adaptive seeding process, after the -th trial to activate node is finished, its state and the states of those related edges could be updated. Our observation until now can be described by a partial realization . It is a function of observed items to their states. For ∈ , ( ) ∈ {0, 1, ?} ( ) , and ( ) ( ) =? if the result -th trial to node is not yet observed. For ( , ) ∈ , (( , )) ∈ {0, 1, ?} as well. The domain of a partial realization can be defined as dom( ) = {⟨ , ⟩| ( ) ( ) ≠?}, which is the trials that have been done. We say is consistent with a realization if the states of items in the domain of are equal between them, denoted by ∼ . Given , ′ and , if dom( ) ⊆ dom( ′ ) and ∼ , ′ , we say is a subrealization of ′ , denoted by ⊆ ′ . Let ( ) be a randomized policy based on a random variable that represents a random source of this randomized policy. The ( ) is a function mapping from current seeding vector and one of its possible partial realizations to a node * , then it executes the ( ( * ) + 1)-th trial that tries to select node * as a seed. Here, we denote by * = ( , , ) where * is the next potential seed that policy ( ) will select based on and . The influence spread gained from policy ( ) under the realization can be defined as follows: where ∈ {0, 1} is the graph realization contained in realization and ( ( ), ) is the seeding vector returned by policy under the realization . The expected influence spread of policy ( ) can be shown as follows: Therefore, the adaptive IM on multiple activations (Adaptive-IMMA) problem is formulated, which can be defined in Problem 1. Problem 1 (Adaptive-IMMA Problem). Givne a social graph = ( , ), a budget ∈ R + , a vector ∈ Z + , and a cost function : × Z + → R + , it aims to find a policy * ( ) that maximizes its expected influence spread defined in Equation (9) Given a seed vector ∈ Z + , we say "increase ( ) by 1" is equivalent to execute the trial ⟨ , ( )+1⟩. For each node ∈ , we assume (⟨ , 1⟩) ≤ (⟨ , 2⟩) ≤ · · · ≤ (⟨ , ( )⟩). It is valid becuase in general, we execute trial ⟨ , + 1⟩ only when trial ⟨ , ⟩ fails to activate node as a seed, thereby the cost of trial ⟨ , + 1⟩ is larger than the cost of ⟨ , ⟩. In this section, we first introduce some concepts of submodularity on integer lattice, and then, generalize several properties of our Adaptive-IMMA problem. Usually, for two sets , ⊆ , a set function ℎ The submodularity of set function can be generalized by diminishing return property, in other words, submodular if ℎ( ∪ { }) − ( ) ≥ ( ∪ { }) − ( ) for any ⊆ ⊆ and ∉ . On integer lattice, for two vectors , ∈ Z + , let ∨ ∈ Z + be defined as ( ∨ ) ( ) = max{ ( ), ( )}, and ∧ ∈ Z + be defined as ( ∧ ) ( ) = min{ ( ), ( )} for any ∈ . A vector function : Z + → R + is defined on the integer lattice Z + . This vector function is monotone if ( ) ≤ ( ) for any ≤ ∈ Z + and lattice submodular if ( ) + ( ) ≥ ( ∨ ) + ( ∧ ) for any , ∈ Z + . When the domain of vector are restricted to binary lattice {0, 1} , the vector function is reduced to set function ℎ. Thus, the submodularity on set function is a special case of submodularity on integer lattice. Besides, we consider a vector function : Z + → R + is diminishing return submodular (drsubmodular) if ( + ) − ( ) ≥ ( + ) − ( ) for any ≤ and ∈ , where ∈ Z is the -th unit vector with the -th component being 1 and others being 0. Here, there is a little different from the submodularity on set function. is lattice submodular does not mean it is dr-submodular on integer lattice, but the opppsite is true. Thus, dr-submodularity is a stronger property than lattice submodular. We consider the dr-submodularity later. Assume that = 1 for each node ∈ and seeding vector ∈ {0, 1} , the IMMA problem can be reduced to the IM problem naturally. Therefore, the IMMA problem is more general and inherits the NP-hardness of IM. In the traditional IM problem, the expected influence spread shown as Equation (2) is monotone and submodular on the seed set [17] . In order to study the properties of our Adaptive-IMMA problem, we define its marginal gain first, that is Definition 1 (Conditional Expected Marginal Gain on Integer Lattice). Given a seeding vector ∈ Z + and a partial realization generated by it, the conditional expected marginal gain of increasing ( ) by 1 is defined as where the expectation is on Here, Δ( | , ) is the expected gain by increasing ( ) by 1 conditioned on current partial realization of and Δ( ( )| , ) is the expected gain by running ( ) after observing partial realization but neglect it. Then, adapted from [8] , the concepts of adaptive monotonicity and adaptive submodularity are described as follows: Definition 2 (Adaptive Monotonicity). A vector function (·, ) is adaptive monotone if the conditional expected marginal gain with resprect to distribution Pr[ ] of any node , seeding vector , and its possible partial realization is nonnegative, that is Definition 3 (Adaptive dr-submodularity). A vector function (·, ) is adaptive dr-submodular if the conditional expected marginal gain with resprect to distribution Pr[ ] of any node , seeding vectors , with ≤ , and their possible partial realizations (generated by ), ′ (generated by ′ ) with ⊆ ′ satisfies the following inequality, that is For our Adaptive-IMMA problem, the function (·, ) is adaptive monotone and adaptive submodular according to Theorem 1 and Theorem 2. Theorem 1. The objective function (·, ) is adaptive monotone. Proof. To prove adaptive monotonicity, we are required to show Δ( | , ) ≥ 0. Given a seeding vector and its partial realization , we denote the marginal gain under the realization ∼ as follows: If node has been activated as a seed under the partial realization , there is no marginal gain. Otherwise, it is possible to be activated by increasing ( ) by 1, namely trial ⟨ , ( ) + 1⟩ succeeds. Thus Proof. To prove its adaptive dr-submodularity, we are required to show Δ( | , ) ≥ Δ( | , ′ ) for any two partial realizations , ′ such that ≤ and ⊆ ′ . Considering two fixed partial realizations with ⊆ ′ , which are generated by seeding vector and respectively. We defined the generative active seed set under the seeding vector and its partial realization as Obviously, we have ( , ∼ ) ⊆ ( , ′ ∼ ′ ) because of ≤ and ⊆ ′ . Here, we assume two fixed realizaitons, ∼ , ′ ∼ ′ , and ( ) = ( ) − ( ). For each ⟨ , ⟩ ∉ dom( ′ ), we have ( ) ( − ( )) = ′ ( ) ( ); for each ( , ) ∉ ( ′ ), we have (( , )) = ′ (( , )). We define the area that these two fixed realizations , ′ share as . To show Δ( | , ∼ ) ≥ Δ( | , ′ ∼ ′ ), we can consider these three cases: ( = ∑︁ Since ∼ Pr[ | ∼ ] = 1, we have = ∑︁ Therefore, we have Δ( | , ) ≥ Δ( | , ′ ) for any ≤ and their partial realizations ⊆ ′ . The proof of adaptive submodular is completed. □ In this section, we propose algorithms to solve our Adaptive-IMMA problem and give an approximation ratio with necessary theoretical analysis. We define a randomized adaptive greedy policy ( ) here. The seeding vector is initialized to = 0 ∈ Z + . In each iteration, the ( ) selects the node * ∈ that maximizes Δ( | , )/ (⟨ , ( )+1⟩) Algorithm 1 AdaptiveGreedy ( , , , , ) Input: A graph = ( , ), a function (·, ), a budget ∈ R + , a vector ∈ Z + and, a cost function : × Z + → R + Output: A seeding vector ∈ Z + and ( , ) where ( ) < ( ) and is the partial realization generated by the current , then increases ( * ) by 1. Then, we need to observe the state of * and update this partial realization . The ( ) repeats above procedure, terminates until ( ) ≥ , or terminates with a probability. The main idea of adaptive greedy policy is shown in Algorithm 1. Shown as line 5 to 7 of Algorithm 1, it returns with a probability when the remaining budget is not sufficient to do a trial on the selected node * . Thereby, the random source in this adaptive greedy policy indicates whether contains the selected node in the last iteration. The adaptive greedy policy ( ) shown as Algorithm 1 satisfies ( ( ), ) ≤ and E [ ( ( ( ), ))] ≤ for any realization . To make the following analysis understandable, we introduce the operations of policy truncation and policy concatenation, which are adapted from [8] but suitable on integer lattice domain. We imagine a randomized policy ( ) running over time. In each iteration, it selects node * = ( , , ) under the current seeding vector and its partial realization . It runs trial ⟨ * , ( * ) + 1⟩ for Proof. Given a fixed random source , we have ( ′ ( )@ ( ), ) = ( ′ ( ), ) ∨ ( ( ), ) = ( ( )@ ′ ( ), ) under any realization . Therefore, ( ( )) ≤ ( ′ ( )@ ( )) holds if and only if ( ( )) ≤ ( ( )@ ′ ( )). Then, we need to show ( ( )) ≤ ( ( )@ ′ ( )), which can be inferred from Lemma A.8 in [8] , thus we omit here. Take the expectation over random source , Inequality (22) can be established. □ Lemma 2. Given a seeding vector and a partial realization generated by it, (·, ) is an adaptive monotone and adaptive dr-submodular function. For any policy * ( ) that satisfies ( * ( ), ) ≤ and E [ ( ( * ( ), ))] ≤ for any realization , we have Proof. Consider the seeding vector ′ maintained by a policy ′ ( ), we can define this policy ′ ( ) as follow. The seeding vector ′ is initialized to ′ = 0 ∈ Z + . The policy ′ ( ) increases ′ ( ) from 0 to ( ) step by step for each node ∈ . It will terminate if the state of trial ⟨ , ⟩ with ≤ ( ) is different from ( ) ( ) or the state of edge ( , ) is different from (( , )). If reaching ′ = and not stopping, it will begin to run policy * ( ) like a fresh start without information from before. Here, we can imagine there is a virtual vector * associated with * ( ) updated from 0 and ′ = ∨ * under the realization ∼ . For each trial ⟨ , ⟩, we define (⟨ , ⟩) = Pr[ ≤ ( ′ ( ), ) ( )| ∼ ] as the probability that is selected by ′ ( ) and increases ′ ( ) from − 1 to . When the policy * ( ) selects a node ∈ with ( ) ≤ * ( ) < ( ), namely ⟨ , * ( ) + 1⟩ ∉ dom( ), the partial realization ′ generated by current ′ satisfies ⊆ ′ , thereby we have Δ( | ′ , ′ ) ≤ Δ( | , ) because of adaptive dr-submodularity. Thus, the total contribution to Δ( * ( )| , ) is bounded by Δ( * ( )| , ) ≤ ∈ , ( ) < ( ) ( )−1 = ( ) (⟨ , + 1⟩) · Δ( | , ). From the above, we have Since (⟨ , ⟩) ≤ (⟨ , + 1⟩), we have where Inequality (28) is correct because it only count a subset of trials contained in ( * ( ), ). Thus, this lemma is proven. □ Theorem 3. The adaptive greedy policy ( ) shown as Algorithm 1 achieves a (1 − −1 ) expected approximation guarantee. Thus, for any policy * ( ) that satisfies ( * ( ), ) ≤ and E [ ( ( * ( ), ))] ≤ for any realization , we have Proof. Consider the policy [ +1] ( ) given any ∈ [0, − 1], its current seeding vector and partial realization when it enters the last iteration before termination (line 3 of Algorithm 1) are denoted by and . In the last iteration, the node * is selected in line 4 of Algorithm 1. The expected marginal gain of the last iteration is Δ( * | , ) · ( + 1 − ( ))/ (⟨ * , ( * ) + 1⟩). Consider the policy [ ] ( ), there are two cases could happen. Here, the and are fixed, which are determined by potential realization . Take the expectation over all realizations, we have where the ( ) is the current seeding vector (partial realization) of the policy [ +1] ( ) at the beginning of its last iteration under the potential realization and the node * can be considered as the one that is able to get the maximum marginal gain based on the seed vector and its partial realizaton . Then, the definition of and are the same as above. We can define the seeding vector and its partial realization ′ as that returned by the policy [ ] ( ), where we have ⊆ ′ and ≤ . Policy According to Inequality (23) in Lemma 2, we have Now, we can define : , which means ≤ · ( − +1 ) and The proof of this theorem is completed. □ In the last section, our adaptive greedy policy shown as Algorithm 1 can achieve a (1−1/ ) expected approximation guarantee, which has been proved by Theorem 3. However, it is based on a basic assumption that we are able to compute the exact value of Δ( | , ) and get the feasible node with maximum unit marginal gain in line 4 of Algorithm 1 in each iteration. In fact, this is an impossible task because it is #P-hard [4] to compute marginal gain Δ( | , ) for each node ∈ under the IC-model. Thus, the true value of Δ( | , ) is difficult to obtain. MC simulations is a general method to estimate this value, but its running time is unacceptable. To overcome that, we are able to seek an estimator of Δ( | , ) through the reverse influence sampling (RIS) [1] then maximize this estimator. If maximizing this estimator through sampling technique, it will be possible to get a extremely worse node with some probability, even though very small. In other words, the selected node * in line 4 of Algorithm 1 is not optimal such that * ∉ arg max ∈ , ( ) < ( ) Δ( | , )/ (⟨ , ( ) + 1⟩) in actual execution. Like this, the expected approximation ratio shown in Theorem 3 will not be ensured. Consider the traditional IM problem, we need to introduce the concept of reverse reachable sets (RR-sets) first. Given a graph = ( , ), a random RR-set of can be generated by selecting a node ∈ uniformly and sampling a graph realization from G, then collecting those nodes can reach in . A RR-set rooted at is a collection of nodes that are likely to influence . A larger expected influence spread a seed set has, the higher the probability that intersects with a random RR-set is. Given a seed set and a random RR-set , we have ( ) = · Pr[ ∩ ≠ ∅]. Let R = { 1 , 2 , · · · , } be a collection of random RR-sets and ( , ) be the indicator, where ( , ) = 1 if ∩ ≠ ∅, or else ( , ) = 0. Denoted by R ( ) = =1 ( , )/ , the · R ( ) is an unbiased estimator of the expected influence spread ( ). When the |R| is large, the · R ( ) will converge to the true value ( ). Thus, how to set the value of is flexible, we need to balance between accuracy and running time carefully. For our adaptive greedy policy, its current seeding vector and partial realization at the beginning of each iteration (when entering line 3 of Algorithm 1) are denoted by and . Let ( ) = ( ( ), ( )) be the subgraph induced by all inactive nodes under the current partial realization . Here, computing Δ( | , ) is equivalent to computing · ( ) ({ }). We can note that Δ( | , ) = Algorithm 2 Sampled- AdaptiveGreedy ( , , , , , ) Input: A graph = ( , ), a function (·, ), a budget ∈ R + , a vector ∈ Z + , a cost function : × Z + → R + , and an error parameter Output: A seeding vector ∈ Z + and ( , ) Update the edge states of observed by • 's actual influence diffusion 15: Update ( ) by removing all active nodes 16: end if 17: end while 18: return , ( , ) 0 if node ∉ ( ). Thus, for a node ∈ ( ) and a random RR-sets ( ) of ( ), we can get an unbiased estimator of Δ( | , ). That is Then, we can reformulate our adaptive greedy policy through the above sampling, which is shown in Algorithm 2. It is called "sampled adaptive greedy policy" and denoted by ( , ), where the random variable indicates the random source of sampling for estimations. In each iteration, it generates a collection of random RR-sets R ( ) = { 1 ( ), 2 ( ), · · · , ( )} based on current subgraph ( ) first. Then, it select a feasible node • ∈ ( ) that maximizes · | ( )| · R ( ) ({ })/ (⟨ , ( ) + 1⟩) where ( ) < ( ) and increases ( • ) by 1. Finally, we need to observe the state of • , update this partial realization , and update the subgraph ( ). The ( , ) repeats above procedure, terminates until ( ) ≥ , or terminates with a probability. According to the current seeding vector and its partial relization at the beginning of each iteration (line 5 of Algorithm 2), we can get a subgraph ( ) and a collection of random RR-sets R ( ). Now, we define a function R ( ) ({ }| ) = · R ( ) ({ })/ (⟨ , ( ) + 1⟩), thereby the | ( )| · R ( ) ({ }| ) is an unbiased estimator of Δ( | , )/ (⟨ , ( ) +1⟩). Next, a natural question is how to determine the number of RR-sets in R ( ). The proceduce of generating enough random RR-sets of ( ) and returning the approximately optimal node • ∈ ( ) (line 7 of Algorithm 2) in each iteration is shown in Algorithm 3. It is adapted from the sampling process of EPIC in [16] , but there are several differences: (1) The seed size is fixed to one; and (2) The targeted estimator is Algorithm 3 Generalized-EPIC ( ( ), , , , ) [16] Input: A graph ( ) = ( ( ), ( )), the current seeding vector ∈ Z + , a vector ∈ Z + , a cost : × Z + → R + , and an error parameter Output: An approximately optimal node • ∈ ( ) Double the size of R 1 ( ) and R 2 ( ) with new random RR-sets 15: end for the function R ( ) ({ }| ) we defined before instead of R ( ) ({ }). Thus, the sampling process shown as algorithm 3 is called "Generalized-EPIC". From line 1 to line 5 of Algorithm 3, it initializes those parameters similar to EPIC in [16] but fixs the seed set to one, then generate two collections R 1 ( ) and R 2 ( ) of random RR-sets with the same size. In each iteration, it select the feasible node • ∈ ( ) that maximizes the estimator R 1 ( ) ({ }| ), which can be computed in polynomial time. Denoted by * the optimal feasible node that maximizes the unit marginal gain Δ( | , )/ (⟨ , ( ) + 1⟩), the ({ * }) is an uppper bound on R 1 ( ) ({ * }| ). Thus, we have Moveover, the | ( )| · ({ • }) gives an accurate lower bound on Δ( • | , )/ (⟨ • , ( • ) + 1⟩) with high probability. After that, it checks whether the stopping condition in line 11 can be satisfied. If true, it will return an approximate optimal node • definitely. Lemma 3. Given the current seeding vector and its partial realization , the feasible node • returned by Algorithm 3 achieves a (1 − ) expected approximation guarantee within ((| ( )| + | ( )|) · (log(| ( )|) + log(1/ ))/ 2 ) expected time. That is Proof. Given the current seeding vector and its partial realization , let us look at the targeted function R ( ) ({ }| ) = · R ( ) ({ })/ (⟨ , ( ) + 1⟩). It is a weighted coverage on the collection R ( ), where we can consider the / (⟨ , ( ) + 1⟩) as the weight of each node ∈ ( ). The weighted coverage function is submodular, thereby we can compute the node • ∈ arg max ∈ ( ), ( ) < ( ) R 1 ( ) ({ }| ) accurately shown as line 8 of Algorithm 3 in polynomial time. Because of its submodularity, Lemma 3 can be obtained by adapting from the expected approximation guarantee of EPIC in [16] . □ Let us look back at Algorithm 2. The actual number of activated seeds should be much less than the number of actual iterations in Algorithm 2, since there are some iterations that fail to activate its selected node. Based on that, we can make the following assumptions: (1) Generate an active seed successfully in each iteration, namely we suppose = 1 for each node ∈ . (2) The node we select in each itertaion has the lowest cost until now. (3) We sort the node set as 1⟩) . Given a graph = ( , ) and a budget , we can define the maximum number of iterations in Algorithm 2 as . That is By finding the smallest such that =1 (⟨ ′ , 1⟩) ≥ , it is obvious that the actual number of iterations in Algorithm 2 must be less than defined in Equation (41). Theorem 4. The sampled adaptive greedy policy ( , ) shown as Algorithm 2 achieved a (1 − −1+ ) expected approximation guarantee within ( · ( + ) · (log( ) + log(1/ ))/ 2 ) expected time. Thus, for any policy * ( ) that satisfies ( * ( ), ) ≤ and E [ ( ( * ( ), ))] ≤ for any realization , we have Proof. According to the above assumptions, the maximum number of iterations can be executed in Algorithm 2 is . Based on Lemma 3, the selected node in each iteartion satisfies (1 − ) expected approximation. In this extreme case, the total expected error over all iterations is = (1/ ) · =1 . Actually, the total expected error will be much less than due to the ≤ 1 for each node ∈ . Here, there is no node can be activated in many iterations. Based on Theorem 3 and Lemma 3, Theorem 4 holds by inferring from Theorem 6 in [16] . □ In this section, we carry out several experiments on different datasets to validate the performance of our proposed policy. It aims to test the efficiency of our sampled adaptive greedy policy shown as Algorithm 2 and its effectiveness compared to other adaptive heuristic policies. All of our experiments are programmed by python and run on a Windows machine with a 3.40GHz, 4 core Intel CPU and 16GB RAM. There are four datasets used in our experiments: (1) NetScience [21] : a co-authorship network, co-authorship among scientists to publish papers about network science; (2) Wiki [21] : a whovotes-on-whom network, which come from the collection Wikipedia voting; (3) HetHEPT [18] : an academic collaboration relationship on high energy physics area; and (4) Epinions [18] : a who-trust-whom online social network on Epinions.com, a general consumer review site. The statistics information of these four datasets is represented in Table 1 . For the undirected graph, each undirected edge is replaced with two reversed directed edges. The diffusion model used in our experiments relies on the IC-model. For each edge ( , ) ∈ , we set = 1/| − ( )|, which is widely used by prior works about influence maximization [17] [1] [30] [29] [19] . There are several parameters associated with the objective function of our Adaptive-IMMA problem. Here, we set the vector = {5} where each node can be attempted to activate as a seed at most 5 times; the cost of each trial (⟨ , 1⟩) = 1 and (⟨ , + 1⟩) = 1.2 × (⟨ , ⟩); and variable budget ∈ {0, 10, 20, 30, 40, 50}. Besides, for each node ∈ , its probability is sampled from a normal distribution within given a mean, variance and interval. For each adaptive policies, we generate 20 realizations (test it 20 times) randomly and take the average of their results as its final performance. We perform two experiments with different purposes in this section. The first experiment is to test the time efficiency of the adaptive greedy policy and sampled adaptive greedy policy (Algorithm 2), then validate the superiority over their non-adaptive settings. The corresponding non-adaptive versions of adaptive greedy policy and sampled adaptive greedy policy are referred to as greedy and sampled greedy algorithm respectively. Here, the greedy algorithm and adaptive greedy policy are implemented by MC simulations. They can be shown as follows: (1) Greedy algorithm: Shown as Algorithm 4, it selects a node ∈ with ( ) < such that maximizes the unit marginal gain ( ( + ) − ( ))/ (⟨ , ( ) + 1⟩) in each iteration. The selected node in the last iteration will be contained with a probability. To estimate the value of ( ), we have where we need to create a constructed graph = ( , ) by adding a new node and a new directed edge ( , ) for each node ∈ to , where ( , ) is with activation probability Here, the ( − ) can be estimated by MC simulations, which is an effective methods to estimate the value of ( ) [10] . (2) Adaptive greedy policy: Shown as Algorithm 1, we can compute the unit marginal gain can be estimated by MC simulations. (3) Sampled greedy algorithm: Here, we require to obtain an unbiased estimator of ( ). Let R be a collection of random RR-sets sampled from , we have Let R ( ) = ( − =1 ∈ (1 − ) ( ) )/ , thereby we have | | · R ( ) is an unbiased estimator of ( ). Because there is no existing algorithm to determine the number of random RR-sets in this case, we will guess a size of R according to datasets and budgets. Given a collection R, it selects a node • ∈ with ( ) < ( ) such that maximizes the unit marginal coverage ( R ( + ) − R ( ))/ (⟨ , ( ) + 1⟩) in each iteration. The selected node in the last iteration will be contained with a probability, which is similar to Algorithm 4. (4) Sampled adaptive greedy policy: It can be implemented by Algorithm 2 with the error parameter = 0.5. The second experiment is to test the performance of our sampled adaptive greedy policy compared with other heuristic adaptive policies, which aims to evaluate its effectiveness. The difference between these heuristic adaptive policies and our sampled adaptive greedy policy lies in how to select a node • from the feasible node set that satisfies ∈ ( ) and ( ) < ( ) in each iteration. Thus, the only difference is in line 6 of Algorithm 2 and other procedures are totally identical. In other words, they are obtained by replacing line 6 of Algorithm 2 with these heuristic strategies, summarized as follows: (1) Random: select a node • from the feasible node set uniformly in each iteration; (2) MaxDegree: select a node • from the feasible node set that maximizes + ( )/ (⟨ , ( ) + 1⟩) in each iteration; (3) MaxProb: select a node • from the feasible node set that maximizes / (⟨ , ( ) + 1⟩) in each iteration; and (4) MaxDegreeProb: select a node • from the feasible node set that maximizes · + ( )/ (⟨ , ( ) + 1⟩) in each iteration. Figure 2 are the experimental results of the first experiment. Figure 1 draws the expected influence spread achieved by the (sampled) greedy algorithm and (sampled) adaptive greedy policy under the NetScience and Wiki datasets. Here, the probability ∼ ( , ) means for each node ∈ is sampled from a truncated normal distribution whose mean is and variance is within the interval [0, 1]. Because the greedy algorithm and adaptive greedy policy are implemented by MC simulations, and its time complexity is too high, thereby we only use these two small graphs to test them in this experiment. Here, the number of MC simulations for each estimation is set to 300 in NetScience dataset and 600 in Wiki dataset. This is far from enough, just for performance comparison. For the sampled greedy algorithm, the number of random RR-sets is determined based on experience, where we give |R| = 5000 + 1000 · ( /10) in NetScience dataset and |R| = 10000 + 2000 · ( /10) in Wiki dataset. We note that the expected influence spread obtained by the adaptive greedy policy and sampled adaptive greedy policy is very close, which proves the effectiveness of our sampling techniques. Under the non-adaptive settings, the performance achieved by the sampled greedy algorithm is better than that achieved by the greedy algorithm. This may be because the number of MC simulations we set for each estimation is not enough to get a precise estimation. Thus, we are more inclined to think the results obtained by the sampled greedy algorithm are more precise. Compare the performances shown as Figure 1 , we find that the sampled adaptive greedy policy has an obvious advantage, which is much better than the sampled greedy algorithm. This illustrates the effectiveness of our proposed adaptive policy from one aspect. Besides, with the increase of the mean of , there is no doubt the expected influence spread will increase. However, we observe an interesting phenomenon where the gap between the performance under the adaptive settings and non-adaptive settings seems to be shrinking. This is because the uncertainty of nodes, whether to be an active seed or not, decreases as the mean of increases, thereby reducing the advantage of our adaptive policies. Figure 2 draws the running time achieved by the (sampled) greedy algorithm and (sampled) adaptive greedy policy under the NetScience and Wiki datasets. Here, in order to compare the running time of different strategies, we do not use parallel acceleration in our implementations. We note that the running time of the sampled adaptive greedy policy is smaller than that of the sampled greedy algorithm, which is counter-intuitive. This looks unreasonable because the sampled greedy algorithm only needs to generate a collection of RR-sets once and selects seed nodes in one batch, but the sampled adaptive greedy policy has to generate a new collection of RR-sets in each iteration. Why does it happen? First, the estimator of ( ) shown as Equation (44) is more complicated than the estimator of Δ( | , ) shown as Equation (38). Second, the number of RR-sets we give in the sampled greedy algorithm may be too much, which exceeds actual needs. At last, the sampling process will be faster and faster as the graph gets smaller in the sampled adaptive greedy policy. Then, we can see that the running time of the sampled adaptive greedy policy is less than that of the adaptive greedy policy even though the number of MC simulations is far from enough, which proves the efficiency of our sampling techniques. Compare to the running times achieved by the adaptive greedy policy, the greedy algorithm is very inefficient, nearly 10 times slower than the adaptive greedy policy. There are two reasons to explain this phenomenon. First, the graph that the adaptive greedy policy relies on is shrinking gradually as the number of iterations increases. Secondly, the process of reverse breadth-first search in MC simulations will be more time-consuming when the seed set is large. Figure 3 draws the performance comparisons between our sampled adaptive greedy policy and other heuristic adaptive policies under the four datasets. We can see that the expected influence spread of any adaptive policy increases with budget because attempting to select more seed results in a larger influence spread. The expected influence spread returned by our sampled adaptive greedy policy outperforms all other heuristic adaptive policies under any dataset, thereby its performance is the best undoubtedly. This illustrates the effectiveness of our proposed policy from another aspect. Among these heuristic adaptive policies, the adaptive maxDegreeProb policy has the largest expected influence spread, because it considers the node's degree and probability to be a seed comprehensively. The performance of other policies is unstable on different datasets. We can observe that the sampled adaptive greedy policy can obtain at least 10% gain of the expected influence spread than the best heuristic adaptive policy. However, the gap between the sampled adaptive greedy policy and other heuristic adaptive policies can be affected by the dataset itself, since there are different topologies and graph realizations associated with different networks. In this paper, we have studied a variant of adaptive influence maximization, where the seed node we select may be unwilling to be the influencer and we can activate her many times. Because its objective function is defined on integer lattice, we propose the concepts of adaptive monotonicity on integer lattice and adaptive dr-submodularity firstly. Then, we summarize the properties of this problem and give a strict theoretical analysis about the approximation ratio of the adaptive greedy policy. Our approach can be used as a flexible framework to address adaptive monotone and dr-submodular function under the expected knapsack constraint. Combine with the-state-of-art EPIC algorithms, the sampled adaptive greedy policy is formulated, which reduces its running time significantly without losing the approximation guarantee. Eventually, we evaluate our proposed policies on four real networks and validate the effectiveness and efficiency comparing to their corresponding non-adaptive algorithms and other heuristic adaptive policies. Maximizing social influence in nearly optimal time Influence maximization in social networks when negative opinions may emerge and propagate Robust influence maximization Scalable influence maximization for prevalent viral marketing in large-scale social networks Scalable lattice influence maximization Scalable influence maximization in social networks under the linear threshold model Mining the network value of customers Adaptive submodularity: Theory and applications in active learning and stochastic optimization Submodular function maximization on the bounded integer lattice Continuous Activity Maximization in Online Social Networks A novel scene of viral marketing for complementary products Influence Maximization: Seeding Based on Community Structure 2020. A k-hop collaborate game model: Adaptive strategy to maximize total revenue Efficient algorithms for adaptive influence maximization Adaptive Budget Allocation for Maximizing Influence of Advertisements Efficient Approximation Algorithms for Adaptive Influence Maximization Maximizing the spread of influence through a social network SNAP Datasets: Stanford Large Network Dataset Collection Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks Mining knowledge-sharing sites for viral marketing The Network Data Repository with Interactive Graph Analytics and Visualization A generalization of submodular cover via the diminishing return property on the integer lattice Non-monotone dr-submodular function maximization Maximizing monotone submodular functions over the integer lattice Multi-round influence maximization Efficient approximation algorithms for adaptive seed minimization Online processing algorithms for influence maximization Influence maximization with partial feedback Influence maximization in near-linear time: A martingale approach Influence maximization: Near-optimal time complexity meets practical efficiency On Adaptive Influence Maximization under General Feedback Models No time to observe: adaptive influence maximization with partial feedback This work is partly supported by National Science Foundation under grant 1747818 and 1907472.