1 Introduction

Consider a graph \(G=(V,E)\) and a vertex subset \(A \subseteq V\). A vertex v is positive-influence dominated by A if either v is in A or at least half the number of neighbors of v belong to A. The positive-influence dominating has been studied extensively in the literature [6, 12, 14] due to its applications in social networks.

A positive comment produces a positive-influence and a negative comment generates a negative-influence. Every person is influenced by his friends positively or negatively, and tends to adopt a behavior with more positive-influence. For example, more children begin smoking when parents are smoking [10]. This is the background of the concept of positive-influence dominating.

Suppose a company wants to advertise its product by sending out some free samples for generating positive-influence for dominating a group of target members in a social networks. For example, if the product is woman’s clothing, then the target group should consist of only women. To dominate all target members by positive-influence, how can samples used be distributed to minimize the total number of free samples? This viral marketing problem can be formulated as the positive-influence target-dominating set (PITD) problem in the following way: given a graph G and a subset S of vertices, find the minimum vertex subset A such that every vertex in S is positive-influence dominated by A. Each vertex in S is called a target and S is called a target set. In this paper, we show two results:

  1. 1.

    The PITD problem has a polynomial-time \([\log \Delta + O(1)]\)-approximation in general graph G where \(\Delta \) is the maximum vertex-degree of G.

  2. 2.

    For target set S with \(|S|=\Omega (|V|)\), the PITD problem has a polynomial-time O(1)-approximation in power-law graphs.

2 Preliminaries

Consider a finite set X and a function \(f: 2^X \rightarrow \mathfrak {R}\). Function f is called a submodular function if for any two subsets A and B of X,

$$\begin{aligned} f(A) + f(B) \ge f(A \cup B) + f(A \cap B). \end{aligned}$$

Function f is monotone nondecreasing if

$$\begin{aligned} A \subset B \Rightarrow f(A) \le f(B). \end{aligned}$$

A monotone nondecreasing submodular function f with \(f(\emptyset )=0\) is called a polymatroid function. The followings are well-known properties of submodular and monotone nondecreasing functions and polymatroid functions, which can be found in [8, 11, 13].

Lemma 1

Function f is monotone nondecreasing submodular if and only if for any element \(x \in X\), and two subsets A and B with \(A \subset B\),

$$\begin{aligned} \Delta _x f(A) \ge \Delta _x f(B) \end{aligned}$$

where \(\Delta _xf(A) = f(A \cup \{x\})-f(A)\).

Lemma 2

Suppose f is a monotone nondecreasing submodular function. Then for any constant c, \(\min (c,f)\) is monotone nondecreasing submodular. Moreover, if f is a polymatroid function and \(c > 0\) is a constant, then \(\min (c,f)\) is also a polymatroid function.

Lemma 3

If f and g are two polymatroid functions, then \(f+g\) is also polymatroid.

Consider a polymatroid function f on \(2^X\) and a nonnegative cost function \(c: X \rightarrow \mathfrak {R}_+\). Define \(c(A) = \sum _{v \in A}c(v)\). The following is called the submodular cover problem:

$$\begin{aligned} \min&c(A) \\ \text{ subject } \text{ to }&A \in \Omega (f) \end{aligned}$$

where \(\Omega (f) = \{A \mid f(A)=f(X)\}\). There is a greedy approximation algorithm with a Theorem on its performance for the submodular cover problem which can found in [8, 13].

figure a

Theorem 4

If f is a polymatroid integer function on \(2^X\), then Greedy Algorithm SC produces an approximation solution for the submodular cover problem within a factor of \(1+\ln \gamma \) from the optimal where \(\gamma = \max _{x \in X}f(\{x\})\).

3 In general graphs

Consider a graph \(G=(V,E)\) and a set of targets, \(S \subseteq V\). For any \(v \in V\), denote \(deg_A(v) = |\{(u,v) \mid u \in A \text{ or } v \in A\}|\). For any vertex subset A, define

$$\begin{aligned} f_S(A) = \sum _{v \in S} \min \left( \left\lceil \frac{1}{2} \cdot deg(v) \right\rceil , deg_A(v)\right) . \end{aligned}$$

