Continuous Profit Maximization: A Study of Unconstrained Dr-submodular Maximization

An OSN can be abstracted as a directed graph $G=(V,E)$ where $V=\{v_{1},v_{2},\cdots,v_{n}\}$ is the set of $n$ nodes (users) and $E=\{e_{1},e_{2},\cdots,e_{m}\}$ is the set of $m$ edges (relationship between users). We default $|V|=n$ and $|E|=m$ when given $G=(V,E)$. For each directed edge $(u,v)\in E$, we say $v$ is an outgoing neighbor of $u$, and $u$ is an incoming neighbor of $v$. For any node $u\in V$, let $N^{-}(u)$ denote its set of incoming neighbors, and $N^{+}(u)$ denote its set of outgoing neighbors. In the process of influence diffusion, we consider a user is active if she accepts (is activated by) the information cascade from her neighbors or she is selected as a seed successfully. To model the influence diffusion, Kempe et al. [3] proposed two classical models, IC-model and LT-model.

Let $S\subseteq V$ be a seed set and $S_{i}\subseteq V$ be the set of all active nodes at time step $t_{i}$. The influence diffusion initiated by $S$ can be represented by a discrete-time stochastic process. At time step $t_{0}$, all nodes in $S$ are activated, so we have $S_{0}:=S$. Under the IC-model, there is a diffusion probabiltiy $p_{uv}\in(0,1]$ associated with each edge $(u,v)\in E$. We set $S_{i}:=S_{i-1}$ at time step $t_{i}$ $(t\geq 1)$ first; then, for each node $u\in S_{i-1}\backslash S_{i-2}$, activated first at time step $t_{i-1}$, it have one chance to activate each of its inactive outgoing neighbor $v$ with probability $p_{uv}$. We add $v$ into $S_{i}$ if $u$ activates $v$ successfully at $t_{i}$. Under the LT-model, each edge $(u,v)\in E$ has a weight $b_{uv}$, and each node $v\in V$ has a threshold $\theta_{v}$ sampled uniformly in $[0,1]$ and $\sum_{u\in N^{-}(v)}b_{uv}\leq 1$. We set $S_{i}:=S_{i-1}$ at time step $t_{i}$ $(t\geq 1)$ first; then, for each inactive node $v\in V\backslash S_{i-1}$, it can be activated if $\sum_{u\in S_{i-1}\cap N^{-}(v)}b_{uv}\geq\theta_{v}$. We add $v$ into $S_{i}$ if $v$ is activated successfully at $t_{i}$. The influence diffusion terminates when no more inactive nodes can be activated. In this paper, we consider the triggering mode, where IC-model and LT-model are its special cases.

From above, a triggering model can be defined as $\Omega=(G,\mathcal{D})$, where $\mathcal{D}=\{\mathcal{D}_{v_{1}},\mathcal{D}_{v_{2}},\cdots\mathcal{D}_{v_{n}}\}$ is a set of distribution over the subsets of each $N^{-}(v_{i})$.

For each node $v\in V$, under the IC-model, each node $u\in N^{-}(v)$ appears in $v$’s random triggering set $T_{v}$ with probability $p_{uv}$ independently. Under the LT-model, at most one node can appear in $T_{v}$, thus, for each node $u\in N^{-}(v)$, $T_{v}=\{u\}$ with probability $b_{uv}$ exclusively and $T_{v}=\emptyset$ with probability $1-\sum_{u\in N^{-}(v)}b_{uv}$. Now, we can define the realization (possible world) $g$ of graph $G$ under the triggering model $\Omega=(G,\mathcal{D})$, that is

If a node $u$ appears in $v$’s triggering set, $u\in T_{v}$, we say edge $(u,v)$ is live, or else edge $(u,v)$ is blocked. Thus, realization $g$ can be regarded as a subgraph of $G$, which is the remaining graph by removing these blocked edges. Let $\Pr[g|g\sim\Omega]$ be the probability of realization $g$ of $G$ sampled from distribution $\mathcal{D}$, that is,

