Towards Profit Maximization for Online Social Network Providers
Jing Tang Xueyan Tang Junsong Yuan
cs.SI cs.DS

Complexes of dipolar excitons in layered quasi-two-dimensional nanostructures
    Maria R. Vladimirova
    December 30, 2023
=============================================================================


Online Social Networks (OSNs) attract billions of users to share information and communicate where viral marketing has emerged as a new way to promote the sales of products. An OSN provider is often hired by an advertiser to conduct viral marketing campaigns. The OSN provider generates revenue from the commission paid by the advertiser which is determined by the spread of its product information. Meanwhile, to propagate influence, the activities performed by users such as viewing video ads normally induce diffusion cost to the OSN provider. In this paper, we aim to find a seed set to optimize a new profit metric that combines the benefit of influence spread with the cost of influence propagation for the OSN provider. Under many diffusion models, our profit metric is the difference between two submodular functions which is challenging to optimize as it is neither submodular nor monotone. We design a general two-phase framework to select seeds for profit maximization and develop several bounds to measure the quality of the seed set constructed. Experimental results with real OSN datasets show that our approach can achieve high approximation guarantees and significantly outperform the baseline algorithms, including state-of-the-art influence maximization algorithms.




§ INTRODUCTION

Information can be disseminated widely and rapidly through Online Social Networks (OSNs) (such as Facebook, Twitter, Flickr, Google+, and LinkedIn) with “word-of-mouth" effects. Viral marketing is a typical application that leverages OSNs as the medium for information diffusion <cit.>. The market of OSN advertisement is growing explosively. For example, Fortune <cit.> reports that the online and digital advertisement spending for the 2016 election of the United States will reach 1.2 billion US dollars in which 49% is expected to go to social media.

Advertisers often delegate the operation of viral marketing campaigns to OSN providers who have the complete information of their social network structures <cit.>. Providing viral marketing services is a potential and promising approach that OSN providers can explore for monetization. When hiring an OSN provider to conduct the viral marketing campaign, the advertiser usually pays the OSN provider a commission for each user that adopts its product or shares its ads. Thus, the revenue of the OSN provider generated from the commission is determined by the spread of the product information. Meanwhile, to propagate influence, the activities performed by users such as viewing video ads normally induce diffusion cost to the OSN provider. For example, for a cloud-based OSN running viral video marketing <cit.>, the OSN will be charged by the cloud for each video click due to the data traffic produced. Intuitively, the number of clicks for each video is dependent on the number of connections among users that are actually used during the viral marketing campaign. Therefore, to maximize its profit, the OSN provider needs to account for both the reward of influence spread and the expense of influence propagation, both of which are dependent on the seed users selected to initialize the viral marketing campaign. In this paper, we study the problem of finding a seed set to optimize such a new profit metric that combines the benefit of influence spread with the cost of influence propagation.

Our profit metric is challenging to optimize as it is significantly different from the influence metric that has been studied widely <cit.>. It is well known that the influence spread generated by a seed set is submodular and monotone under many diffusion models <cit.>, which makes it easy to design influence maximization algorithms with strong approximation guarantees <cit.>. Some recent studies have addressed profit maximization from the advertiser's perspective by putting together the benefit of influence spread and the cost of seed selection <cit.>. In these studies, the cost of seed selection is modeled by the incentives (e.g., free samples) provided to seed users. Since the seed selection cost is given by the sum of the costs of individual seeds which is modular, the resultant profit metric is still submodular. In contrast, in our problem, both the revenue and cost of the OSN provider are attached to the diffusion process. As a result, our profit metric can be viewed as the difference between two submodular functions, which is neither submodular nor monotone and is thus much more difficult to deal with. 

In this paper, we propose a general two-phase framework to optimize profit for the OSN provider. Our framework is comprised of a pruning phase that iteratively narrows down the search space and a search phase that uses heuristics to select seed nodes within the reduced search space. We theoretically establish the advantages of our pruning technique in improving the effectiveness and efficiency of any algorithm used in the search phase. We further derive several bounds on the maximum achievable profit to evaluate the quality of the seed sets obtained by any algorithm. We conduct extensive experiments with several real OSN datasets. The results demonstrate the effectiveness and efficiency of our framework.

The rest of this paper is organized as follows. Section <ref> reviews the related work. Section <ref> defines the profit maximization problem for the OSN provider. Section <ref> elaborates the design of our two-phase framework. Section <ref> develops the bounds for quality measurement. Section <ref> presents the experimental evaluation. Finally, Section <ref> concludes the paper.



§ RELATED WORK


Influence Maximization. 
Kempe et al. <cit.> formulated an influence maximization problem for a given seed set size with two basic diffusion models, namely the Independent Cascade (IC) and Linear Threshold (LT) models. They showed that the influence spreads under these models are submodular and monotone. Thus, they proposed a simple hill-climbing greedy algorithm to address the problem, which can provide a (1-1/e)-approximation guarantee <cit.>. The follow-up studies have mainly concentrated on improving the efficiency of the algorithm implementation for large-scale OSNs <cit.>. Different from the above studies, we target at maximizing the profit that accounts for both the benefit of influence spread and the cost of influence propagation in viral marketing.

Profit Maximization. 
Maximizing the influence spread alone has been shown to be ineffective for optimizing the profit return of viral marketing <cit.>. This is because the number of seeds selected yields a tradeoff between the expense and reward of viral marketing. To avoid pre-setting the number of seeds to select, some recent work studied profit maximization from the advertiser's perspective <cit.>. These studies considered the cost of seed selection which is modular and implies that their profit metric is still submodular. They investigated heuristics to select seeds under the assumption that the social network structures are available to the advertiser. In practice, only the OSN providers have the complete information of their social graphs and they often keep the formation secret for business and privacy reasons <cit.>. Therefore, the OSN providers are able to run viral marketing campaigns more efficiently than the advertisers. Different from the above work, we formulate a new profit maximization problem from the OSN provider's perspective that takes into account the cost of information diffusion over the social network. As shall be shown later, our profit metric is the difference between two submodular functions, which is neither submodular nor monotone. 

Submodular Optimization.
Iyer and Bilmes <cit.> investigated optimizing the difference between two submodular functions. They showed that this problem is multiplicatively inapproximable unless P=NP and proposed several heuristic methods to address the problem. The greedy algorithm <cit.> is another widely used heuristic for submodular optimization. We apply these heuristic methods to the search phase of our two-phase framework. More importantly, we develop an iterative pruning technique to reduce the search space which significantly improves these heuristics in terms of not only effectiveness but also efficiency. In addition, we also derive several upper bounds of the optimum to benchmark the output of any algorithm.



§ PROBLEM FORMULATION



 §.§ Preliminaries

Let G=(V,E) be a directed graph modeling an OSN, where the nodes V represent users and the edges E represent the connections among users (e.g., friendships on Facebook, followships on Twitter). For each directed edge ⟨u,v⟩∈E, we refer to v as a neighbor of u, and refer to u as an inverse neighbor of v.