Then we have the following.

Lemma 5

For any given subset of vertices S, \(f_S\) is a polymatroid function.

Proof

We claim that \(g(A)=deg_A(v)\) is a polymatroid function for any \(v \in V\). Note that \(g(\emptyset )=0\). By Lemma 1, it is sufficient to show that for any vertex \(x \in V\) and two vertex subsets A and B with \(A \subset B\), \(\Delta _xg(A) \ge \Delta _xg(B)\). We divide the proof into three cases.

Case 1. \(v \in A\). Then \(g(A) = g(A\cup \{x\}) = g(B) = g(B \cup \{x\})= deg(v)\). Hence, \(\Delta _xg(A) = \Delta _xg(B) = 0\).

Case 2. \(v \in B\setminus A\). Then \(g(B)=g(B \cup \{x\})=deg(v)\). Hence, \(\Delta _xg(A) \ge \Delta _xg(B)=0\).

Case 3. \(v \not \in B\). If \(v \ne x\), then we have

$$\begin{aligned} \Delta _xg(A)= & {} g(A \cup \{x\}) - g(A) \\= & {} |(A \cup \{x\}) \cap N(v)| - |A \cap N(v)|\\\ge & {} |(B \cup \{x\}) \cap N(v)| - |B \cap N(v)|\\= & {} \Delta _x g(B), \end{aligned}$$

where N(v) is the set of neighbors of v. If \(v = x\), then we have

$$\begin{aligned} \Delta _xg(A)= & {} g(A \cup \{x\}) - g(A) \\= & {} deg(v) - |A \cap N(v)|\\\ge & {} deg(v) - |B \cap N(v)|\\= & {} \Delta _x g(B). \end{aligned}$$

Now, by our claim and Lemmas 2 and 3, \(f_S\) is also a polymatroid function. \(\Box \)

Lemma 6

A vertex subset A is a positive-influence dominating set for target S if and only if \(f_S(A)=f_S(V)\).

Proof

Note that v is positive-influence dominated by A if and only if \(\lceil \frac{1}{2}\cdot deg(v) \rceil \le deg_A(v)\). Now, the lemma follows immediately from this fact. \(\Box \)

Theorem 7

Let a target set S be given. Then there exists a polynomial-time greedy algorithm which produces an approximation solution for the PITD problem, within a factor of \(1+\ln \lceil \frac{3}{2}\Delta \rceil \) from the optimal where \(\Delta \) is the maximum vertex degree of graph G.

Proof

By Lemma 6, \(\Omega (f_S)\) is the set of positive-influence dominating sets for target S. Thus, finding the minimum positive-influence dominating set for target S is the submodular cover problem with polymatroid function \(f_S\) and constant cost function \(c(u) = 1\) for every vertex u.

By Lemmas 5, 6 and Theorem 4, Greedy Algorithm SC produces an approximation solution within a factor of \(1+\ln \gamma \) from the optimal where \(\gamma = \max _{u \in V} f_S (\{u\})\). Note that

$$\begin{aligned} f_S(\{u\}) = \sum _{v \in S} \min \left( \left\lceil \frac{1}{2} \cdot deg(v) \right\rceil , deg_{\{u\}}(v)\right) . \end{aligned}$$

In this sum, when \(v=u\), the corresponding term is equal to \(\lceil \frac{1}{2} \cdot deg(u) \rceil \) since by our definition of \(deg_A(v)\), \(deg_{\{u\}}(u) = deg (u)\). When \(v \ne u\) and \((v,u) \in E\), the coresponding term is equal to 1. When \(v \ne u\) and \((v,u) \not \in E\), the corresponding term is equal to 0. Therefore,

$$\begin{aligned} \gamma= & {} \max _{u \in V} f_S(\{u\})\\\le & {} \max _{u \in V} \left( deg (u) + \left\lceil \frac{1}{2}deg(u) \right\rceil \right) \\= & {} \max _{u \in V} \left\lceil \frac{3}{2} deg(u) \right\rceil \\\le & {} \left\lceil \frac{3}{2}\Delta \right\rceil . \end{aligned}$$

