Adaptive seeding for profit maximization in social networks

Abstract

Social networks are becoming important dissemination platforms, and a large body of works have been performed on viral marketing, but most are to maximize the benefits associated with the number of active nodes. In this paper, we study the benefits related to interactions among activated nodes. Furthermore, since the stochasticity caused by the dynamics of influence cascade in the social network, we propose the adaptive seeding strategy where seeds are selected one by one according to influence propagation situation of seeds already selected, and define the adaptive profit maximization problem. We analyze its complexity and prove it is not adaptive submodular. We find the upper and lower bounds which are adaptive submodular and design an adaptive sandwich policy based on the sandwich strategy which could gain a data dependent approximation solution. Through real data sets, we verify the effectiveness of our proposed algorithm.

1 Introduction

With the advancements in information science in the last two decades, social networks find important applications in viral marketing, where a few individuals are provided with free products, hoping that the product will be recursively recommended by each individual to his friends to create a large cascade of further adoptions. Kempe et al. [14] first formulate it as the influence maximization problem on independent cascade (IC) model and linear threshold (LT) model. After that, a large body of works have been performed on viral marketing to maximize the benefits associated with the number of active nodes.

In this paper, we study the benefits related to strength of interactions among activated nodes. For example, when multiple people participate in one game, a large amount of data are transferred to synchronize the settings of game environment and operations between players [27]. Network provider generally charges based on the amount of data used by customers. In addition, interaction behaviors between game players may bring some advertising revenues to the network provider [25]. We consider the scenario of gaming on console like Nintendo switch, which provides online play mode. Players can find online opponents and play, in this case, the interaction determines the game company profit. Let’s take the game “overcooked 2” as an example, when playing online mode, 2 or 4 players can join one game, they can select a new released level to play together, that level is not free if played locally. Thus the online gaming is actually a live advertisement of the game depending on the interaction. Affected by the advertisement, players may later buy the new levels and play locally. We use profit to represent the revenues related to the strength of interactions between players and define a profit maximization problem, which selecting a seed set to maximize the profits between activated nodes.

Furthermore, one must deal with the stochasticity caused by the dynamics of influence cascade [24]. Specifically, when a seed is selected, how the influence propagates and how many nodes it will eventually affect is uncertain. In such settings, the outcome of a seed is not known in advance and will only be discovered after it is selected.

Motivated by the above observations, we aim to consider adaptive strategies to address the profit maximization problem. We pick a node, get to see which nodes it influenced and the profit among them, then adaptively pick the next node based on these observations and so on. Note that when picking the next node, we take into account the current profits of influenced nodes. To this end, we formulate adaptive profit maximization problem (APMP) in this work.

Solving such stochastic optimization problems is a notoriously difficult challenge. However, Golovin et al. [10] introduce the concept of adaptive submodularity and prove that if the problem satisfies this property, the adaptive greedy policy can achieve a $1-1/e$ approximate solution to the optimal policy. But unfortunately, our adaptive profit maximization problem is not adaptive submodular, thus the greedy strategy cannot obtain a guaranteed approximate solution. To solve this problem, we find the upper and lower bounds of the objective function both of which are adaptive submodular, and then use the sandwich strategy [16] to design an adaptive sandwich policy, which can obtain a data-dependent approximate solution.

The contributions of this paper are summarized as follows.

• We propose a new problem named adaptive profit maximization problem, analyze its complexity and prove it is not adaptive submodular.

• We find the upper and lower bounds of APMP and prove both of them are adaptive submodular.

• Based on the upper and lower bound, we design an adaptive sandwich policy for APMP using the sandwich strategy and get a data dependent approximate solution.

• Through real data sets, we verify the effectiveness of our proposed algorithms.

To the best of our knowledge, this is the first paper applying the sandwich strategy to the stochastic optimization problem which is not adaptive submodular.

The rest of the paper is organized as follows. Section 2 is devoted to the related work. The profit maximization problem is proposed in Sect. 3. The preliminaries about stochastic optimization and adaptive profit maximization problem are provided in Sect. 4. The upper bound and lower bound are presented in Sect. 5. In Sect. 6 we propose the adaptive sandwich policy. The experiments are presented in Sect. 7.

2 Related work

Kempe et al. [14] formulate the influence maximization problem under IC and LT models and provide a greedy algorithm with an approximation ratio. Since the problem is submodular a simple greedy algorithm gain an approximation ratio of $1-1/e$ [9, 17]. Since then, considerable work [3, 4, 16, 18, 19, 21, 22, 22, 23] has been devoted to extending existing models to study influence maximization and its variants. Recently, Wang et al. [26] study the activity maximization problem to maximize the sum of activity strengths among the influenced users.

Our work is related to [26] but we are different from it in the following aspects. First, the optimization problem we addressed in this paper is adaptive profit maximization problem which is different from the normal activity maximization. Our optimization strategy is selecting seeds one by one according to current observations while activity maximization is to choose a seed set in one step. Second, the property of our problem is totally different from [26] as we prove our problem is adaptive non-submodular while the problem in [26] is non-submodular. And we prove the upper and lower bounds are adaptive submodular respectively while they prove they are submodular. Third, to solve the adaptive non-submodular problem in our paper, we try to apply the sandwich algorithm to solve the adaptive non-submodular problem and successfully prove it could get a data dependent approximation solution. This is the first method to solve the adaptive non-submodular problem. Actually, we successfully apply the sandwich algorithm to the adaptive non-submodular problem like Golovin and Krause in [10] apply the greedy algorithm to adaptive submodular problem which is a meaningful work.

The adaptive strategy is a stochastic optimization framework. Asadpour et al. [1] present the preliminary results of stochastic submodular maximization problem with respect to a cardinality constraint. Golovin and Krause [10] define the concept of adaptive submodularity, generalizing submodular set functions to adaptive policies, and propose a greedy adaptive algorithm with an approximation ratio. After their initial works, algorithms for stochastic maximization problems with adaptive submodular functions have been studied in [7, 8, 11]. Other applications of adaptive submodularity in artificial intelligence are shown in [5, 6, 15].

Most of them are to address the adaptive submodular problem and apply the greedy framework. There is no work to solve the adaptive non-submodular problem. To the best of our knowledge, our paper has been the first work that tries to solve the adaptive non-submodular problem since the definition of adaptive submodular is proposed by Golovin and Krause in [10].

For the application of stochastic optimization in social networks, Seeman and Singer [20] consider the adaptive approach to a variant influence maximization problem, and Horel and Singer [13] consider the strategies with two seeding steps. Hatano et al. [12] study adaptive budget allocation problem. Tong et al. [24] introduce the adaptive seeding strategy based on a dynamic independent cascade model. Yuan and Tang [28] study the influence maximization discount allocation problem.

3 Non-adaptive profit maximization problem

In this section, we first propose the non-adaptive profit maximization problem in IC model.