There are many diffusion models for the processes by which influence propagates in social networks. The diffusion model is normally a random process that starts with a set of seed nodes S. Initially, the seed nodes S are activated, while all the other nodes are not activated. When a node u becomes activated, it would attempt to further activate its neighbors which are not yet activated. The diffusion process terminates when no more node can be further activated. Let g∼G be a sample outcome of influence propagation by the diffusion process and let V_g(S) be the set of nodes activated by the seed set S in the sample outcome g. The influence spread of the seed set S, denoted by σ(S), is the expected number of nodes activated over all possible sample outcomes of influence propagation, i.e., σ(S)=𝔼[|V_g(S)|].



 §.§ The Profit Maximization Problem

As discussed, the influence spread is the benefit gained by the OSN provider and the cost of influence propagation is the price to pay for viral marketing. We assume that each node v in the social network is associated with a benefit weight b(v), which represents the benefit offered by activating v (e.g., the commission received from the advertiser).
The benefit β(S) of influence spread generated by a seed set S is the total benefit brought by all the nodes activated:

    β(S)=𝔼[∑_v∈V_g(S)b(v)].

To model the cost of influence propagation, we consider the diffusion process in the social network. Recall that when a node is activated, it attempts to further activate its neighbors through the connections to them in the social network. Without loss of generality, we assume that each node v is associated with a cost weight c(v), which represents the cost of information diffusion incurred by v in attempting to activate its neighbors when it becomes activated (e.g., pushing video ads). The cost γ(S) of influence propagation introduced by a seed set S is the total cost incurred by all the nodes activated: 

    γ(S)=𝔼[∑_v∈V_g(S)c(v)].

Then, we naturally define a profit metric from OSN provider's perspective as the benefit of influence spread less the cost of influence propagation, i.e., the profit ϕ(S) for running a viral marketing campaign with a seed set S is given by

    ϕ(S)=β(S)-γ(S),

Our goal is to find a seed set S to maximize the profit ϕ(S).

By defining w(v)=b(v)-c(v), we can rewrite the profit metric in (<ref>) as

    ϕ(S)=𝔼[∑_v∈V_g(S)(b(v)-c(v))]≜𝔼[∑_v∈V_g(S)w(v)].

Here, w(v) represents the profit gain of activating a node v. If the benefit offered by v outweighs its cost, w(v) is positive. Otherwise, w(v) is negative. Therefore, we can normalize the benefit and cost weights of each node v by setting b̅(v)=max{0,w(v)} and c̅(v)=max{0,-w(v)}. Then, the benefit and cost metrics become 

    β̅(S)=𝔼[∑_v∈V_g(S)b̅(v)],
       and  γ̅(S)=𝔼[∑_v∈V_g(S)c̅(v)],

respectively. We show later that this normalized form can make the pruning phase of our proposed framework more effective.



It has been proved that the influence function σ(·) is submodular under many commonly used diffusion models due to V_g(S)⊆V_g(T) for any S⊆T <cit.>. Similarly, it can be shown that the benefit and cost metrics defined above are both submodular under these diffusion models. That is, for any two seed sets S and T where S⊆T and any node v∉T, it holds that β(S∪{v})-β(S)≥β(T∪{v})-β(T) and γ(S∪{v})-γ(S)≥γ(T∪{v})-γ(T). Likewise, the normalized β̅(·) and γ̅(·) are also submodular. Although both the benefit and cost metrics are monotone and submodular, the profit metric is neither monotone nor submodular (an example is given in  <ref>). Thus, the methods used for maximizing monotone submodular functions would perform poorly for our profit maximization problem as shall be shown in our experiments. In the following, we develop heuristic algorithms to address our profit maximization problem.


	 <ref> gives an example to illustrate that the profit function ϕ(·) is neither monotone nor submodular. In this example, once a node is activated, it will activate all of its neighbors. It can be seen from the figure that ϕ(∅)=0, ϕ({v_1})=-1.5, ϕ({v_3})=-1 and, ϕ({v_1,v_3})=0.5. Thus, ϕ(∅)>ϕ({v_1}) and ϕ({v_1})<ϕ({v_1,v_3}), which indicates that ϕ(·) is non-monotone. In addition, we can also get that ϕ({v_1})-ϕ(∅)=-1.5 < ϕ({v_1,v_3})-ϕ({v_3})=1.5, which indicates that ϕ(·) is non-submodular.




§ TWO-PHASE FRAMEWORK

We propose a general two-phase framework to select seed nodes for optimizing the profit.

	
  * Pruning phase (Algorithm <ref>): We develop an iterative pruning technique to cut the search space.
	
  * Search phase (Algorithms <ref> and <ref>): We use some heuristics to find the solution in the reduced search space.




 §.§ Prune Search Space

To simplify the notations, we define the marginal gain of adding a node v to a seed set S for metrics ϕ, β and γ as

    ϕ(v|S)=ϕ(S∪{v})-ϕ(S),
       β(v|S)=β(S∪{v})-β(S),
       γ(v|S)=γ(S∪{v})-γ(S).




We start by proposing an iterative pruning approach that can dramatically reduce the search space from the power set of V to a smaller lattice for maximizing the profit function. Algorithm <ref> shows the pseudo code of the pruning algorithm. Recall that by the submodularity of the benefit and cost metrics, their marginal gains for adding a new seed node decrease with the base seed set. Thus, the largest possible benefit (cost) gain is produced by adding a node into an empty seed set, whereas the smallest possible benefit (cost) gain is generated by adding the node into an almost universal set. Note that the marginal profit gain is bounded below by the smallest benefit gain less the largest cost gain. So, it is intuitive that if the latter is positive, the node must be selected in an optimal solution. Similarly, the marginal profit gain is bounded above by the largest benefit gain less the smallest cost gain. If the latter is negative, the node cannot be selected in an optimal solution. Algorithm <ref> extends this idea in an iterative manner to reduce the search space. It is easy to verify that after each iteration, the newly generated lattice is a sublattice of that in the previous iteration, i.e., A_t⊆A_t+1⊆B_t+1⊆B_t. Furthermore, it can be proved that any seed set outside the resultant lattice [A^∗,B^∗] delimited by the node sets A^∗ and B^∗ returned by Algorithm <ref> can be transformed to a seed set in [A^∗,B^∗] with higher profit. The formal proofs of all the theoretical results in this paper are given in the appendix.

	For any node set S and t≥ 0, let S_t=S∩B_t∪A_t, it holds that ϕ(S_t)≤ϕ(S_t+1),
	where the “=” holds if and only if S_t=S_t+1.


Theorem <ref> shows that the pruning technique can only increase the profit value of the seed set S_t=S∩B_t∪A_t at every iteration. The following corollary shows how our search space reduction improves the quality of any solution.

	For any node set S, if S∉[A^∗,B^∗], then ϕ(S)<ϕ(S∩B^∗∪A^∗).