where $\Pr[T_{v_{i}}|T_{v_{i}}\sim\mathcal{D}_{v_{i}}]$ is the probability of $T_{v_{i}}$ sampled from $\mathcal{D}_{v_{i}}$. Under the IC-model, $\Pr[T_{v}|T_{v}\sim\mathcal{D}_{v}]=\prod_{u\in T_{v}}p_{uv}\prod_{u\in N^{-}(v)\backslash T_{v}}(1-p_{uv})$, and under the LT-model, $\Pr[T_{v}=\{u\}|T_{v}\sim\mathcal{D}_{v}]=b_{uv}$ for each $u\in N^{-}(v)$ and $\Pr[T_{v}=\emptyset|T_{v}\sim\mathcal{D}_{v}]=1-\sum_{u\in N^{-}(v)}b_{uv}$ deterministically.

Given a seed set $S\subseteq V$, we consider $I_{\Omega}(S)$ as a random variable that denotes the number of active nodes (influence spread) when the influence diffusion of $S$ terminates under the triggering model $\Omega=(G,\mathcal{D})$. Then, the number of nodes that are reachable from at least one node in $S$ under a realization $g$, $g\sim\Omega$, is denoted by $I_{g}(S)$. Thus, the expected influence spread $\sigma_{\Omega}(S)$, that is

where it is the weighted average of influence spread under all possible graph realizations. The IM problem aims to find a seed set $S$, such that $|S|\leq k$, to maximize the expected influence spread $\sigma_{\Omega}(S)$.

Under the general marketing strategies, the definition of IM problem will be different from above [3]. Let $\mathbb{Z}^{d}_{+}$ be the collection of non-negative integer vector. A marketing strategy can be denoted by a $d$-dimensional vector $\boldsymbol{x}=(x_{1},x_{2},\cdots,x_{d})\in\mathbb{Z}^{d}_{+}$, and we call it “marketing vector”. Each component $\boldsymbol{x}(i)\in\mathbb{Z}_{+}$, $i\in[d]=\{1,2,\cdots,d\}$ means the number of investment units assigned to marketing action $M_{i}$. For example, $\boldsymbol{x}(i)=b$ tells us that marketing strategy $\boldsymbol{x}$ assigns $b$ investment units to marketing action $M_{i}$. Given a marketing vector $\boldsymbol{x}$, the probability that node $u\in V$ is activated as a seed is denoted by strategy function $h_{u}(\boldsymbol{x})$, where $h_{u}(\boldsymbol{x})\in[0,1]$. Thus, unlike the standard IM problem, the selection of seed set is not deterministic, but stochastic. Given a marketing vector $\boldsymbol{x}$, the probability of seed set $S$ sampled from $\boldsymbol{x}$, that is

where $\Pr[S|S\sim\boldsymbol{x}]$ is the probability that exactly nodes in $S$ are selected as seeds, but not in S are not selected as seeds under the marketing strategy $\boldsymbol{x}$, because each node is select as a seed independently. Thus, the expected influence spread $\mu_{\Omega}(\boldsymbol{x})$ of marketing vector $\boldsymbol{x}$ under the triggering model $\Omega(G,\mathcal{D})$ can be formulated, that is

As we know, benefit is the gain obtained from influence spread and cost is the price required to pay for marketing strategy. Here, we assume each unit of marketing action $M_{i}$, $i\in[d]$, is associated with a cost $c_{i}\in\mathbb{R}_{+}$. Then, the total cost function $c:\mathbb{Z}^{d}_{+}\rightarrow\mathbb{R}_{+}$ can be defined as $c(\boldsymbol{x})=\sum_{i\in[d]}c_{i}\cdot\boldsymbol{x}(i)$. For simplicity, we consider the expected influence spread as our benefit. Thus, the expected profit $f_{\Omega}(\boldsymbol{x})$ we can obtain from marketing strategy $\boldsymbol{x}$ is the expected influence spread of $\boldsymbol{x}$ minus the cost of $\boldsymbol{x}$, that is