\(\Box \)

4 In power law graphs

Next, we move our attention to power law graphs. A graph G is said to belong to class \(C(\alpha ,\gamma )\) if G has no isolated vertex and, for \(k \ge 1\), the number of vertices with degree k is \(\lfloor \frac{e^{\alpha }}{k^{\gamma }}\rfloor \). Clearly, the maximum vertex degree \(\Delta = \lfloor e^{\alpha /\gamma } \rfloor \). For the number n of vertices and the number m of edges, we have

$$\begin{aligned} n = \sum _{k=1}^{\Delta } \left\lfloor \frac{e^{\alpha }}{k^{\gamma }} \right\rfloor \le \sum _{k=1}^{\Delta } \frac{e^{\alpha }}{k^{\gamma }} < 2n, \end{aligned}$$

and

$$\begin{aligned} m = \frac{1}{2} \cdot \sum _{k=1}^{\Delta } k \left\lfloor \frac{e^{\alpha }}{k^{\gamma }} \right\rfloor \le \frac{1}{2} \cdot \sum _{k=1}^{\Delta } \frac{e^{\alpha }}{k^{\gamma -1}} < 2m. \end{aligned}$$

Usually, an online social network varies as time changes, which can be formulated by a family of power law graphs with a fixed \(\gamma \). In this family, m and n are varied when \(\alpha \) is varied. Our study will emphase on a family of power law graphs with fixed \(\gamma > 2\) because many social networks are such a family of power law graphs [1–5, 9].

Let us first show some properties for such a family of power law graphs \(C(\alpha ,\gamma )\).

Lemma 8

For any power law graph \(G \in C(\alpha ,\gamma )\) with fixed \(\gamma > 2\), \(n \ge c_1 \cdot m\) where \(c_1\) is a constant depending on only \(\gamma \).

Proof

It suffices to show that n / m is greater than a positive constant. Let \(\zeta (\gamma )\) be the Riemann Zeta function, i.e., \(\zeta (\gamma ) = \sum _{k=1}^{\infty } \frac{1}{k^{\gamma }}\). Then

$$\begin{aligned} n/m \ge \frac{0.5 \sum _{k=1}^{\Delta }\frac{1}{k^{\gamma }}}{0.5\sum _{k=1}^{\Delta }\frac{1}{k^{\gamma -1}}} > \frac{\zeta (\gamma )}{\zeta (\gamma -1)}. \end{aligned}$$

\(\Box \)

For any vertex subset A, denote \(deg(A) = \sum _{v \in A}deg(v)\).

Lemma 9

Suppose G is a graph without isolated vertex and S is a target set. Let A be a positive-influence target-dominating set in G. Then \(deg(A) \ge 0.5 \cdot |S|\).

Proof

Note that at least |S| vertices are positive-influence dominated by A and each vertex has degree at least one. Thus, \(deg(S) \ge |S|\). Since A is a positive-influence target-dominating set for target set S, each vertex \(v \in S\) has at least half the number of neighbors in A. Hence, we have \(deg(A) \ge 0.5 deg(S) \ge 0.5 |S|\). \(\Box \)

Lemma 10

For any constant \(c >0\) and \(\gamma > 2\), there exists a constant \(c_2 >0\), which depends on only c and \(\gamma \), such that for any graph G in class \(C(\alpha ,\gamma )\) with fixed \(\gamma > 2\) and any vertex subset A,

$$\begin{aligned} deg(A) \ge c m \Rightarrow |A| \ge c_2 n. \end{aligned}$$

Proof

Let \(k_0\) be the largest integer such that

$$\begin{aligned} |A| \le \sum _{k = k_0}^{\Delta } \left\lfloor \frac{e^{\alpha }}{k^{\gamma }} \right\rfloor . \end{aligned}$$

Then

$$\begin{aligned} c m \le deg(A) \le \sum _{k = k_0}^{\Delta } \frac{e^{\alpha }}{k^{\gamma -1}}. \end{aligned}$$
(1)