By Corollary <ref>, the pruning approach can always improve the quality of any seed set S outside [A^∗,B^∗] by transforming it to the seed set S∩B^∗∪A^∗ in [A^∗,B^∗]. Thus, the lattice [A^∗,B^∗] retains all the optimal seed sets. As a result, we can reduce the search space from the lattice [∅,V] to [A^∗,B^∗]. Our pruning approach can be used prior to any seed selection algorithms to improve the solution quality.

	
	For any seed set S^∗ producing the maximum achievable profit, it holds that A^∗⊆S^∗⊆B^∗. 





	 <ref> gives an example to illustrate how the pruning algorithm works as well as the above theorem and corollaries. This example assumes the Independent Cascade (IC) diffusion model. The IC model is a representative and most widely-studied diffusion model for influence propagation <cit.>. In the IC model, a propagation probability p_u,v is associated with each edge ⟨u,v⟩, representing the probability for v to be activated by u through their connection. In the diffusion process, when a node u first becomes activated, it has a chance to activate its neighbors who are not yet activated. Each such neighbor v would become activated with probability p_u,v. This process repeats until no more node can be activated. For example, in  <ref>, when {v_1,v_3} are selected as seeds, v_2 would be activated with probability 0.3. Meanwhile, v_4 would be activated by v_1 with probability 0.4, by v_2 with probability 0.3× 0.2=0.06, and by v_3 with probability 0.3. Thus, overall, v_4 would be activated  with probability 1-(1-0.4)×(1-0.06)×(1-0.3)=0.6052.
	
	To conduct iterative pruning, A_0 is initialized by ∅ and B_0 is initialized by {v_1,v_2,v_3,v_4} respectively. To simplify the notations, let ϕ^-_t(v)=β(v|B_t∖{v})-γ(v|A_t) and ϕ^+_t(v)=β(v|A_t)-γ(v|B_t∖{v}) describe the calculations in Algorithm <ref>. At iteration 1, ϕ^-_1(v_1)=β(v_1|{v_2,v_3,v_4})-γ(v_1|∅)=1× b(v_1)-(1× c(v_1)+0.3× c(v_2)+(1-(1-0.4)×(1-0.3× 0.2))× c(v_4))=1.5-(1+0.3+2.18)=1.5-3.48=-1.98<0. Similarly, ϕ^-_1(v_2)=-0.6<0, ϕ^-_1(v_3)=0.5>0, ϕ^-_1(v_4)=-4.328<0, ϕ^+_1(v_1)=1.972>0, ϕ^+_1(v_2)=1.7>0, ϕ^+_1(v_3)=2.6>0, and ϕ^+_1(v_4)=0.32>0. Thus, v_3 is added to A_1 so that A_1={v_3} and B_1={v_1,v_2,v_3,v_4}. At iteration 2, ϕ^-_2(v_1)=-1.326<0, ϕ^-_2(v_2)=-0.3<0, ϕ^-_2(v_4)=-2.828<0, ϕ^+_2(v_1)=1.7104>0, ϕ^+_2(v_2)=1.58>0, and ϕ^+_2(v_4)=-0.28<0. Thus, v_4 is removed from B_2 so that A_2={v_3} and B_2={v_1,v_2,v_3}. At iteration 3, ϕ^-_3(v_1)=-0.878<0, ϕ^-_3(v_2)=-0.1824<0, ϕ^+_3(v_1)=0.5904>0, and ϕ^+_3(v_2)=1.286>0. Thus, both A_3 and B_3 remain the same as in the previous iteration. As a result, A^∗={v_3} and B^∗={v_1,v_2,v_3} are returned. For a seed set S={v_2,v_4}∉[A^∗,B^∗], we have S_1=S∩B_1∪A_1={v_2,v_3,v_4} and S_2=S_3=S∩B^∗∪A^∗={v_2,v_3}. Then, it can be obtained that ϕ(S)=-2<ϕ(S_1)=0<ϕ(S_2)=1.68, which demonstrates Theorem <ref> and Corollary <ref>. Moreover, it is easy to verify that the optimal seed set S^∗={v_2,v_3} belongs to [A^∗,B^∗], which confirms Corollary <ref>.


Finally, it can be shown that normalizing the benefit and cost weights as described in Section <ref> can only increase the amount of the search space cut by our pruning technique.


	Let A̅^∗ and B̅^∗ be the node sets returned by Algorithm <ref> under the normalized form. Then, A^∗⊆A̅^∗⊆B̅^∗⊆B^∗.


We shall experimentally evaluate the additional reduction in the search space due to normalization in Section <ref>.



 §.§ Heuristic Algorithms

We now present some heuristic methods to address the profit maximization problem since there does not exist any polynomial time algorithm with any polynomial time multiplicative approximation guarantees unless P=NP <cit.>.

Greedy Algorithm: 
We apply a simple hill-climbing idea to optimize the profit function (<ref>). Algorithm <ref> describes the pseudo code. In each iteration, the greedy heuristic adds a new node u to S that has the largest marginal profit gain ϕ(u|S) until all the remaining nodes have negative marginal gains.



Modular-Modular Algorithm: 
Iyer and Bilmes <cit.> introduced a modular-modular (ModMod) algorithm for optimizing the difference between submodular functions. Since we just need to search the lattice [A^∗,B^∗] after pruning, we adapt the ModMod algorithm as shown in Algorithm <ref>. In line <ref> of Algorithm <ref>, h_X^t^π(Y;β) is a modular lower bound of β(Y) that is tight at set X^t, i.e., h_X^t^π(Y;β)≤β(Y) for any Y⊆V and h_X^t^π(X^t;β)=β(X^t), while m_X^t(X^t;γ) is a modular upper bound of γ(Y) that is also tight at X^t, i.e., m_X^t(Y;γ)≥γ(Y) for any Y⊆V and m_X^t(X^t;γ)=γ(X^t). Thus, the difference h_X^t^π(Y;β)-m_X^t(Y;γ) is a lower bound of the profit function ϕ(Y). The algorithm maximizes the lower bound in each iteration. Since the lower bound is tight at Y=X^t, it is guaranteed that ϕ(X^t+1)≥ h_X^t^π(X^t+1;β)-m_X^t(X^t+1;γ) ≥ h_X^t^π(X^t;β)-m_X^t(X^t;γ)=ϕ(X^t). This indicates that Algorithm <ref> always increases the profit value at every iteration. Examples of the modular upper and lower bounds will be given in Section <ref>.





 §.§ Discussions

Time Complexity:
Evaluating the profit metric involves estimating the influence spread given a seed set. Any existing influence estimation methods, such as Monte-Carlo simulation <cit.> and reverse influence sampling <cit.>, can be used. Suppose the time complexity for computing the marginal profit gain of adding/removing a node into/from a seed set is O(M). For the iterative pruning process (Algorithm <ref>), the size of the node set B_t∖A_t to check reduces by at least 1 in each iteration. Therefore, it takes at most O((|V|+|V|-1+…+1)M)=O(|V|^2M) time to find A^∗ and B^∗. After the reduction of the search space, there are k_1=|B^∗∖A^∗| nodes to be further examined. For the Greedy algorithm, it checks k_1-i+1 nodes in the ith iteration. Thus, it takes at most O(k_1^2M) time, which means the total time complexity of the Greedy algorithm is O((|V|^2+k_1^2)M). Each iteration of the ModMod algorithm has a time complexity of O(k_1M). Let k_2 denote the total number of iterations used for the ModMod algorithm. Then, the total time complexity of the ModMod algorithm is O((|V|^2+k_1k_2)M).

Diffusion Models:
Our analysis and algorithms are general frameworks that can be adapted to any diffusion models which are submodular, such as the Independent Cascade and Linear Threshold models, the triggering model <cit.>, the continuous-time models <cit.>, and the topic-aware models <cit.>.



§ PERFORMANCE ANALYSIS