where $c(\boldsymbol{x})=\sum_{i\in[d]}c_{i}\cdot\boldsymbol{x}(i)$. Therefore, the continuous profit maximization under the general marketing strategies (CPM-MS) problem is formulated as follows:

Generally, defined on set, a set function $\alpha:2^{V}\rightarrow\mathbb{R}$ is monotone if $\alpha(S)\leq\alpha(T)$ for any $S\subseteq T\subseteq V$, and submodular if $\alpha(S)+\alpha(T)\geq\alpha(S\cup T)+\alpha(S\cap T)$. The submodularity of set function implies a diminishing return property, thus $\alpha(S\cup\{u\})-\alpha(S)\geq\alpha(T\cup\{u\})-\alpha(T)$ for any $S\subseteq T\subseteq V$ and $u\notin T$. These two definitions of submodularity on set function are equivalent. Defined on integer lattice, a vector function $\beta:\mathbb{Z}^{d}_{+}\rightarrow\mathbb{R}$ is monotone if $\beta(\boldsymbol{s})\leq\beta(\boldsymbol{t})$ for any $\boldsymbol{s}\preceq\boldsymbol{t}\in\mathbb{Z}^{d}_{+}$, and submodular if $\beta(\boldsymbol{s})+\beta(\boldsymbol{t})\geq\beta(\boldsymbol{s}\lor\boldsymbol{t})+\beta(\boldsymbol{s}\land\boldsymbol{t})$ for any $s,t\in\mathbb{Z}^{d}_{+}$, where $(\boldsymbol{s}\lor\boldsymbol{t})(i)=\max\{\boldsymbol{s}(i),\boldsymbol{t}(i)\}$ and $(\boldsymbol{s}\land\boldsymbol{t})(i)=\min\{\boldsymbol{s}(i),\boldsymbol{t}(i)\}$. Here, $\boldsymbol{s}\preceq\boldsymbol{t}$ implies $\boldsymbol{s}(i)\leq\boldsymbol{t}(i)$ for each component $i\in[d]$. Besides, we consider a vector function is diminishing return submodular (dr-submodular) if $\beta(\boldsymbol{s}+\boldsymbol{e}_{i})-\beta(\boldsymbol{s})\geq\beta(\boldsymbol{t}+\boldsymbol{e}_{i})-\beta(\boldsymbol{t})$ for any $\boldsymbol{s}\preceq\boldsymbol{t}$ and $i\in[d]$, where $\boldsymbol{e}_{i}\in\mathbb{Z}^{d}_{+}$ is the $i$-th unit vector with the $i$-th component being $1$ and others being $0$. Different from the submodularity for a set function, for a vector function, $\beta$ is submodular does not mean it is dr-submodular, but the oppposite is true. Thus, dr-submodularity is stronger than submodularity generally.

Given a seed set $S\subseteq V$, it is #P-hard to compute the expected influence spread $\sigma_{\Omega}(S)$ under the IC-model [17] and the LT-model [18]. Assume that a marketing vector $\boldsymbol{x}\in\{0,1\}^{n}$ and $h_{u}(\boldsymbol{x})=\boldsymbol{x}(u)$ for $u\in V$ where user $u$ is a seed if and only if $\boldsymbol{x}(u)=1$. According to the Equation (4), the expected influence spread $\mu_{\Omega}(\boldsymbol{x})$ is equivalent to $\sigma_{\Omega}(S)$ in which $S=\{u\in V:\boldsymbol{x}(u)=1\}$. Thereby, given a marketing vector $\boldsymbol{x}$, computing the expected influence spread $\mu_{\Omega}(\boldsymbol{x})$ is #P-hard as well under the IC-model and LT-model. Subsequently, a natural question how to estimate the value of $\mu_{\Omega}(\boldsymbol{x})$ given $\boldsymbol{x}$ effectively. To estimate $\mu_{\Omega}(\boldsymbol{x})$, we usually adopt Monte-Carlo simulations. However, it is inconvenient for us to use such a method here because the randomness comes from two parts, one is from the seed selection, and the other is from the process of influence diffusion. Therefore, we require to design a more simple and efficient method.