In IC model each node has two states, active and inactive. Every edge (u, v) is assigned with a probability $p_{uv}$ so that when u is active, v is activated by u with probability $p_{uv}$. And the profit between nodes is represented by a nonnegative function $c: V\times V\rightarrow \mathbb {R}_{\ge 0}$, in which $c(u,v)=c(v,u)$ for the unordered pair $\{u, v\}$ of node u and v. For any seed set S, denote by I(S) the set of all active nodes at end of the diffusion process. We denote the P(A) as the collection of subsets of set A whose cardinality is two. For example, if $A=\{1,2,3\}$, then $P(A)=\{\{1,2\},\{1,3\},\{2,3\}\}$. Actually the set P consists of all the pairs of nodes in set A. The expected profit would be defined as

$$\begin{aligned} f(S) = {\mathbb {E}}\left[ \sum _{\{u,v\}\in P( I(S))}c(u,v)\right] \end{aligned}$$

(1)

Note that for each unordered pair $\{u, v\}$, we only compute once the profit between them denoted as c(u, v) or c(v, u).

Definition 1

Non-Adaptive Profit Maximization: Given a social network $G=(V,E)$ under the IC model, a profit function $c:V\times V \rightarrow \mathbb {R}_{\ge 0}$, and a positive integer k, find a set S of k seeds to maximize the expected profit between activated nodes by S through influence propagation:

$$\begin{aligned} \max f(S) \end{aligned}$$

(2)

$$\begin{aligned} s.t. |S|\le k \end{aligned}$$

(3)

Theorem 1

Non-adaptive profit maximization problem is NP-hard.

Proof

We prove it by reducing from the activity maximization problem proposed by Wang et al. [26] which is NP-hard. Note that they only consider the activity between active nodes which are connected by edges. But we consider the benefits among all active nodes, regardless of whether there is an edge connecting them. To this end, our non-adaptive profit maximization problem can be viewed as a significant extension of activity maximization problem. In order to make an obvious comparison with our problem, we give an equivalent formulation about it: given a social network $G=(V,E)$ with the IC model, each edge $(u,v)\in E$ is associated with an activity strength $A_{u,v}$ and a propagation probability $B_{u,v}$, the activity of a given seed set S is defined as

$$\begin{aligned} \delta _{A}(S) = {\mathbb {E}}\left[ \sum _{(u,v)\in E,\{u,v\}\subseteq I(S)}A_{u,v}\right] \end{aligned}$$

The activity maximization problem can be stated as follows:

$$\begin{aligned} \max \delta _{A}(S) \end{aligned}$$

(4)

$$\begin{aligned} s.t. |S|\le k \end{aligned}$$

(5)

$\square$

Remark 1

The activity maximization problem is polynomial time reducible to the non-adaptive profit maximization problem. Given an instance of activity maximization problem, we construct a corresponding graph which has the same network topology and the propagation probability. And we construct the profit function for profit maximization problem as follows. For each pair of nodes $\{u,v\}$ between which there are edges, we set the profit value on unordered pair $\{u, v\}$ to be the sum of activity strength $A_{u,v}$ and $A_{v,u}$. For the pair of nodes $\{u,v\}$ between which there are no edges, we set the profit value on unordered pair $\{u, v\}$ to be 0. Therefore, the activity maximization problem is equivalent to solve the non-adaptive profit maximization problem.

According to Remark1 and Theorem 1 in [26] which says activity maximization problem is NP-hard, the theorem follows immediately. $\square$

Theorem 2

Give a seed S, computing the exact game profit f(S) is $\sharp P$-hard.

Proof

According to Remark1 and Theorem 2 in [26] which says computing the exact activity $\delta _A(S)$ under IC model given a seed set S is $\sharp P$-hard, the theorem follows immediately.$\square$

4 Adaptive profit maximization problem

In this section, we propose the adaptive seeding strategy for profit maximization problem, where seeds are selected one by one according to influence propagation situation of seeds already selected.

4.1 Preliminaries

We employ the following concepts to formulate our problem.

Definition 2

Realization and Partial realization: Each node $v\in V$ is in a particular state from a set O of possible states. A realization is a function $\phi : V \rightarrow O$, representing the states of nodes. And $\phi (v)$ is the state of v. We use $\varPhi$ to denote a random realization. A partial realization $\psi : H \rightarrow O , H \subseteq V$, is a function from some subset H of V to their states. It is actually a set of relations, so that $\psi \subseteq V \times O$ equals $\{(v,o): \psi (v) = o\}$. We use the notation $dom (\psi ) =\{ v: (v,o) \in \psi \}$ to refer to the domain of $\psi$. A partial realization $\psi$ is consistent with a realization $\phi$ if they are equal everywhere in the domain of $\psi$. In this case, we write $\phi \sim \psi$. We say $\psi$ is a subrealization of $\psi '$ if and only if $\psi \subseteq \psi '$.

In social networks, when a node is selected, its state corresponds to the diffusion of influence other than the state of itself, active or inactive. Specifically, we model $\phi (u)$ as a function $\phi _{u} : E \rightarrow \{0,1,?\}$, where $\phi _{u}((u,v))=0$ means that activating u has revealed that the edge (u, v) is dead; $\phi _{u}((u,v))=1$ means the edge (u, v) is live, and $\phi _{u}((u,v))= ?$ means the status of (u, v) is unknown. We require each realization to be consistent and complete. Consistency means that no edge should be declared both live and dead by any two states of nodes. That is, for all $u,v \in V$ and $e \in E$, $(\phi _{u}(e),\phi _{v}(e))\notin \{(1,0),(0,1)\}$. Completeness means that the status of each edge is revealed by some activation. Let $E(\phi )$ denote the live edges as encoded by $\phi$.

Note that the realization $\phi$ represent the state of each node according to its definition, and in the social network it actually revealed the state of each edge. But these two expressions are not contradictory since we model $\phi (u)$ as a function $\phi _{u} : E \rightarrow \{0,1,?\}$. In different contexts, we will alternate between the two representations as needed, if there is no confusion.

Definition 3

The Full-Adoption Feedback Model: After activating seed u, we get to see the status (live or dead) of all edges existing v, for all nodes v reachable from u via live edges(i.e., reachable from u in $(V,E(\phi ))$), where $\phi$ is the true realization.

Definition 4

Adaptive policy: We encode our adaptive strategy for picking seeds as a policy $\pi$ which is a function from a set of partial realizations to V, specifying which node to pick next under a particular set of observations.

4.2 Adaptive profit maximization problem

For the adaptive stochastic settings of profit maximization problem in the full adoption feedback model, we pick a node, get to see which nodes it influenced and compute the profit between them which is called the current observations. And when picking the next node, we need to take into account the current profits of influenced nodes. In other words, making a decision based on these observations and so on. We define the profit function as follows

$$\begin{aligned} f(S,\phi ) = \sum _{\{u,v\}\in P( I(S, \phi ))}c(u,v) \end{aligned}$$

(6)

where $\phi$ is a realization which encode the states of each node selected (i.e., actually reveals the states of all edges, live or dead), $I(S,\phi )$ is nodes activated by seed set S under realization $\phi$, $P(I(S,\phi ))$ is the all pairs of nodes in $I(S,\phi )$. $N(\pi ,\phi )$ is the seeds selected by policy $\pi$ under realization $\phi$. Based on this notation, the expected profit of a policy $\pi$ is