The challenges to evaluate the quality of the seed set constructed for the profit maximization problem are two-fold. First, optimizing the difference between two submodular functions is multiplicative inapproximability unless P=NP. Thus, it is difficult to measure the gap between the seed set obtained and an optimal seed set. Second, the random processes of many diffusion models are analytically intractable. For example, computing the exact influence spread under the IC diffusion model is #P-hard <cit.>. Thus, the benefit brought and the cost incurred by a seed set can only be estimated via some sampling approaches <cit.>. As a result, the sampling error also affects the quality measurement of the seed set.

We propose techniques to analyze the aforementioned gap and sampling error, which enable us to evaluate the approximation guarantee of the seed set obtained by any algorithm on any given instance of the profit maximization problem. Specifically, let S^o be the seed set constructed for a problem instance. We develop an upper bound μ on the maximum achievable profit for the problem instance to characterize the gap between the real profit value ϕ(S^o) and the maximum achievable profit. Note that both ϕ(S^o) and μ are to be estimated by sampling. Let ϕ̃(S^o) and μ̃ be their estimated values. We further study the sampling errors to bound the difference between ϕ̃(S^o) and ϕ(S^o) and the difference between μ̃ and μ. In this way, we can obtain an approximation guarantee of S^o using the estimated values ϕ̃(S^o) and μ̃.



 §.§ Upper Bound of Maximum Achievable Profit

To derive our bounds on the maximum achievable profit, we first introduce two modular bounds for submodular functions.

Modular Upper Bounds:
For any submodular set function f(·), we have the following two modular upper bounds m_X^1 and m_X^2 that are tight at a given set X <cit.>:

    m_X^1(Y)≜ f(X)-∑_v∈X∖Yf(v|V∖{v})+∑_v∈Y∖Xf(v|X),
       m_X^2(Y)≜ f(X)-∑_v∈X∖Yf(v|X∖{v})+∑_v∈Y∖Xf(v|∅).

In the previous section, we have reduced the search space so that only the sets belonging to [A^∗,B^∗] need to be considered for profit maximization. As a result, for any A^∗⊆X,Y⊆B^∗, the above two upper bounds can be improved to:
[4]

    m_X^3(Y)≜ f(X)-∑_v∈X∖Yf(v|B^∗∖{v})+∑_v∈Y∖Xf(v|X),
       m_X^4(Y)≜ f(X)-∑_v∈X∖Yf(v|X∖{v})+∑_v∈Y∖Xf(v|A^∗).

It is easy to show that the bounds m_X^3(Y) and m_X^4(Y) remain tight at X, i.e., m_X^3(X)=m_X^4(X)=f(X), and they are tighter than m_X^1(Y) and m_X^2(Y) at other sets, i.e., m_X^1(Y)≥ m_X^3(Y)≥ f(Y) and m_X^2(Y)≥ m_X^4(Y)≥ f(Y) for any A^∗⊆Y⊆B^∗.

Modular Lower Bounds: 
For any submodular set function f(·), a modular lower bound h_X that is tight at a given set X can be obtained as follows <cit.>. Let π be any permutation of V that places all the nodes in X before the nodes in V∖X. Let S^π_i={π(1),π(2),⋯,π(i)} be a chain formed by the permutation, where S^π_0=∅ and S^π_|X|=X. Define  

    h_X^π(π(i)) = f(S^π_i)-f(S^π_i-1).

Then, h_X^π(Y)=∑_v∈Y h_X^π(v) is a lower bound of f(Y), which is tight at X, i.e., h_X^π(Y)≤ f(Y) for any Y⊆V and h_X^π(X)=f(X). After the search space is reduced to [A^∗,B^∗], we restrict π to any permutation of V in the order of A^∗, X∖A^∗ and B^∗∖X.

Upper Bounds on Maximum Achievable Profit: 
Based on the above bounds, we can derive two series of upper bounds on the maximum value of the profit function ϕ(·) as follows. For any set X where A^∗⊆X⊆B^∗, we define 

    μ_i(X)≜max_A^∗⊆Y⊆B^∗m_X^i(Y;β)-h_X^π(Y;γ),

where m_X^i(Y;β) (i=3,4) denotes the modular upper bound on the benefit function β and h_X^π(Y;γ) denotes the modular lower bound on the cost function γ respectively. For briefness, we shall use μ(X) to refer to either bound with i=3 or 4 in the rest of the paper. 

	 
	For any set X where A^∗⊆X⊆B^∗,
	
    μ(X)≥max_S⊆Vϕ(S).



The upper bounds established above can be computed very fast since m_X^i(Y;β) and h_X^π(Y;γ) are both modular functions with respect to Y. It is much easier to find the maximum value for a modular function than that for a submodular function. We can obtain upper bounds by arbitrarily choosing the set X in μ(X). Given a seed set solution S^o obtained by any algorithm, we simply choose X=S^o. Then, the approximation guarantee of S^o can be estimated by ϕ(S^o)/μ(S^o).



 §.§ Sampling Error

To estimate ϕ(S^o) and μ(S^o), we make use of a state-of-the-art technique called reverse influence sampling <cit.>.


	A random reverse reachable (RR) set R for a weighted graph G is generated by (1) first selecting a random node v∈V with a probability distribution p(·) proportional to the node weights, (2) then sampling a graph g randomly from G according to the diffusion model, (3) finally taking the set of nodes in g that can reach v as R.


Taking our benefit metric as an example, the probability for choosing a node v in a random RR set is given by p(v)=b(v)/Υ_b, where Υ_b=b(V)=∑_v∈Vb(v) is the total benefit weight of all nodes. For a seed set S, the relation between its benefit and a random RR set R is β(S)=Υ_b·[S∩R≠∅], where [S∩R≠∅] is the probability that R contains at least one node in S <cit.>. Similarly, we can estimate the diffusion cost γ(S) by choosing each node in a random RR set with a probability proportional to the cost of the node, i.e., p(v)=c(v)/Υ_c, where Υ_c=c(V)=∑_v∈Vc(v) is the total cost weight of all nodes. Therefore, we generate two groups of RR sets to estimate the benefit and cost respectively for a seed set.

Suppose that we generate a total of θ_β random RR sets to estimate the benefit brought by a seed set S. An RR set is said to be covered by S if it contains at least one node in S. Let Λ_β(S) denote the number of RR sets covered by S among the θ_β random RR sets. Then, the benefit brought by S can be estimated as Λ_β(S)·Υ_b/θ_β. To analyze the sampling error, we make use of the Chernoff-Hoeffding Theorem <cit.>.

	Let Z_1,Z_2,…,Z_θ denote random variables that are independently and identically distributed according to Z in the interval [0,1] with mean 𝔼[Z]. For any fixed θ>0 and ε>0,
	
    [∑_i=1^θZ_i - θ·𝔼[Z]≥ε]≤exp(-ε^2/4(e-2)θ𝔼[Z]),
       [∑_i=1^θZ_i - θ·𝔼[Z]≤ -ε]≤exp(-ε^2/4(e-2)θ𝔼[Z]).



Based on Lemma <ref>, we can establish the following relation between Λ_β(S) and the real benefit β(S).


	For θ_β random RR sets that are independent of S and any δ∈(0,1), we have
	
    [β(S)≥(√(Λ_β(S)+0.25a) - 0.5√(a))^2·Υ_b/θ_β]≥ 1-δ/2,
       [β(S)≤(√(Λ_β(S)+0.25a)+0.5√(a))^2·Υ_b/θ_β]≥ 1-δ/2,

	where a=4(e-2)ln(2/δ).