First, we are able to establish an equivalent relationship between $\sigma_{\Omega}(\cdot)$ and $\mu_{\Omega}(\cdot)$. Given a social network $G=(V,E)$ and a marketing vector $\boldsymbol{x}\in\mathbb{Z}^{d}_{+}$, we create a constructed graph $\widetilde{G}=(\widetilde{V},\widetilde{E})$ by adding a new node $\widetilde{u}$ and a new directed edge $(\widetilde{u},u)$ for each node $u\in V$ to $G$. Take IC-model for instance, the diffusion probability for this new edge $(\widetilde{u},u)$ can be set as $p_{\widetilde{u}u}=h_{u}(\boldsymbol{x})$. Then, we have

where $\mu(\cdot|G)$ and $\sigma(\cdot|\widetilde{G})$ imply that we compute them under the graph $G$ and the constructed graph $\widetilde{G}$.

Based on the Theorem 3, we can get an accurate estimation for the objective function $f_{\Omega}(\boldsymbol{x})$, shown as (6), of CPM-MS problem by adjusting the parameter $\gamma$ and $\delta$ definitely.

For non-negative submodular functions, Buchbinder et al. [12] designed a double greedy algorithm to get a solution for the USM problem with a tight theoretical guarantee. Under the deterministic setting, the double greedy algorithm has a $(1/3)$-approximation, while it has a $(1/2)$-approximation under the randomized setting. Extending from set to integer lattice, we derive a revised double greedy algorithm that is suitable for dr-submodular functions, namely UDSM problem. We adopt the randomized setting, and the lattice-based double greedy algorithm is shown in Algorithm 1. We omit the subscript of $f_{\Omega}(\cdot)$, denote it by $f(\cdot)$ from now on.

Here, we denote by $f(\boldsymbol{e}_{i}|\boldsymbol{x})=f(\boldsymbol{x}+\boldsymbol{e}_{i})-f(\boldsymbol{x})$, the marginal gain of adding component $i\in[d]$ by $1$. Generally, this algorithm is initialized by $[\boldsymbol{0},\boldsymbol{b}]$, and for each component $i\in[d]$, we increase $\boldsymbol{x}(i)$ by $1$ or decrease $\boldsymbol{y}(i)$ by $1$ until they are equal in each inner (while) iteration. The result returned by Algorithm 1 has $\boldsymbol{x}=\boldsymbol{y}$. Then, we have the following conclusion which can be inferred directly from double greedy algorithm in [12], that is

According to Theorem 4, $(1/2)$-approximation is based on an assumption that $f(\boldsymbol{0})+f(\boldsymbol{b})\geq 0$, and this is almost impossible in may real application scenarios. It means that we are able to gain profit if giving all marketing action full investments, which is ridiculous for viral marketing. However, a valid approximation ratio cannot be obtained by using Algorithm 1 when $f(\boldsymbol{b})<0$ exists. To address this problem, Tang et al. [8] proposed a groundbreaking techniques, called iterative pruning, to reduce the search space such that the objective is non-negative in this space and without losing approximation guarantee. But their techniques are designed for submodular function based on set domain, it cannot be applied to dr-submodular function directly. Inspired by [8], we develop an iterative pruning technique suitable for dr-submodular functions in this section, which is a non-trival transformation from set to integer lattice.