$$\begin{aligned} f_{\text{ avg }} (\pi )= \mathbb {E}[f(N(\pi ,\varPhi ), \varPhi )] \end{aligned}$$

(7)

where the expectation is taken with respect to $p(\phi )$.

Definition 5

(Adaptive Profit Maximization Problem, APMP) Given a social network $G=(V,E)$ under the full feedback model, a profit function $c:V\times V \rightarrow \mathbb {R}_{\ge 0}$, and a positive integer k, find a policy $\pi ^*$ to maximize the expected profit between nodes activated through influence propagation:

$$\begin{aligned} \max f_{\text{ avg } }(\pi ) \end{aligned}$$

(8)

$$\begin{aligned} s.t. | N(\pi ,\phi ) | \le k \text{ for } \text{ all } \phi \end{aligned}$$

(9)

Remark 2

Let us first consider the very special case of adaptive profit maximization where the distribution $p(\phi )$ is deterministic. Note that, we model $\phi (i)$ as a function $\phi _{i} : E \rightarrow \{0,1,?\}$. Because of completeness of the realization $\phi$, the state of each edge is revealed, live or dead. And no edge is declared to be both live and dead by any two states of nodes, since the property of consistency. Through the above analysis, a deterministic realization corresponds to a live edge graph [14]which is obtained from live edges $E(\phi )$ under realization $\phi$ and all nodes. In this case, the realization $\phi$ is known to the decision maker in advance, and thus there is no benefit in adaptive selection and the policies are non-adaptive. So when the distribution is deterministic, the APMP is transferred to the following problem: given a live graph $G(V,E(\phi ))$ (i.e. given the realization $\phi$), where each edge(u, v) in $E(\phi )$ is live, find a seed set S that max the profit of influenced nodes:

$$\begin{aligned} \max f(S,\phi ) \end{aligned}$$

(10)

$$\begin{aligned} s.t. |S|\le k \end{aligned}$$

(11)

Our research work is mainly based on the theory of adaptive submodularity which is the first proposed by [10], the specific concepts associated with it are as follows

Definition 6

Conditional Expected Marginal Benefit: Given a partial realization $\psi$ and node v, the conditional expected marginal benefit of v conditioned on having observed $\psi$, denoted $\triangle (v \mid \psi )$, is

$$\begin{aligned} \triangle (v\mid \psi ) := \mathbb {E}[f(dom(\psi ) \cup {v}, \varPhi ) - f(dom(\psi ), \varPhi ) \mid \varPhi \sim \psi ] \end{aligned}$$

(12)

Definition 7

Adaptive Monotonicity: A function $f : 2^{V} \times O^{V} \rightarrow \mathbb {R}_{\ge 0}$ is adaptive monotone with respect to distribution $p(\phi )$ if the conditional expected marginal benefit of any item is nonnegative, i.e., for all $\psi$ with $\mathbb {P}[\varPhi \sim \psi ] > 0$ and all $v\in V$ we have

$$\begin{aligned} \triangle (v\mid \psi ) \ge 0. \end{aligned}$$

(13)

Definition 8

Adaptive Submodularity: A function $f : 2^{V} \times O^{V} \rightarrow \mathbb {R}_{\ge 0}$ is adaptive submodular with respect to distribution $p(\phi )$ if the conditional expected marginal benefit of any fixed item does not increase as more items are selected and their states are observed. Formally, f is adaptive submodular w.r.t. $p(\phi )$ if for all $\psi$ and $\psi '$ such that $\psi$ is a subrealization of $\psi '$ (i.e., $\psi \subseteq \psi '$), and for all $v\in V\setminus dom(\psi ')$, we have