According to Theorem <ref>, given Λ_β(S), we can define a lower bound and an upper bound of β(S) with a probability at least 1-δ/2 as

    β_l(S)≜(√(Λ_β(S)+0.25a) - 0.5√(a))^2·Υ_b/θ_β,
    β_u(S)≜(√(Λ_β(S)+0.25a)+0.5√(a))^2·Υ_b/θ_β.


The above analysis can also be applied to the estimation of the cost. Let θ_γ denote the number of random RR sets generated to estimate the cost incurred by a seed set S. Let Λ_γ(S) denote the number of RR sets covered by S among the θ_γ random RR sets. Then, the cost incurred by S can be estimated as Λ_γ(S)·Υ_c/θ_γ. We can similarly define a lower bound γ_l(S) and an upper bound γ_u(S) on the real cost γ(S) with a probability at least 1-δ/2. Then, given a seed set solution S^o obtained by any algorithm, we can derive a lower bound β_l(S^o)-γ_u(S^o) on its real profit ϕ(S^o) such that [ϕ(S^o)≥β_l(S^o)-γ_u(S^o)]≥[(β(S^o)≥β_l(S^o))∧(γ(S^o)≤γ_u(S^o))]=1-[(β(S^o)< β_l(S^o))∨(γ(S^o)>γ_u(S^o))]≥1-(δ/2+δ/2)>1-δ.

The difficulty in analyzing the sampling error for the upper bound μ(S^o) of the maximum achievable profit lies in that we can never find a specific seed set to achieve the upper bound. From Theorem <ref>, we know that the profit of any seed set S is bounded above by β_u(S)-γ_l(S) with a high probability. By definition, β_u(S)-γ_l(S) is a function of Λ_β(S) and Λ_γ(S). Let ϕ̃(S) be the estimated profit of S on the RR sets generated, which is defined by ϕ̃(S)=Λ_β(S)·Υ_b/θ_β-Λ_γ(S)·Υ_c/θ_γ. Then, β_u(S)-γ_l(S) can be represented as a function η of Λ_β(S) and ϕ̃(S), i.e., η(Λ_β(S),ϕ̃(S)). We can prove that η(Λ_β(S),ϕ̃(S)) is increasing with both Λ_β(S) and ϕ̃(S). Naturally, Λ_β(S) is bounded above by θ_β. On the other hand, thanks to the submodularity of the set coverage used to estimate the benefit and cost metrics in the reverse influence sampling approach, we can easily get the estimated upper bound μ̃(S^o) on the maximum achievable profit from the RR sets generated according to the analysis in Section <ref>. As a result, for any seed set S, the upper bound η(Λ_β(S),ϕ̃(S)) of its profit is bounded above by η(θ_β,μ̃(S^o)). In this way, we can obtain the sampling error for the upper bound μ(S^o).

	For any δ∈(0,1), we have 
	
    [max_S⊆Vϕ(S)≤μ̃(S^o)+ε(μ̃(S^o))]≥ 1-δ,

	where ε(μ̃(S^o)) is the sampling error for μ̃(S^o) such that ε(μ̃(S^o))=ρ_γ√(a((ρ_βθ_β-μ̃(S^o))/ρ_γ+0.25a))+0.5a(ρ_β-ρ_γ)+ρ_β√(a(θ_β+0.25a)), and ρ_β=Υ_b/θ_β and ρ_γ=Υ_c/θ_γ.


By Theorems <ref> and <ref>, we have the approximation guarantee that

    ϕ(S^o)/max_S⊆Vϕ(S)≥β_l(S^o)-γ_u(S^o)/μ̃(S^o)+ε(μ̃(S^o))

with a probability at least 1-2δ.



 §.§ Reduce Sampling Error via Normalization

As discussed in Section <ref>, we can normalize the benefit and cost weights by b̅(v) and c̅(v) for every node v∈V. Intuitively, the normalization can avoid unnecessary samples conducted by the weights ∑_v∈Vmin{b(v),c(v)} for the estimations of both the benefit and cost. Therefore, the normalization can reduce the sampling error by increasing the number of useful samples. 


	For any seed set S and a fixed number of samples, let ε_ϕ be the sampling error limit that can provide a probability guarantee of 1-δ, i.e., [-ε_ϕ≤ϕ̃(S)-ϕ(S)≤ε_ϕ]≥ 1-δ, and let ε̅_ϕ be the sampling error limit under the normalized form. We have ε̅_ϕ≤ε_ϕ.


Theorem <ref> indicates that the normalization can improve the solution quality which shall be demonstrated in the experiments.



§ EVALUATION








 §.§ Experimental Setup

Datasets. We use several real social networks available at <cit.> to evaluate our proposed techniques. Due to space limitations, we report here the results for two representative datasets, Google+ (108K nodes, 14M edges), and LiveJournal (5M nodes, 69M edges).

Algorithms. Recall that the ModMod algorithm needs a modular lower bound of the benefit function β(·) and a modular upper bound of the cost function γ(·). In Section <ref>, we have presented one such lower bound and two such upper bounds. We use ModMod-1 to refer to that using the upper bound m_X^3(Y) defined in Eq. (<ref>) and use ModMod-2 to refer to that using the upper bound m_X^4(Y) defined in Eq. (<ref>). We compare our two-phase methods with the following baselines.


	
  * Random: It randomly selects k nodes. We run the algorithm 10 times and take their average as the expected profit. 
	
  * HighDegree: It selects k nodes with the highest degrees.
	
  * BenefitMax: It makes use of the reverse influence sampling technique to find the top-k influential nodes for influence/benefit maximization <cit.>.

The above baselines are executed on the entire social networks without applying any pruning technique. To explore different seed numbers, in each baseline, we iterate through k=|V|/2^i for i=0,1,…,10 (where |V| is the network size) and choose the k value producing the largest profit.

Parameter Settings. By default, we use the IC diffusion model (as described in Example <ref> of Section <ref>), a uniform benefit distribution (where every node has a unit benefit to model the commission paid by the advertiser for each user activated), and a degree-proportional cost distribution (where the cost of each node is set proportional to its out-degree to emulate the diffusion cost for each activated user to push the product advertisement to all of his neighbors). In the IC model, we set the propagation probability p_u,v of each edge ⟨u,v⟩ to the reciprocal of v's in-degree (the number of v's inverse neighbors) as widely adopted by other studies <cit.>. 