Given a dr-submodular function $f(\boldsymbol{x})$ defined on $\boldsymbol{x}\preceq\boldsymbol{b}$, we have two vectors $\boldsymbol{g}_{1}$ and $\boldsymbol{h}_{1}$, such that: (1) $\boldsymbol{g}_{1}(i)=0$ if $f(\boldsymbol{e}_{i}|\boldsymbol{b}-\boldsymbol{b}(i)\boldsymbol{e}_{i})\leq 0$, or else $\boldsymbol{g}_{1}(i)=\max\{k:f(\boldsymbol{e}_{i}|\boldsymbol{b}-\boldsymbol{b}(i)\boldsymbol{e}_{i}+(k-1)\boldsymbol{e}_{i})>0\}$ for $k\in\{1,\cdots,\boldsymbol{b}(i)\}$; (2) $\boldsymbol{h}_{1}(i)=0$ if $f(\boldsymbol{e}_{i}|\boldsymbol{0})<0$, or else $\boldsymbol{h}_{1}(i)=\max\{k:f(\boldsymbol{e}_{i}|\boldsymbol{0}+(k-1)\boldsymbol{e}_{i})\geq 0\}$ for $k\in\{1,\cdots,\boldsymbol{b}(i)\}$.

From above, Lemma 3 determines a range for the optimal vector, thus reducing the search space. Then, the collection $\pi_{1}=[\boldsymbol{g}_{1},\boldsymbol{h}_{1}]$ can be pruned further in an iterative manner. Now, the upper bound of the optimal vector is $\boldsymbol{h}_{1}$, i.e., $\boldsymbol{x}^{*}\preceq\boldsymbol{h}_{1}$, hereafter, we are able to increase $\boldsymbol{g}_{1}$ to $\boldsymbol{g}_{2}$, where $\boldsymbol{g}_{2}(i)=\boldsymbol{g}_{1}(i)$ if $f(\boldsymbol{e}_{i}|\boldsymbol{h}_{1}-\boldsymbol{h}_{1}(i)\boldsymbol{e}_{i}+\boldsymbol{g}_{1}(i)\boldsymbol{e}_{i})\leq 0$, or else $\boldsymbol{g}_{2}(i)=\boldsymbol{g}_{1}(i)+\max\{k:f(\boldsymbol{e}_{i}|\boldsymbol{h}_{1}-\boldsymbol{h}_{1}(i)\boldsymbol{e}_{i}+\boldsymbol{g}_{1}(i)\boldsymbol{e}_{i}+(k-1)\boldsymbol{e}_{i})>0\}$ for $k\in\{1,\cdots,\boldsymbol{h}_{1}(i)-\boldsymbol{g}_{1}(i)\}$. The lower bound of the optimal vector is $\boldsymbol{g}_{1}$, i.e., $\boldsymbol{x}^{*}\succeq\boldsymbol{g}_{1}$, and similarly we are able to decrease $\boldsymbol{h}_{1}$ to $\boldsymbol{h}_{2}$, where $\boldsymbol{h}_{2}(i)=\boldsymbol{h}_{1}(i)$ if $f(\boldsymbol{e}_{i}|\boldsymbol{g}_{1})<0$, or else $\boldsymbol{h}_{2}(i)=\boldsymbol{g}_{1}(i)+\max\{k:f(\boldsymbol{e}_{i}|\boldsymbol{g}_{1}+(k-1)\boldsymbol{e}_{i})\geq 0\}$ for $k\in\{1,\cdots,\boldsymbol{h}_{1}(i)-\boldsymbol{g}_{1}(i)\}$. In this process, it generates a more compressed collection $\pi_{2}=[\boldsymbol{g}_{2},\boldsymbol{h}_{2}]$ than $\pi_{1}$. We repeat this process iteratively until $\boldsymbol{g}_{t}$ and $\boldsymbol{h}_{t}$ cannot be increased and decreased further. The Lattice-basedPruning algorithm is shown in Algorithm 2. The collection returned by Algorithm 2 is denoted by $\pi^{\circ}=[\boldsymbol{g}^{\circ},\boldsymbol{h}^{\circ}]$.