Since \(\sum _{k=1}^{\Delta }\frac{1}{k^{\gamma -1}} \rightarrow \zeta (\gamma -1)\) as \(\Delta \rightarrow \infty \), there exists \(\Delta _0>0\) such that for \(\Delta > \Delta _0\), \(\sum _{k=1}^{\Delta } \frac{1}{k^{\gamma -1}} \ge 0.5\zeta (\gamma -1)\), where \(\Delta _0\) depends on only \(\gamma \). Note that for \(1\le k \le \Delta \), \(\lfloor \frac{e^{\alpha }}{k^{\gamma }}\rfloor \ge 1\). Therefore, for \(1\le k \le \Delta \), \(\lfloor \frac{e^{\alpha }}{k^{\gamma }}\rfloor > 0.5 \cdot \frac{e^{\alpha }}{k^{\gamma }}\). Thus, for \(\Delta > \Delta _0\),

$$\begin{aligned} m= & {} \frac{1}{2} \sum _{k=1}^{\Delta } k \cdot \left\lfloor \frac{e^{\alpha }}{k^{\gamma }} \right\rfloor \\> & {} \frac{1}{4} \sum _{k=1}^{\Delta }\frac{e^{\alpha }}{k^{\gamma -1}} \\\ge & {} \frac{1}{8}\zeta (\gamma -1)e^{\alpha }. \end{aligned}$$

Choose \(k_1> 0\) such that

$$\begin{aligned} \sum _{k=k_1}^{\infty }\frac{1}{k^{\gamma -1}} < c\zeta (\gamma -1)/8. \end{aligned}$$

Then \(k_1\) depends on only c and \(\gamma \). Moreover, for \(\Delta > \Delta _0\),

$$\begin{aligned} cm > \sum _{k=k_1}^{\infty } \frac{e^{\alpha }}{k^{\gamma -1}} > \sum _{k=k_1}^{\Delta }\frac{e^{\alpha }}{k^{\gamma -1}}. \end{aligned}$$
(2)

Comparing (2) with (1), we obtain \(k_0 < k_1\). It follows that

$$\begin{aligned} |A| > \sum _{k=k_1}^{\Delta } \left\lfloor \frac{e^{\alpha }}{k^{\gamma }} \right\rfloor \ge \frac{1}{2} \sum _{k=k_1}^{\Delta } \frac{e^{\alpha }}{k^{\gamma }} \ge \frac{n}{2} \cdot \frac{\sum _{k=k_1}^{\Delta } \frac{1}{k^{\gamma }}}{\sum _{k=1}^{\Delta }\frac{1}{k^{\gamma }}}. \end{aligned}$$

Since

$$\begin{aligned} \frac{\sum _{k=k_1}^{\Delta } \frac{1}{k^{\gamma }}}{\sum _{k=1}^{\Delta }\frac{1}{k^{\gamma }}} \rightarrow \frac{\sum _{k=k_1} ^{\infty }\frac{1}{k^{\gamma }}}{\zeta (\gamma )} \quad \text{ as } \Delta \rightarrow \infty , \end{aligned}$$

we can choose \(\Delta _1 \ge \Delta _0\) such that for \(\Delta > \Delta _1\),

$$\begin{aligned} \frac{\sum _{k=k_1}^{\Delta } \frac{1}{k^{\gamma }}}{\sum _{k=1}^{\Delta }\frac{1}{k^{\gamma }}} \ge \beta _1 =0.5 \frac{\sum _{k=k_1} ^{\infty }\frac{1}{k^{\gamma -1}}}{\zeta (\gamma )}. \end{aligned}$$

Here, \(\Delta _1\) depends on \(k_1\) and \(\gamma \), and hence depends on only c and \(\gamma \). Therefore, for \(\Delta > \Delta _1\),

$$\begin{aligned} |A| > n (\beta _1 /2). \end{aligned}$$

For \(\Delta \le \Delta _1\), we note \(\Delta = e^{\lfloor \alpha /\gamma \rfloor }\) and hence \(e^{\alpha } \le (\Delta _1+1)^{\gamma }\). Therefore,