By default, we normalize the benefit and cost weights as described in Section <ref>. We use a scale factor r to control the ratio between the total cost and total benefit of all nodes. A higher r implies a higher cost of influence propagation relative to the benefit of influence spread. The default value of r is set to 1. We have tested a wide range of r values and observed similar performance trends. In executing our two-phase methods and the baseline BenefitMax algorithm, we vary the number of RR sets generated to study the impact of benefit and cost estimations. To evaluate the profits of the seed sets returned by different algorithms, we generate a group of validation RR sets to keep the estimation errors within 1% with a high probability at least 1-10^-6 according to Theorem <ref>.



 §.§ Profits Produced by Different Algorithms


 <ref> shows the profits produced by different algorithms. Comparing the seed selection algorithms, our heuristic algorithms are more effective in optimizing the profit than the three baseline algorithms (Random, HighDegree and BenefitMax) on the datasets tested. This suggests that improving the influence spread or benefit alone is not effective for maximizing the profit. Our three heuristic algorithms perform quite close in terms of the profit produced. It can also be seen that with increasing number of RR sets generated for profit estimation in the seed selection process, the solution quality of our heuristics is improved due to lower estimation errors.



 §.§ Running Times of Different Algorithms

 <ref> shows the running times of different algorithms. The algorithms are all implemented in C++ and the experiments are carried out on a machine with an Intel Xeon E5-1650 3.2GHz CPU and 16GB memory. The time spent for generating RR sets is common to all our heuristics as well as BenefitMax. We plot it as a separate curve and exclude it from the running times of all the algorithms in  <ref>. It can be seen that generating the RR sets takes significant time. The Random and HighDegree algorithms do not need benefit and cost estimations. Thus, their running times are independent of the number of RR sets. The other four methods have running times increasing almost linearly with the number of RR sets (note that both axes are in logscale). In most cases, our heuristic methods complete execution within 100 seconds even for the LiveJournal dataset with millions of nodes. This shows the efficiency of our two-phase algorithms.



 §.§ Iterative Pruning Technique



Table <ref> shows the amount of search space reduction by the iterative pruning technique proposed in Section <ref>. These results are for the experiments with 2^10× 10,000 RR sets generated. As can be seen, the pruning technique substantially reduces the number of nodes that need to be considered for seed selection. Specifically, the search space is reduced by 98.3% and 83.7% of the original network size for the Google+ and LiveJournal datasets respectively when the normalization is applied. On the other hand, the reduction is much less when the normalization is not applied (67.6% and 38.3% for the Google+ and LiveJournal datasets respectively). This observation confirms Theorem <ref>. 

 <ref> shows the impact of the search space reduction on the profit produced and the running time of our heuristics, where O-X refers to heuristic X without the search space reduction. As claimed in Corollary <ref>, the pruning technique can help improve all the heuristic algorithms in terms of the profit produced. This is confirmed by the experimental results. For the LiveJournal dataset ( <ref>), the Greedy algorithm even produces negative profit without pruning the search space first, and the pruning technique can bring improvements up to 24.1% and 14.3% for the ModMod-1 and ModMod-2 algorithms respectively. Furthermore, the pruning technique can also help reduce the running time considerably. By pruning the search space first, our heuristic algorithms can run up to 3 orders faster. These observations demonstrate the effectiveness of our pruning technique.



 §.§ Guarantee of Solution Quality


We evaluate the quality of the seed sets returned by different algorithms using the techniques presented in Section <ref>. In our evaluation, we always choose the tighter bound between μ_3(X) and μ_4(X) as defined in (<ref>). We set δ=10^-6 so that the approximation guarantees obtained by (<ref>) have high confidence. Table <ref> shows the approximation guarantees derived for the seed sets constructed with 2^10× 10,000 RR sets generated. As can be seen, the seed sets constructed by our algorithms have approximation guarantees above 98% and 70% for the Google+ and LiveJournal datasets respectively. This implies that (i) our proposed upper bounds on the maximum achievable profit are quite tight, and (ii) the heuristic algorithms perform rather close to the optimal.



 §.§ Normalization



In Section <ref>, we have shown that the normalization can increase the amount of search space reduction by the pruning technique. Now, we further evaluate the impact of normalization on the profit.  <ref> shows the profit produced by the Greedy algorithm with and without the normalization. The results for the ModMod algorithms are similar. As can be seen, no matter whether the pruning technique is used, the Greedy algorithm with normalization can always produce higher profit than that without normalization. This confirms Theorem <ref> that the normalization can reduce the sampling error limit and thus, it can further improve the solution quality.



§ CONCLUSION

In this paper, we have studied a profit maximization problem for OSN providers conducting viral marketing. The objective is to select initial seed nodes to maximize the total profit that accounts for both the benefit of influence spread and the cost of influence propagation. We have proposed a two-phase framework that first reduces the search space via an iterative pruning technique and then finds the solution via some heuristic algorithms. We have presented several bounds to measure the quality of the solution obtained by any algorithm. Experimental results with real OSN datasets demonstrate the effectiveness and efficiency of our techniques, and show the tightness of our derived upper bounds.



§ ACKNOWLEDGMENT

This research is supported by Singapore Ministry of Education Academic Research Fund Tier 1 under Grant 2017-T1-002-024 and Tier 2 under Grant MOE2015-T2-2-114.

IEEEtranS




§ APPENDIX


	A_t⊆A_t+1⊆B_t+1⊆B_t for any t≥ 0.

[Proof of Lemma <ref>]
	By the definitions in lines <ref> and <ref> of Algorithm <ref>, A_t gradually expands over iterations and B_t gradually shrinks, i.e., A_t⊆A_t+1 and B_t+1⊆B_t. What is left is to show that A_t is always a subset of B_t. We prove it by induction. Obviously, A_0=∅⊆V=B_0. Suppose that A_t⊆B_t holds for some t≥ 0. Then, we can easily get that A_t⊆B_t+1 by the definition in line <ref> of Algorithm <ref> and that A_t+1⊆B_t by the definition in line <ref> of Algorithm <ref>. On the other hand, for any node v∈B_t∖A_t, it is obvious that A_t⊆B_t∖{v}. Thus, for any node v∈A_t+1∖A_t⊆B_t∖A_t, we have β(v|A_t)-γ(v|B_t∖{v})≥β(v|B_t∖{v})-γ(v|A_t)>0, where the first inequality is due to the submodularity of β(·) and γ(·) and the second inequality is by the definition of A_t+1 in line <ref> of Algorithm <ref>. It indicates that v∈B_t+1 as well. Therefore, A_t+1∖A_t⊆B_t+1, which implies A_t+1⊆B_t+1 since we already know that A_t⊆B_t+1. Thus, we can conclude that A_t+1⊆B_t+1.