$$\begin{aligned} \triangle (v\mid \psi ) \ge \triangle (v\mid \psi '). \end{aligned}$$

(14)

Theorem 3

$f(S,\phi )$ is not adaptive submodular under full adoption feedback model.

Proof

We prove it by a special case proposed by Remark 2. Actually, when the distribution is deterministic, the diminishing returns property of adaptive submodularity reduces to the classical characterization of submodular set functions. So we construct a live graph as shown in Fig. 1. Note that each edge in the figure is bidirectional, and the first number in the tuple attached to each edge represents the propagation probability, the second number is the profit between its two endpoints. For example in Fig. 1, the tuple (0, 1) on edge $(v_{1},v_{2})$ means propagation probability $p(v_{1},v_{2})= p(v_{2},v_{1})=0$ and $c(v_{1},v_{2})=1$. And for the vertices between which there is no edge we set $c(v_{i},v_{j})=0$. Then we have $f(\{v_{1}\})=0$, $f(\{v_{1}, v_{4}\})=1$, $f(\{v_{1}, v_{2}\})=1$ and $f(\{v_{1}, v_{2},v_{4}\})=3$. Thus, $f(\{v_{1}, v_{4}\})-f(\{v_{1}\})<f(\{v_{1}, v_{2},v_{4}\})-f(\{v_{1}, v_{2}\})$, which implies $f(\cdot )$ is not submodular. $\square$

Fig. 1

Counter example

Theorem 4

Adaptive profit maximization problem is NP-hard.

Proof

We prove APMP is NP-hard by showing a special case of it is NP-hard, where $p(\phi )$ is deterministic as proposed by Remark 2. Now we prove by reducing from the set cover problem, which is NP-complete. Given a ground set $U = \{ u_{1}, u_{2},\dots , u_{n}\}$ and a collection of sets $\{S_{1}, S_{2}, \dots ,S_{m}\}$ whose union equals the ground set, the set cover problem is to decide if there exist k sets in S so that the union equals U. Given an instance of the set cover problem, we construct a corresponding live graph with $m +2n$ nodes as follows. For each set $S_{i}$ we create one node $p_{i}$, and for each element $u_{j}$ we create two nodes $q_{j}$ and $q'_{j}$. If the $S_{i}$ contains the element $u_{j}$, then we create two edges $(p_{i},q_{j})$ and $(p_{i},q'_{j})$. Note that each edge is live. Now we create the profit function over pairs of nodes. For the pairs $\{q_{j},q'_{j}\}$, the profit equals to 1, and the other pairs equal to 0. Then the set cover problem is equivalent to deciding if there is a set S of k nodes such that the profit of S equals to n. The deterministic case of Adaptive profit maximization problem is NP-hard follows immediately and so is the theorem. $\square$

Through above analysis, we find that the problem APMP is not adaptive submodular and hard to solve. There is no general way to optimize or approximate a non-adaptive submodular function.

5 Adaptive submodular upper bound and lower bound

In this section, we propose an upper and a lower bound of the original problem APMP, and we prove that both of them are adaptive submodular. Thus, the adaptive greedy policy can achieve a $1-1/e$ approximate solution to the expected reward of the best policy according to [10].

5.1 Upper bound

Under realization $\phi$, the upper bound equals to the profit between nodes both of which are active plus half of the profit between nodes which are active and nodes which are not active. The former is exactly the profit we want to compute. And it can be defined as

$$\begin{aligned} U(S,\phi )&=\sum _{\{u,v\}\in P(I(S,\phi ))} c(u,v)+\frac{1}{2}\sum _{u\in I(S,\phi ),v\in V\setminus I(S,\phi )}c(u,v) \nonumber \\&=\sum _{v\in I(S,\phi )}w(v) \end{aligned}$$

(15)

where $I(S,\phi )$ denotes the set of all active nodes under the realization $\phi$, when S is the seed set and

$$\begin{aligned} w(v)=\frac{1}{2}\sum _{u\in V}c(v,u) \end{aligned}$$

(16)

Thus, we can see that the upper bound is essentially a weighted version of influence spread, where the weight of node v is $\frac{1}{2}\sum _{u\in V}c(v,u)$, which equals to half of the sum of profit between v and the other nodes in V.

Lemma 1

Under any fixed realization $\phi$, $U(S,\phi )$ is monotone and submodular.

Proof

Given a fixed realization $\phi$ which means the state of all the edges are determined according to Remark 2, we just need to prove $U(S,\phi )$ is monotone and submodular in a live graph. Since the profit function $c: V\times V \rightarrow \mathbb {R}_{\ge 0}$ is nonnegative which means the profit of each pair of nodes is non-negative. Thus the weight of every node is non-negative and the monotonicity of $U(S,\phi )$ follows immediately. For the submodularity, we need prove $U(A\cup \{v\}) -U(A) \ge U(B \cup \{v\}) -U(B)$, such that $A \subseteq B \subseteq V$ and $v\in V\setminus B$. It is the second equivalent definitions of submodularity as shown in Theorem 1 of work [9]. The left side of inequality is the weight of nodes which can be activated by v but can not by A. The right side is the weight of nodes which can be activated by v but can not by B. We have $I(v) -I(A) \supseteq I(v) - I(B)$, since $A \subseteq B$. And the submodularity follows immediately. $\square$

Lemma 2

If we have $U(S,\phi ) = f(I(S,\phi ))$, where $I(S,\phi )$ denotes the set of all activated nodes when S is the seed set selected under the realization $\phi$, then $f: 2^V \rightarrow \mathbb {R}_{\ge 0}$ is a monotone submodular function indicating the profit of influenced nodes set .

Proof

Since $U(S,\phi )=\sum _{v\in I(S,\phi )}w(v)$, and $U(S,\phi ) = f(I(S,\phi ))$, we have $f(I(S,\phi )) =\sum _{v\in I(S,\phi )}w(v)$. Since w(v) is a constant for each node v, apparently $f: 2^V \rightarrow \mathbb {R}_{\ge 0}$ is linear function. And for each node v, its weight $w(v) \ge 0$. So $f: 2^V \rightarrow \mathbb {R}_{\ge 0}$ is an monotone submodular function indicating the profit for influencing a set. $\square$

Lemma 3

In the full-adoption feedback model, given realizations $\phi$ and $\phi '$, and a node $v\in V$, if $\phi (v) = \phi '(v)$, then $I(v, \phi ) = I(v,\phi ')$.

Proof

It means that if the states of a seed v are the same under different realizations, then the nodes that can be activated by it are the same too. For any node $w \in I(v, \phi )$, there is a live path from v to w under realization $\phi$. According to the definition of realization, we know that the node v reveals a set of edges denoted as A to be dead or live under realization $\phi$ and $\phi '$. And for any edge $(i,j)\in A$, $\phi _{v}(i,j) =\phi '_{v}(i,j)$ since $\phi (v) = \phi '(v)$, which means the node v revealed edge (i, j) to the same state under realization $\phi$ and $\phi '$ respectively. So if there a live path from v to w under realization $\phi$, then there a live path from v to w under realization $\phi '$ too. It follows that $w \in I(v, \phi ')$ and vice versa. $\square$

Lemma 4

In the full-adoption feedback model, given realizations $\phi$ and partial realization $\psi$, such that $\phi \sim \psi$ , then $I(dom(\psi ), \phi ) = \cup _{x\in dom(\psi )} I(x, \phi )$

Proof

Since the realization is complete according to the definition of it, the state of every edge in social network is deterministic which means we get a live graph under the realization $\phi$. Apparently, in a live graph the influence spread of nodes set $dom(\psi )$ equals to the union of influenced spread of node in $dom(\psi )$. The lemma follows immediately. $\square$

Lemma 5

In the full-adoption feedback model, given realizations $\phi$ and $\phi '$, and partial realization $\psi$ and $\psi '$, such that $\phi \sim \psi$, $\phi ' \sim \psi '$, and $\psi$ is subrealization of $\psi '$ , then $I(dom(\psi ), \phi ) = I(dom(\psi ),\phi ')$.

Proof

Since $\psi$ is subrealization of $\psi '$, we know that $\psi \subseteq \psi '$ which means that $\psi (x) =\psi '(x)$ for all $x \in dom(\psi )$. Then we get $\phi (x) = \phi '(x)$, for $x \in dom(\psi )$, since the consistency of realization and the given fact $\phi \sim \psi$, $\phi ' \sim \psi '$. And based on Lemma 3, we have $I(x, \phi ) = I(x,\phi ')$, for $x \in dom(\psi )$. And we have $I(dom(\psi ), \phi ) = \cup _{x\in dom(\psi )} I(x, \phi )$, $I(dom(\psi ), \phi ' ) = \cup _{x\in dom(\psi )} I(x, \phi ')$ according to Lemma 4. Then the lemma follows immediately. $\square$

Theorem 5

$U(S,\phi )$ is adaptive monotone and submodular.

Proof

Since $U(\cdot , \phi )$ is monotonic for each fixed $\phi$ according to Lemma 1, adaptive monotonicity is readily proved.

Moving on to adaptive submodularity, we first define a coupled distribution $\theta (\phi , \phi ')$ over pairs of realizations $\phi \thicksim \psi$ and $\phi ' \thicksim \phi '$ using the technique proposed by [10]. We denote the state of edge (u, v) as $X_{uw}$, for $(u,v)\in E$. Then a realization can be represented by a random variable $\mathbf{X} = \{X_{uw} : (u,w) \in E\}$. Then $\theta (\phi ,\phi ')$ can be defined implicitly in terms of a joint distribution $\hat{\theta }$ on $\mathbf{X} \times \mathbf{X} '$, where $\theta = \theta (\mathbf{X} )$ and $\theta ' = \theta '(\mathbf{X} ')$ are the realizations induced by the two sets of edge statuses, respectively. Hence $\theta (\phi , \phi ') = \hat{\theta }(\mathbf{X} ,\mathbf{X} ')$. There are two constraints we need to consider in constructing $\hat{\theta }$. First, the status of all edges which are revealed by $\psi$ are the same since $\psi \subseteq \psi '$. Second, the status of all edges which are unobserved by both $\psi$ and $\psi '$ are the same in $\mathbf{X}$ and $\mathbf{X} '$, meaning $X_{uw} = X'_{uw}$ for all such edges (u, w). The bove constraints leave us with the following degrees of freedom: we may select $X_{uw}$ for all $(u,w) \in E$ which are unobserved by $\psi$.