$$\begin{aligned} n \le \sum _{k=1}^{\Delta } \frac{e^{\alpha }}{k^{\gamma }} \le \beta _2 = \sum _{k=1}^{\Delta _1}\frac{(\Delta _1+1)^{\gamma }}{k^{\gamma }}. \end{aligned}$$

Since \(|A| \ge 1\), we have that for \(\Delta \le \Delta _1\),

$$\begin{aligned} |A| \ge n \cdot \frac{1}{\beta _2}. \end{aligned}$$

Set \(c_2 = \min (\beta _1/2, 1/\beta _2)\). Then

$$\begin{aligned} |A| \ge c_2 n. \end{aligned}$$

Since \(\beta _1\) and \(\beta _2\) depend on only c and \(\gamma \), \(c_2\) depends on only c and \(\gamma \). \(\Box \)

Theorem 11

For any family of power-lar graphs \(G=(V,E)\) in \(C(\alpha ,\gamma )\) with fixed \(\gamma > 2\) and target set S with \(|S| \ge \mu n\) for a constant \(\mu >0\), there exists a polynomial-time approximation algorithm for PITD problem, with constant performance ratio depending on only \(\mu \) and \(\gamma \).

Proof

Suppose A is a positive-influence target-dominating set for target set S. By Lemma 9, \(deg (A) \ge 0.5 |S|\). Since \(|S| \ge \mu n\) and \(n \ge c_1 m\) by Lemma 8, we have \(deg (A) \ge 0.5 |S| \ge 0.5\mu n \ge 0.5\mu c_1 \cdot m\). By Lemma 10, \(|A| \ge c_2 n\) where \(c_2\) depends on \(0.5\mu c_1\) and \(\gamma \), i.e., depends on \(\mu \) and \(\gamma \). Since \(|A| \le n\), the ratio of sizes of any two positive-influence target-dominating sets is upper bounded by \(1/c_2\). This means that any positive-influence target-dominating set for target S is a \((1/c_2)\)-approximation solution. \(\Box \)

Given a graph \(G=(V,E)\) and a fraction r with \(0 <r \le 1\), the positive-influence partial-dominating set (PIPD) problem is to find the minimum vertex subset A such that at least a portion r of vertices are positive-influence dominated by A. With above approach, we can also show the following.

Theorem 12

For any family of powr-law graphs G in class \(C(\alpha , \gamma )\) with fixed \(\gamma > 2\), the PIPD problem has a polynomial-time approximation with a constant performance ratio depending on only \(\gamma \) and r.

Proof

Suppose that at least rn vertices are positive-influence dominated by A and each vertex has degree at least one. Let B denote the set of vertices positive-influence dominated by A. Then \(|B| \ge rn\) and \(deg(B) \ge rn\). Since each vertex \(v \in B\) has at least a half number of neighbors in A, we have \(deg(A) \ge 0.5 rn\). By Lemma 8, \(deg(A) \ge 0.5r n \ge 0.5rc_1 \cdot m\). By Lemma 10, \(|A| \ge c_2 n\), where \(c_2\) depends on only r and \(\gamma \). This means that every feasible solution for the PIPD problem is a \((1/c_2)\)-approximation. \(\Box \)

5 Discussion

Note that the positive-influence dominating set (PIDS) problem in [6, 7] is exactly the PITD problem in case \(S=V\) and the PIPD problem in case \(r=1\). Therefore, all lower bound results in [6, 7] can be extended to the PITD problem and the PIPD problem. Thus, we have the following.

Theorem 13

  1. (a)

    In general graphs, the PITD (and the PIPD) problem has no polynomial-time \((0.5-\varepsilon )\ln n\)-approximation for any \(\varepsilon >0\) unless \(NP \subseteq DTIME(n^{O(\log \log n)})\).

  2. (b)

    In power-law graphs, both the PITD and the PIPD problems are NP-hard.

This lower-bound indicates that the result in Theorem 7 is almost the best possible. However, it is an open problem whether there exists a PTAS for the PITD (or the PIPD) problem.