[Proof of Theorem <ref>]
	By the definition of S_t, we easily have A_t⊆S_t⊆B_t. We already know that A_t⊆A_t+1⊆B_t+1⊆B_t by Lemma <ref>. Thus,
	[4]
	
    S_t+1   =S∩B_t+1∪A_t+1
       =S∩(B_t∖(B_t∖B_t+1))∪A_t+1
       =S∩B_t∖(S∩(B_t∖B_t+1))∪A_t+1
       =S∩B_t∪A_t+1∖(S∩(B_t∖B_t+1)∖A_t+1)
       =S∩B_t∪A_t+1∖(S∩(B_t∖B_t+1))
       =S∩B_t∪A_t∪(A_t+1∖A_t)∖(S∩(B_t∖B_t+1))
       =S_t∪(A_t+1∖A_t)∖(S∩(B_t∖B_t+1)).

	By line <ref> of Algorithm <ref>, for any node v∈A_t+1∖A_t, it holds that β(v|B_t∖{v})-γ(v|A_t)>0. Then, for any S_t⊆T⊆S_t∪(A_t+1∖A_t), since A_t⊆T and T⊆B_t∖{v}, we have ϕ(v|T)=β(v|T)-γ(v|T)≥β(v|B_t∖{v})-γ(v|A_t)>0 due to the submodularity. Let v_1,v_2,…,v_k be the set of nodes in A_t+1∖A_t∖S_t. It follows that
	
    ϕ(S_t)
    	   <ϕ(S_t∪{v_1})
       <ϕ(S_t∪{v_1,v_2})
       <⋯
       <ϕ(S_t∪{v_1,v_2,…,v_k})
       =ϕ(S_t∪(A_t+1∖A_t∖S_t))
       =ϕ(S_t∪(A_t+1∖A_t)).

	Similarly, by line <ref> of Algorithm <ref>, for any node v∈B_t∖B_t+1, it holds that β(v|A_t)-γ(v|B_t∖{v})<0. Then, for any S_t∪(A_t+1∖A_t)∖(S∩(B_t∖B_t+1))⊆T⊆S_t∪(A_t+1∖A_t), since A_t⊆T and T⊆B_t∖{v}, we have ϕ(v|T)=β(v|T)-γ(v|T)≤β(v|A_t)-γ(v|B_t∖{v})<0 due to the submodularity. Let u_1,u_2,⋯,u_l be the set of nodes in S∩(B_t∖B_t+1). It follows that
	
    ϕ(S_t∪(A_t+1∖A_t))
       <ϕ(S_t∪(A_t+1∖A_t)∖{u_1})
       <ϕ(S_t∪(A_t+1∖A_t)∖{u_1,u_2})
       <⋯
       <ϕ(S_t∪(A_t+1∖A_t)∖{u_1,u_2,…,u_l})
       =ϕ(S_t∪(A_t+1∖A_t)∖(S∩(B_t∖B_t+1)))
       =ϕ(S_t+1),

	where the last equality is due to (<ref>). Therefore, ϕ(S_t)<ϕ(S_t+1) if A_t+1∖A_t∖S_t≠∅ or S∩(B_t∖B_t+1)≠∅. On the other hand, if A_t+1∖A_t∖S_t=S∩(B_t∖B_t+1)=∅, based on (<ref>), we have S_t=S_t+1.



[Proof of Corollary <ref>]
	According to Theorem <ref>, ϕ(S)=ϕ(S_0)≤ϕ(S_1)≤⋯≤ϕ(S∩B^∗∪A^∗) since S=S∩B_0∪A_0=S_0. On the other hand, if every “=” holds, we have S=S_0=S_1=⋯=S∩B^∗∪A^∗, which implies A^∗⊆S⊆B^∗. This is contradictory to S∉[A^∗,B^∗]. Thus, it holds that ϕ(S)<ϕ(S∩B^∗∪A^∗).



[Proof of Corollary <ref>]
	Suppose S^∗∉[A^∗,B^∗]. By Corollary <ref>, we have ϕ(S^∗)<ϕ(S^∗∩B^∗∪A^∗). This is contradictory to the fact that S^∗ produces the maximum achievable profit. Thus, it holds that A^∗⊆S^∗⊆B^∗.


[Proof of Theorem <ref>]
	Let α(S) denote the overlapping value between the benefit of influence spread and the cost of influence propagation for a seed set S, which is defined as
	
    α(S)=𝔼[∑_v∈V_X(S)min{b(v),c(v)}].

	It is easy to verify that α(·) is also submodular and monotone. By the definition of normalization in Section <ref>, we have β(S)=β̅(S)+α(S) and γ(S)=γ̅(S)+α(S). We prove that A_t⊆A̅_t⊆B̅_t⊆B_t for any t≥ 0 by induction. Obviously, it holds that ∅=A_0=A̅_0⊆B̅_0=B_0=V. Suppose that A_t⊆A̅_t⊆B̅_t⊆B_t holds for some t≥ 0. 
	
	Then, for any node v∈B_t∖B̅_t, we have β(v|B_t∖{v})-γ(v|A_t)=β̅(v|B_t∖{v})-γ̅(v|A_t)+α(v|B_t∖{v})-α(v|A_t)≤β̅(v|B_t∖{v})-γ̅(v|A_t)≤β̅(v|B̅_t∖{v})-γ̅(v|A̅_t), where the inequalities are due to the submodularity of α(·), β̅(·) and γ̅(·). By Lemma <ref>, A̅_t-1⊆A̅_t⊆B̅_t-1=B̅_t-1∖{v}⊆B̅_t∖{v}. It follows from the submodularity that β̅(v|B̅_t∖{v})-γ̅(v|A̅_t)≤β̅(v|A̅_t-1)-γ̅(v|B̅_t-1∖{v})<0, where the last inequality is due to v∉B̅_t. This implies that (A_t+1∖A_t)∩(B_t∖B̅_t)=∅. Since A_t+1∖A_t⊆B_t,  we have A_t+1∖A_t⊆B̅_t. Since A_t⊆B̅_t, it follows that A_t+1⊆B̅_t. Thus, for any node v∈A_t+1∖A̅_t⊆B̅_t∖A̅_t, we have β̅(v|B̅_t∖{v})-γ̅(v|A̅_t)≥β̅(v|B_t∖{v})-γ̅(v|A_t)=β(v|B_t∖{v})-γ(v|A_t)-α(v|B_t∖{v})+α(v|A_t)≥β(v|B_t∖{v})-γ(v|A_t)>0, where the first two inequalities are due to the submodularity and the last inequality is due to v∈A_t+1. This implies that A_t+1∖A̅_t⊆A̅_t+1. Since A̅_t⊆A̅_t+1, it follows that A_t+1⊆A̅_t+1.
	
	Similarly, for any node v∈A̅_t∖A_t, we have β(v|A_t)-γ(v|B_t∖{v})=β̅(v|A_t)-γ̅(v|B_t∖{v})+α(v|A_t)-α(v|B_t∖{v})≥β̅(v|A_t)-γ̅(v|B_t∖{v})≥β̅(v|A̅_t)-γ̅(v|B̅_t∖{v})≥β̅(v|B̅_t-1∖{v})-γ̅(v|A̅_t-1)>0, where the first three inequalities are due to the submodularity of α(·), β̅(·) and γ̅(·), and the last inequality is due to v∈A̅_t. This implies that A̅_t∖A_t⊆B_t+1. Since A_t⊆A_t+1⊆B_t+1, it follows that A̅_t⊆B_t+1. Thus, for any node v∈B̅_t∖B_t+1⊆B̅_t∖A̅_t, we have β̅(v|A̅_t)-γ̅(v|B̅_t∖{v})≤β̅(v|A_t)-γ̅(v|B_t∖{v})=β(v|A_t)-γ(v|B_t∖{v})-α(v|A_t)+α(v|B_t∖{v})≤β(v|A_t)-γ(v|B_t∖{v})<0, where the first two inequalities are due to the submodularity and the last inequality is due to v∉B_t+1. This implies that B̅_t+1∩(B̅_t∖B_t+1)=∅. Since B̅_t+1⊆B̅_t, it follows that B̅_t+1⊆B_t+1. 
	By induction, we have A_t⊆A̅_t⊆B̅_t⊆B_t for any t≥ 0 (it also holds after converged) and thus, A^∗⊆A̅^∗⊆B̅^∗⊆B^∗.



[Proof of Theorem <ref>]
	Let S^∗ be an optimal seed set producing the maximum achievable profit. We can directly obtain that μ_i(X)≥ m_X^i(S^∗;β)-h_X^π^∗(S^∗;γ)≥β(S^∗)-γ(S^∗)=ϕ(S^∗), where the first inequality is by the definition of μ_i(X) and the second inequality is due to the modular upper and lower bounds.