Hence for all $(\mathbf{X} ,\mathbf{X} ')$ satisfying the above two constraints, we have

$$\begin{aligned} \hat{\theta }(\mathbf{X} ,\mathbf{X} ') = \prod _{(u,w) \text{ unobserved } \text{ by } \psi } p_{uw}^{X_{uw}}(1-p_{uw})^{1-X_{uw}} \end{aligned}$$

and otherwise $\hat{\theta }(\mathbf{X} ,\mathbf{X} ')= 0$. Note that $p(\phi \mid \psi )=\varSigma _{\phi '}\theta (\phi ,\phi ')$ and $p(\phi '\mid \psi ') = \varSigma _{\phi } \theta (\phi ,\phi ').$ And all $(\mathbf{X} ,\mathbf{X} ') \in \text{ support } (\hat{\theta })$ satisfy the two constraints. We next claim that for all $(\phi ,\phi ')\in \text{ support }(\theta )$,

$$\begin{aligned}&U(dom(\psi ')\cup \{v\},\phi ') - U(dom(\psi '),\phi ')\nonumber \\&\quad \le U(dom(\psi )\cup \{v\}, \phi ) - U(dom(\psi ),\phi ). \end{aligned}$$

(17)

Recall $U(S,\phi ) =f(I(S,\phi ))$ proposed in Lemma 2, where $I (S,\phi )$ is the set of all activated nodes when S is the seed set of activated nodes and $\phi$ is the realization. Let $B := I(dom(\psi ),\phi )$ and $C := I(dom(\psi )\cup \{v\}, \phi )$ denote the active nodes before and after selecting v after $dom(\psi )$ under realization $\phi$, and similarly define $B' := I(dom(\psi '),\phi ')$ and $C' := I(dom(\psi ')\cup \{v\}, \phi ' )$ with respect to $\psi '$ and $\psi '$. Let $D := C\backslash B$, $D':= C'\backslash B'$. Then Eq. 17 is equivalent to

$$\begin{aligned} f(B'\cup D') - f(B') \le f(B\cup D) -f(B) \end{aligned}$$

(18)

According to Lemma 2, we know that $f: 2^V \rightarrow \mathbb {R}_{\ge 0}$ is a monotone submodular function. So it suffices to show that $B\subseteq B'$ and $D' \subseteq D$ to prove the above inequality, which we will now do.

We first prove $B \subseteq B'$. Since $(\phi ,\phi ') \in \text{ support } (\theta )$, this implies that $\psi \subseteq \psi '$ and $dom(\psi ) \subseteq dom(\psi ')$. We denote the set $H = dom(\psi ') -dom(\psi )$. Then $B' = I(dom(\psi '),\phi ') = I(dom(\psi )\cup H,\phi ') = I(dom(\psi ),\phi ') \cup I(H,\phi ')$ according Lemma 4. And $B = I(dom(\psi ),\phi ) = I(dom(\psi ),\phi ' )$ according Lemma 5, so we have $B \subseteq B'$.

Next we show $D' \subseteq D$. According to Lemma 4, we have $D = C - B = I(dom(\psi )\cup \{v\}, \phi ) - I(dom(\psi ),\phi ) = I(v, \phi ) - I(dom(\psi ),\phi )$, and $D' = C' - B' = I(dom(\psi ')\cup \{v\}, \phi ' ) - I(dom(\psi ' ),\phi ' ) = I(v, \phi ' ) - I(dom(\psi ' ),\phi ' )$. We have $\phi (v) = \phi '(v)$ since $(\phi ,\phi ')\in \text{ support }(\theta )$, and then $I(v, \phi ) = I(v, \phi ' )$ according to Lemma 3. And we know that $I(dom(\psi ),\phi ) \subseteq I(dom(\psi ' ),\phi ' )$ which has been proved above(i.e., $B \subseteq B'$), then we have $D' \subseteq D$.

Having proved Eq. 17, we now proceed to use it to show $\triangle (v\mid \psi ') \le \triangle (v\mid \psi )$. Since

$$\begin{aligned} \triangle (v\mid \psi ') =&\sum _{(\phi ,\phi ')} \theta (\phi ,\phi ') (U(dom(\psi ')\cup \{v\},\phi ') - U(dom(\psi '),\phi '))\\ \triangle (v\mid \psi ) =&\sum _{(\phi ,\phi ')} \theta (\phi ,\phi ') (U(dom(\psi )\cup \{v\}, \phi ) - U(dom(\psi ),\phi )) \end{aligned}$$

we have $\triangle (v\mid \psi ')\le \triangle (v\mid \psi )$ which completes the proof. $\square$

5.2 Lower bound

The major idea is that we only consider the profit between nodes which are activated by the same seed node. Accordingly, the lower bound can be defined as

$$\begin{aligned} L(S,\phi ) = \sum _{\{u,v\}\in \cup _{x\in S}P(I(\{x\},\phi ))}c(u,v) \end{aligned}$$

(19)

where $I(\{x\},\phi )$ are nodes activated by node x under realization $\phi$. It is easy to see that $L(S,\phi )\le f(S,\phi )$ for any $S \subseteq V$ since we ignore the profit of pairs of nodes which are activated by different seeds.

Lemma 6

Under any fixed realization $\phi$, $L(S,\phi )$ is monotone and submodular.

Proof

Given a fixed realization $\phi$ which means the state of all the edges in the social network is determined according to Remark 2, we just need to prove $L(S,\phi )$ is monotone and submodular in a live graph. Since the profit function $c: V\times V \rightarrow \mathbb {R}_{\ge 0}$ is nonnegative which means the profit of each pair of nodes is non-negative, the monotonicity of $L(S,\phi )$ follows immediately. For the submodularity, we need prove $L(A\cup \{e\}) -L(A) \ge L(B \cup \{e\}) -L(B)$, such that $A \subseteq B \subseteq V$ and $e\in V\setminus B$. We have $I(e) -\cup _{x\in A}I(x) \supseteq I(e) - \cup _{x\in B}I(x)$, since $A \subseteq B$. Thus $P(I(e) -\cup _{x\in A}I(x)) \supseteq P(I(e) - \cup _{x\in B}I(x))$, and the submodularity follows immediately. $\square$

To prove the lower bound is adaptive submodular, we define a new function

$$\begin{aligned} \hat{f} : 2 ^{V\times O}\rightarrow \mathbb {R}_{\ge 0} \end{aligned}$$

(20)

which quantifies the profit $L(S,\varPhi )$ when seeds S are in arbitrary states. Note $\hat{f}$ is a set function taking a set of (seeds, state) pairs as input. The profit $L(S,\phi )$ of choosing seeds S under realization $\phi$ is then

$$\begin{aligned} L(S,\phi ) := \hat{f}(\{(v,\phi (v)): v\in S\}) \end{aligned}$$

(21)

We make the value of $\hat{f}$ equals 0, when the status of the seeds are not consistent with each other. For example $\hat{f}({(v_1,\phi (v_1)),(v_2,\phi '(v_2)) }) =0$, if there is a edge which is declared to be live and dead by $\phi (v_1)$ and $\phi '(v_2)$ respectively.

Lemma 7

$\hat{f} : 2 ^{V\times O}\rightarrow \mathbb {R}_{\ge 0}$ is a monotone submodular function.

Proof

Since $\hat{f}((x,\phi (x))) = L(x, \phi )$ is nonnegative, for any $(x,\phi )$. The monotonicity of $\hat{f}$ follows immediately.

For the submodularity, we need prove $\hat{f}(A\cup \{x\}) -\hat{f}(A) \ge \hat{f}(B \cup \{x\}) -\hat{f}(B)$, such that $A \subseteq B \subseteq 2 ^{V\times O}$ and $x\in 2 ^{V\times O}\setminus B$. Note that x is actually a tuple $(e, \phi (e))$ or $(e , \phi '(e))$ which means that the node e is in state $\phi (e)$. We have $A:=\psi$ and $B:=\psi '$, and $\phi (e) = \phi '(e)$. We address the problem in two situations. One is called effective domain which means given realizations $\phi$ and $\phi '$, and partial realization $\psi$ and $\psi '$, such that $\phi \sim \psi$, $\phi ' \sim \psi '$, and $\psi$ is subrealization of $\psi '$. The other condition is called non-effective domain where the above condition is not satisfied. Actually it means that there exist some nodes whose states are not consistent with each other.

For the effective domain,

$$\begin{aligned} \hat{f} (\psi ' \cup (e,\phi '(e))) - \hat{f}(\psi ')=\,&L(dom(\psi ')\cup \{e\}, \phi ') -L(dom(\psi '),\phi ')\\ =\,&\sum _{\{u,v\}\in \cup _{x\in \{dom(\psi ')\cup e\}}P(I(\{x\},\phi ' ))}c(u,v)\\&\quad - \sum _{\{u,v\}\in \cup _{x\in dom(\psi ')}P(I(\{x\},\phi ' ))}c(u,v) \\ =\,&\sum _{\{u,v\}\in \{P( I(\{e\},\phi '))-\cup _{x\in dom(\psi ')}P(I(\{x\},\phi ' ))\}} c(u,v) \end{aligned}$$

in the same way

$$\begin{aligned} \hat{f} (\psi \cup (e,\phi (e))) - \hat{f}(\psi ) =\,&L(dom(\psi )\cup \{e\}, \phi ) -L(dom(\psi ),\phi )\\ =\,&\sum _{\{u,v\}\in \cup _{x\in \{dom(\psi )\cup e\}}P(I(\{x\},\phi ))}c(u,v)\\&\quad - \sum _{\{u,v\}\in \cup _{x\in dom(\psi )}P(I(\{x\},\phi ))}c(u,v) \\ =\,&\sum _{\{u,v\}\in \{P( I(\{e\},\phi ))-\cup _{x\in dom(\psi )}P(I(\{x\},\phi ))\}} c(u,v) \end{aligned}$$

According Lemma 3, we have $I(e,\phi ) = I(e,\phi ')$ since $\phi (e) = \phi '(e)$. So we get $P( I(e,\phi ')) = P( I(e,\phi ))$. And since $\psi$ is subrealization of $\psi '$, we have $dom(\psi )\subset dom(\psi ')$, and $I(x,\phi ) =I(x,\phi ')$ for $x\in dom(\psi )$. So we know $\cup _{x\in dom(\psi )}P(I(\{x\},\phi ) \subseteq \cup _{x\in dom(\psi ')}P(I(\{x\},\phi ' ))$. Thus $P( I(e,\phi '))-\cup _{x\in dom(\psi ')}P(I(\{x\},\phi ' )) \subseteq P( I(e,\phi ))-\cup _{x\in dom(\psi ')}P(I(\{x\},\phi ))\}$. Then we have

$$\begin{aligned} \hat{f} (\psi ' \cup (e,\phi '(e))) - \hat{f}(\psi ') \le \hat{f} (\psi \cup (e,\phi (e))) - \hat{f}(\psi ) \end{aligned}$$

For the non-effective domain, we make the value of $\hat{f}$ equals 0 when the status of some seeds are not consistent with each other according to its definition: if the state of $\phi '(e)$ is not consistent with $\psi '$ which means $\phi ' \sim \psi '$ is not satisfied and at the same time the state of $\phi (e)$ is not consistent with $\psi$ which means $\phi \sim \psi$ is not satisfied, then $\hat{f} (\psi '\cup (e,\phi '(e))) = 0$, and $\hat{f} (\psi \cup (e,\phi (e))) =0$. We have $\hat{f}(\psi ) \le \hat{f}(\psi ')$, since $\psi \subseteq \psi '$ and the monotonicity of $\hat{f}$. Thus

$$\begin{aligned} \hat{f} (\psi ' \cup (e,\phi '(e))) - \hat{f}(\psi ') \le \hat{f} (\psi \cup (e,\phi (e))) - \hat{f}(\psi ) \end{aligned}$$

If the state of $\phi '(e)$ is not consistent with $\psi '$ which means $\phi ' \sim \psi '$ is not satisfied, but the state of $\phi (e)$ is consistent with $\psi$, then $\hat{f} (\psi '\cup (e,\phi '(e))) = 0$ and $\hat{f} (\psi \cup (e,\phi (e))) \ge 0$. We have $\hat{f}(\psi ) \le \hat{f}(\psi ')$, since $\psi \subseteq \psi '$ and the monotonicity of $\hat{f}$. Thus

$$\begin{aligned} \hat{f} (\psi ' \cup (e,\phi '(e))) - \hat{f}(\psi ') \le \hat{f} (\psi \cup (e,\phi (e))) - \hat{f}(\psi ) \end{aligned}$$

which complete the proof. $\square$

Theorem 6

$L(S,\phi )$ is adaptive monotone and submodular.

Proof

Adaptive monotonicity is readily proved after observing that $L(\cdot , \phi )$ is monotonic for each $\phi$ according to Lemma 6. Moving on to adaptive submodularity, we define a coupled distribution $\theta (\phi , \phi ')$ over pairs of realizations $\phi \thicksim \psi$ and $\phi ' \thicksim \phi '$ which is the same as Theorem 5. So we have

$$\begin{aligned} \hat{\theta }(\mathbf{X} ,\mathbf{X} ') = \prod _{(u,w) \text{ unobserved } \text{ by } \psi } p_{uw}^{X_{uw}}(1-p_{uw})^{1-X_{uw}} \end{aligned}$$

and otherwise $\hat{\theta }(\mathbf{X} ,\mathbf{X} ')= 0$. Note that $p(\phi \mid \psi )=\varSigma _{\phi '}\theta (\phi ,\phi ')$ and $p(\phi '\mid \psi ') = \varSigma _{\phi } \theta (\phi ,\phi ').$ We next claim that for all $(\phi ,\phi ')\in \text{ support }(\theta )$,

$$\begin{aligned} L(dom(\psi ')\cup \{v\},\phi ') - L(dom(\psi '),\phi ') =\,&\hat{f}(\psi '\cup {(v,\phi '(v))} -\hat{f}(\phi ')) \nonumber \\ \le \,&\hat{f}(\psi \cup {(v,\phi (v))} -\hat{f}(\phi ))\nonumber \\ =\,&L(dom(\psi )\cup \{v\}, \phi ) - L(dom(\psi ),\phi ) \end{aligned}$$

(22)

from the submodularity of $\hat{f}$ according to Lemma 7. We now proceed to use it to show $\triangle (v\mid \psi ') \le \triangle (v\mid \psi )$.

$$\begin{aligned}&\triangle (v\mid \psi ') = \sum _{(\phi ,\phi ')} \theta (\phi ,\phi ') (L(dom(\psi ')\cup \{v\},\phi ') - L(dom(\psi '),\phi '))\\&\triangle (v\mid \psi ) = \sum _{(\phi ,\phi ')} \theta (\phi ,\phi ') (L(dom(\psi )\cup \{v\}, \phi ) - L(dom(\psi ),\phi )) \end{aligned}$$

we have $\triangle (v\mid \psi ') \le \triangle (v\mid \psi )$ according to (22), which completes the proof. $\square$

6 Algorithm

In this section, we propose a greedy policy with lazy evaluation based on submodularity of the upper and lower bound, and design an adaptive sandwich strategy for APMP which can get a data dependent approximation solution. To the best of our knowledge, this is the first paper trying to address the problem that is not adaptive submodular.

6.1 Lazy evaluation

As we know, when adaptive greedy algorithm selects a seed in the round i, it computes $\varDelta (v|\psi _{i})$ for all $v \in V$ and $0\le i \le k$, unless $v \in dom(\psi _{i})$, where $\psi _{i}$ is the partial realization after round i and k is constraint on number of seeds. The key insight is that $i \mapsto \varDelta (v|\psi _{i})$ is nonincreasing for all $v\in V$, because of the adaptive submodularity of the objective. Specifically speaking, in the round i of selecting a seed, if we know $\varDelta (v'|\psi _{j}) \le \varDelta (v|\psi _{i})$ for some items $v'$ and v and $j \le i$, then $\varDelta (v'|\psi _{i}) \le \varDelta (v|\psi _{i})$ follows, since $\varDelta (v'|\psi _{j}) \ge \varDelta (v'|\psi _{i})$ based on the adaptive submodularity. So there is no need to compute $\varDelta (v'|\psi _{i})$ in the round i.

6.2 Accelerated adaptive greedy algorithm

Pseudocode of the adaptive greedy algorithm with lazy evaluation is given in Algorithm 1. Its core idea is to choose the seed with the most expected marginal benefit at each step. S is used to store the seeds selected, T is the profit gained by the seeds in S. The expected marginal gain of each node is stored in the list Q. According to the strategy of lazy evaluation, the while loop computes conditional expected marginal benefit $\varDelta (v|\psi )$ for node v in decreasing order of upper bounds knows on them, until it finds an item whose value is at least as great as the upper bounds of all other nodes. Note the Q.max( ) return max value in the marginal gain list Q, and Max(Q) return the node which has the maximum marginal gain. When a seed with the greatest marginal benefit is found, we observe its realization denoted by $\psi '$ as shown in line 15. After observing the realization, we need to compute the actual marginal benefit of node $v_{max}$ denoted by $\delta _{v_{max}}^{\psi '}$ under partial realization $\psi '$ as shown in line 16. We will delete node $v_{max}$ and the nodes activated by it as shown in line 20 since their marginal gain will be 0 in the next round. The greedy policy will return the seeds and its profit.

6.3 Adaptive sandwich approximation policy

By adopting the sandwich strategy which is first proposed by [16], and using the proving technique introduced by [26], we design an adaptive greedy sandwich approximation policy for adaptive profit maximization problem, which is given in Algorithm 2. The basic idea of the sandwich strategy is that we find an adaptive greedy strategy based on the upper bound, the lower bound, and original function respectively. Then we choose the best greedy strategy for the original problem as the solution. Specifically, the adaptive sandwich approximation strategy works as follows. First, according to the upper bound we find a greedy strategy by calling Algorithm 1. When selecting the seed, we need to calculate the expected marginal gain $\triangle (v|\psi )$ according to the upper bound function as shown in line 9, i.e., $\triangle (v|\psi ) = \mathbb {E}[U(dom(\psi ) \cup {v}, \varPhi ) - U(dom(\psi ), \varPhi ) |\varPhi \sim \psi ]$. Note that after a node with the largest expected return is found, we need to calculate the actual marginal benefit of the node based on the original function instead of upper bound, i.e., $\delta _{v_{max}}^{\psi '}=f(v_{max}\cup S|\psi ')-f(S|\psi )$ as shown in line 16. This is a very important point. Because our purpose is choosing the best strategy for the original function, we need to evaluate the strategy with benefits of the original function. In the same way, for the lower bound we calculate $\triangle (v|\psi )$ according to the lower bound function, i.e., $\triangle (v|\psi ) = \mathbb {E}[L(dom(\psi ) \cup {v}, \varPhi ) - L(dom(\psi ), \varPhi ) |\varPhi \sim \psi ]$. And calculate the actual marginal benefit of the node based on the original function instead of lower bound, i.e., $\delta _{v_{max}}^{\psi '}=f(v_{max}\cup S|\psi ')-f(S|\psi )$.

6.4 Approximation ratio

Theorem 7

Let $\hat{\pi }_{max}$ be the policy return by Algorithm 2, then we have

$$\begin{aligned} f_{avg}(\hat{\pi }_{max})\ge \max \left\{ \frac{f_{avg}(\pi _{U})}{U_{avg}(\pi _{U})}\alpha ,\frac{L_{avg}(\pi _{L}^{*})}{f_{avg}(\pi _{f}^{*})}\beta \right\} \frac{1-\gamma }{1+\gamma }f_{avg}(\pi _{f}^{*}) \end{aligned}$$

where $\pi _{f}^{*}$, $\pi _{U}^{*}$, $\pi _{L}^{*}$ is the optimal policy for $f(\cdot )$, $U(\cdot )$, $L(\cdot )$ respectively, and $\alpha = \beta = 1-1/e.$

Proof

We have

$$\begin{aligned} f_{avg}(\pi _{U})&= \frac{f_{avg}(\pi _{U})}{U_{avg}(\pi _{U})}U_{avg}(\pi _{U}) \ge \frac{f_{avg}(\pi _{U})}{U_{avg}(\pi _{U})}\cdot \alpha \cdot U_{avg}(\pi _{U}^{*})\\&\ge \frac{f_{avg}(\pi _{U})}{U_{avg}(\pi _{U})}\cdot \alpha \cdot U_{avg}(\pi _{f}^{*})\ge \frac{f_{avg}(\pi _{U})}{U_{avg}(\pi _{U})}\cdot \alpha \cdot f_{avg}(\pi _{f}^{*}) \\ f_{avg}(\pi _{L})&\ge L_{avg}(\pi _{L})\ge \beta \cdot L_{avg}(\pi _{L}^{*})\ge \frac{L_{avg}(\pi _{L}^{*})}{f_{avg}(\pi _{A}^{*})}\cdot \beta \cdot f_{avg}(\pi _{f}^{*}) \end{aligned}$$

Let $\pi _{max}= \mathrm{argmax}_{\pi \in \{ \pi _{f},\pi _{U},\pi _{L} \}}f_{avg}(\pi )$, then

$$\begin{aligned} f_{avg}(\pi _{max})\ge \max \left\{ \frac{f_{avg}(\pi _{U})}{U_{avg}(\pi _{U})}\alpha ,\frac{L_{avg}(\pi _{L}^{*})}{f_{avg}(\pi _{f}^{*})}\beta \right\} f_{avg}(\pi _{f}^{*}). \end{aligned}$$

Since $\forall \pi \in \{ \pi _{f},\pi _{U},\pi _{L} \}$, $|\hat{f}_{avg}(\pi )-f_{avg}(\pi ) | \le \gamma f_{avg}(\pi )$, we have $(1+\gamma )f_{avg}(\hat{\pi }_{max})\ge (1-\gamma )f_{avg}(\pi _{max})$. It follows that

$$\begin{aligned} f_{avg}(\hat{\pi }_{max})\ge \frac{1-\gamma }{1+\gamma } f_{avg}(\pi _{max}) \end{aligned}$$

$\square$

6.5 Implementation

To implement the proposed adaptive greedy algorithm, the key step is to calculate the conditional expected marginal gain $\triangle (v|\psi )$ for the upper bound, lower bound, and original function. Unfortunately, all of them are $\sharp$P-hard.

Theorem 8

Given a seed v and partial realization $\psi$, computing conditional expected marginal gain $\triangle (v|\psi )$ for upper bound is $\sharp$ P-hard.

Proof

We prove the theorem through a special case in which the partial realization is $\emptyset$. Since $\psi$ is empty set, we have $\triangle (v |\psi ) = \mathbb {E}[U({v}, \varPhi )]$, where the expectation is taken with respect to $p(\phi )$. Apparently, it equals to compute the upper bound profit of node v in non-adaptive settings under the IC model. This is actually weighted influence spread computation problem which was proved $\sharp P$-hard [2], the theorem follows immediately. $\square$

Theorem 9

Given a seed v and partial realization $\psi$, computing conditional expected marginal benefit $\triangle (v | \psi )$ for lower bound is $\sharp$ P-hard.

Proof

We prove the theorem through a special case in which the partial realization is $\emptyset$. Since $\psi$ is empty set , we have $\triangle (v|\psi ) = \mathbb {E}[L({v}, \varPhi )]$, where the expectation is taken with respect to $p(\phi )$. Apparently, it equals to the problem about computing the lower bound profit of node v in non-adaptive settings. According to Remark 1 we can reduce it from AMP problem, and computing the lower bound of AMP is $\sharp P$-hard which is proved in [26], the theorem follows immediately. $\square$

Theorem 10

Given a seed v and partial realization $\psi$, computing conditional expected marginal benefit $\triangle (v | \psi )$ for original problem is $\sharp$ P-hard.

Proof

We prove the theorem through a special case in which the partial realization is $\emptyset$. Since $\psi$ is empty set, we have $\triangle (v \mid \psi ) := \mathbb {E}[f({v}, \varPhi )]$, where the expectation is taken with respect to $p(\phi )$. Apparently, it equals to the game profit computing problem in non-adaptive settings which is $\sharp$P-hard according to Theorem 2, the theorem follows immediately. $\square$

Although they are difficult to calculate, we can employ the Monte Carlo simulation to obtain an accurate estimation. By the Hoeffding’s Inequality, the error of the estimation can be infinitely small when a sufficient number of simulations are performed.

Table 1 The statistics of the data sets

7 Experiment

7.1 Settings

We use four social networks in our experiments. All datasets are publicly available. Email, DBLP can be obtained from SNAP website (http://snap.stanford.edu), while Facebook and Douban can be obtained from KONECT website (http://konect.uni-koblenz.de). The details of datasets are shown in Table 1.

The propagation probability for IC model is set to $\frac{1}{degree(v)}$ as widely used in other literatures [2, 22], and the profit between nodes is proportional to propagation probability on corresponding edges. For the nodes that are not directly adjacent, we set the profit between them as 0. For comparison, we propose two other algorithms as baselines. One is non-adaptive greedy algorithm in which we select k seeds in advance regardless of their realization. We denote it as Non in Figs. 2, 3 and 4. The other one is a random algorithm which selects the next node in a random way based on the current realization. We mark it as Random in Figs. 2, 3 and 4.

For non-adaptive greedy algorithm, we actually select k seeds in one step without observing the realization of any seed. So the non-adaptive greedy algorithm is similar to the greedy algorithm propose by Kempe [14] except that our objective function is the profit between activated node while their objective function is the number of the activated nodes. For random algorithm, it selects the next node v in a random way based on the current realization.We can employ the Monte Carlo simulation to obtain an estimation. As shown in [14] 10k iterations could get a acceptable quality of approximation. We simulate the process 10k times for each targeted node v and get the average value for conditional expected marginal gain$\triangle (v|\psi )$. For the adaptive policy value we use the same idea simulating the realization 1k times and get the average value. We implement all the algorithms in Python and the experiments run on a workstation with an Intel Xeon 4.0 GHz CPU and 64 GB memory.

Fig. 2

The relationship between profit and seed set size on Email

Fig. 3

The relationship between profit and seed set size on Facebook

Fig. 4

The relationship between profit and seed set size on Douban

7.2 Effectiveness and analysis

The results of profit computed by our proposed algorithms on four data sets are shown in Fig.2, 3 and 4 respectively. As the number of selected seeds increases, the performance of sandwich algorithm donated as Adapt in the figure is always superior to the baseline algorithms. This is because non-adaptive greedy algorithm ignores the stochastics of influence propagation and always chooses the same seed set under any realization. And our adaptive strategy must make a decision based on the actual situation of current network propagation when selecting a seed. Moreover, his submodular upper bound and lower bound guarantee its performance. An interesting question in adaptive optimization is how much better adaptive policies can perform when compared to non-adaptive policies. This is quantified by the adaptivity gap, and the gap as shown in Fig.2, 3 and 4 between the two algorithms is a good illustration of the effectiveness of adaptive strategy in social network impact issues. Not surprisingly, the performance of a random algorithm is the worst because it does not consider any validity or propensity when making a choice. On both small-scale and large-scale networks, the adaptive sandwich algorithm perform quite well and demonstrate good scalability.

8 Conclusion

In this paper, we propose the adaptive profit maximization problem which is not adaptive submodular, and analyze its complexity which is NP-hard. To address the stochastic optimization problem, we find the upper and lower bounds of it and prove both of them are adaptive submodular, so an adaptive greedy algorithm could gain a guaranteed approximate solution for them. Based on the upper and lower bound, we design an adaptive sandwich policy for APMP to get a data dependent approximate solution. To the best of our knowledge, this is the first paper applying the sandwich strategy to stochastic optimization problem which is not adaptive submodular.