[Proof of Theorem <ref>]
	Let λ_β(S) be the expected fraction of samples covered by the seed set S. We have λ_β(S)=β(S)/B. To simplify the notation, we omit the common symbol S in what follows, e.g., β represents β(S) and Λ_β represents Λ_β(S). Then, the inequalities to prove are equivalent to 
    [λ_β<(√(Λ_β+0.25a) - 0.5√(a))^2/θ_β]≤δ/2,
 and 
    [λ_β>(√(Λ_β+0.25a) + 0.5√(a))^2/θ_β]≤δ/2.
 
	
	We prove the former first. In fact,
	
    [λ_β<(√(Λ_β+0.25a) - 0.5√(a))^2/θ_β]
         =[√(λ_βθ_β)<√(Λ_β+0.25a) - 0.5√(a)]
         =[(√(λ_βθ_β)+0.5√(a))^2<Λ_β+0.25a]
         =[Λ_β-λ_βθ_β>√(aλ_βθ_β)]
         ≤exp(-aλ_βθ_β/4(e-2)λ_βθ_β)
         =δ/2,

	where the inequality is due to Lemma <ref>.
	
	The proof of the latter is analogous.
	
    [λ_β>(√(Λ_β+0.25a) + 0.5√(a))^2/θ_β]
         =[√(λ_βθ_β)>√(Λ_β+0.25a) + 0.5√(a)]
         =[(√(λ_βθ_β)-0.5√(a))^2>Λ_β+0.25a]
         =[Λ_β-λ_βθ_β<-√(aλ_βθ_β)]
         ≤exp(-aλ_βθ_β/4(e-2)λ_βθ_β)
         =δ/2

	
	Hence, the theorem is proven.



[Proof of Theorem <ref>]
	Imagine that we evaluate S^∗ with the benefit and cost samples. By Theorem <ref>, we know that
	
    [ϕ(S^∗)≤β_u(S^∗)-γ_l(S^∗)]
       ≥[(β(S^∗)≤β_u(S^∗))∧(γ(S^∗)≥γ_l(S^∗))]
       ≥ 1-([β(S^∗)> β_u(S^∗)]+ [γ(S^∗)< γ_l(S^∗)])
       ≥1-(δ/2+δ/2)
       =1-δ.
 
	
	However, without knowing S^∗, β_u(S^∗) and γ_l(S^∗) cannot be obtained. In what follows, we are going to bound β_u(S^∗)-γ_l(S^∗) by an upper bound on the function η(S)=β_u(S)-γ_l(S). To simplify the notations, and we omit the common symbol S in what follows, e.g., η represents η(S). Then, the estimated profit ϕ̃=ρ_βΛ_β-ρ_γΛ_γ. Consider η as a function of ϕ̃ and Λ_β. We study the monotonicity of η with respect to ϕ̃ and Λ_β. By the definition of η, we have
	
    η(Λ_β,ϕ̃)
    	   =ρ_β(Λ_β+√(a(Λ_β+0.25a))+0.5a)
          -ρ_γ(Λ_γ-√(a(Λ_γ+0.25a))+0.5a)
       =ϕ̃+ρ_γ√(a((ρ_βΛ_β-ϕ̃)/ρ_γ+0.25a))
          +0.5a(ρ_β-ρ_γ)+ρ_β√(a(Λ_β+0.25a)).

	which is increasing with Λ_β under any given ϕ̃. Meanwhile, we also have
	
    η(Λ_β,ϕ̃)
    	   =ρ_β(√(Λ_β+0.25a)+0.5√(a))^2
          -ρ_γ(√(Λ_γ+0.25a)-0.5√(a))^2
       =ρ_β(√(Λ_β+0.25a)+0.5√(a))^2
          -ρ_γ(√((ρ_βΛ_β-ϕ̃)/ρ_γ+0.25a)-0.5√(a))^2,

	which is increasing with ϕ̃ under any given Λ_β.
	
	For an estimated upper bound μ̃(S^o) on the maximum achievable profit, we have ϕ̃(S^∗)≤μ̃(S^o). On the other hand, it naturally holds that Λ_β(S^∗)≤θ_β. Thus, 
	
    β_u(S^∗)-γ_l(S^∗)
       =η(Λ_β(S^∗), ϕ̃(S^∗))
       ≤η(θ_β, μ̃(S^o))
       =μ̃(S^o)+ρ_γ√(a((ρ_βθ_β-μ̃(S^o))/ρ_γ+0.25a))
          +0.5a(ρ_β-ρ_γ)+ρ_β√(a(θ_β+0.25a)).

	Hence, the theorem is proven.



[Proof of Theorem <ref>]
	Consider the sampling error limit ε under θ samples that can provide a probability guarantee of 1-δ, i.e., [-ε≤Λ-λθ≤ε]≥ 1-δ (where λ is the expected value of the random variable and Λ is the sum of θ samples). According to Lemma <ref>, ε is given by 
	
    ε=√(4(e-2)ln(2/δ)λθ)=√(aλθ),

	where a=4(e-2)ln(2/δ).
	
	We denote ε_β and ε_γ as the sampling error limits for the benefit and cost metrics under θ_β and θ_γ samples that can satisfy [-ε_β≤β̃(S)-β(S)≤ε_β]≥ 1-δ and [-ε_γ≤γ̃(S)-γ(S)≤ε_γ]≥ 1-δ. Then, ε_ϕ=ε_β+ε_γ gives a total sampling error limit for the profit metric which guarantees [-ε_ϕ≤ϕ̃(S)-ϕ(S)≤ε_ϕ]≥ 1-2δ. Likewise, let ε̅_β, ε̅_γ and ε̅_ϕ denote the sampling error limits under the normalized form. 
	
	Similar to the definitions of Υ_b and Υ_c, we define Υ̅_b=b̅(V)=∑_v∈Vb̅(v) and Υ̅_c=c̅(V)=∑_v∈Vc̅(v). Then, Υ̅_b-Υ̅_c=Υ_b-Υ_c. For a given seed set S, let λ̅_β(S) and λ̅_γ(S) denote the expected fractions of benefit and cost samples covered by S under the normalized form. To simplify the notation, we omit the common symbol S in what follows, e.g., β represents β(S) and λ̅_β represents λ̅_β(S). Since β=Υ_b/θ_β·λ_βθ_β, based on the definition of ε in (<ref>), we have
	
    ε_β=Υ_b/θ_β·ε=Υ_b√(aλ_βθ_β)/θ_β=√(aΥ_b^2λ_β/θ_β)=√(aΥ_bβ/θ_β).

	Similarly, we have
	
    ε̅_β=√(aΥ̅_bβ̅/θ_β),  ε_γ=√(aΥ_cγ/θ_γ)  and  ε̅_γ=√(aΥ̅_cγ̅/θ_γ).

	Note that Υ_b≥Υ̅_b, Υ_c≥Υ̅_c, β≥β̅ and γ≥γ̅. Together with (<ref>) and (<ref>), we have ε_β≥ε̅_β and ε_γ≥ε̅_γ. Therefore, ε_ϕ=ε_β+ε_γ≥ε̅_β+ε̅_γ=ε̅_ϕ.



