Pricing Social Visibility Service in Online Social Networks: Modeling and Algorithms

The pricing scheme. A “requester” is a user in the set $\mathcal{U}$ who seeks to increase his visibility by requesting other users to be his new incoming neighbors. Let $\mathcal{R}\subseteq\mathcal{U}$ denote a set of all requesters. A “supplier” is a user in the set $\mathcal{U}$ who is willing to be a new incoming neighbor of any requester. Let $\mathcal{S}\subseteq\mathcal{U}$ denote a set of all suppliers. For the ease of presentation, we assume that $\mathcal{R}\cap\mathcal{S}=\emptyset$, this captures that a user can not be both requester and supplier. We consider the general case that there are some users who are neither requesters nor suppliers, i.e., $\mathcal{R}\cup\mathcal{S}\subseteq\mathcal{U}$. The OSN operator provides a “social visibility boosting service” to incentivize the “transaction” between requesters and suppliers. The visibility improvement service is sold at via a posted pricing scheme $(p,q)$, where $p\in[0,1]$ and $q\in[0,1]$. Here, $p$ is the price of per unit social visibility improvement that the OSN operator charges a participating requester (i.e., requesters who use this social visibility boosting service), and $q$ is the price of per unit contribution in improving social visibility of participating requesters that the OSN operator pays to a participating supplier (i.e., add links to requesters). We consider the case that each participating supplier will add links to all participating requesters.

Requesters’ decision model. Each requester $u\in\mathcal{R}$ has a per unit valuation (i.e., the per unit price that requester $u$ is willing to pay) of $p_{u}\in[0,1]$ on the improvement of his social visibility. A requester will use the social visibility boosting service if his per unit valuation is not below the per unit price, i.e., $p_{u}\geq p$. Let $\widetilde{R}(p)$ denote a set of all participating requesters under price $p$, formally

Due to financial budget on boosting service, each requester can afford to add at most $b\in\mathbb{N}_{+}$ incoming neighbors.

Supplier’s decision model. Each supplier $u\in\mathcal{S}$ has a per unit valuation (i.e., the per unit price that supplier $u$ is willing to participate) of $q_{u}\in[0,1]$ on the per unit contribution in improving social visibility of participating requesters. Let $\mathcal{M}$ denote a set participating suppliers, where $|\mathcal{M}|\leq b$. Let $\widetilde{G}(p,\mathcal{M})$ denote the new graph after adding edges from participating suppliers to participating requesters. $\widetilde{G}(p,\mathcal{M})$ can be expressed as:

Let $I_{u}(p,\mathcal{M})$ denote the improvement of social visibility of requester $u\in\widetilde{R}(p)$. It can be expressed as:

Then, the total improvement of social visibility of all participating requesters is

In other words, all participating suppliers make a total contribution of $I(p,\mathcal{M})$ in social visibility enhancement. Quantifying $I(p,\mathcal{M})$ among participating suppliers is a non-trivial problem. There are two underlying challenges: (1) some participating suppliers may have a larger number of follower while others may have a small number of followers; (2) the network structure poses an externality effect, causing the contribution of participating suppliers being correlated. To incentivize suppliers to participate, one needs to divide $I(p,\mathcal{M})$ fairly among suppliers. Let $\phi$ denote a “fair” division mechanism, which prescribes a contribution denoted by $\phi_{u}(p,\mathcal{M})$ for each participating supplier. In order to avoid distracting readers, we defer the detail explanation of $\phi$ to the next section. Given the fair division mechanism $\phi$, a supplier is willing to participant in the social visibility boosting service if his per unit valuation does not exceed the per unit price that the OSN operator pays, i.e., $q_{u}\leq q$. Let $\widetilde{S}(p)$ denote a set of all potential participating suppliers under price $q$, formally

Optimal pricing to maximize revenue. Under the posted pricing scheme, the total payment made by all requesters to the OSN operator can be expressed as:

The total payment made by the OSN operator to all participating suppliers can be expressed as:

The revenue of the OSN operator is therefore:

We consider a proportional transaction fee scheme, i.e., the OSN operator keeps a fraction $(1-\alpha)$ of $G(p,\mathcal{M})$, where $\alpha\in(0,1)$. This is equivalent to imposing $q=\alpha p$. We next formulate a revenue maximization problem for the OSN operator to select $p,q$ and $\mathcal{M}$.

One can observe that the Problem 1 is a mixed optimization problem, i.e., with both continuous and set decision variables.

Hardness analysis. Recall that Problem 1 is a mixed optimization problem, i.e., with both continuous decision variables, i.e., $p$ and $q$, and set decision variables, i.e., $\mathcal{M}$. This implies that gradient based optimization methods does not work for Problem 1. To illustrate the hardness of Problem 1, we consider a sub-problem of Problem 1 with given pricing parameters $(p,q)$, which is stated as follows:

Namely, Problem 2 only selects the optimal set of suppliers to maximize the revenue of the OSN operator. Note that the set of potential participating suppliers $\widetilde{S}(q)$ is determined as $q$ is given. In the following theorem, we analyze its hardness.

Theorem 1 states that it is NP-hard to locate the optimal set of supplier for Problem 2. In other words, it is computationally expensive to locate the exact optimal set of supplier for Problem 2. Note that Problem 2 is a sub-problem of Problem 1. Namely, Problem 1 is harder than Problem 2. And therefore, locating the exact optimal solution for Problem 1 is computationally expensive. We resort to design approximation algorithms for Problem 1 with theoretical guarantee.

Our approach. To address Problem 1, we decompose it into two sub-problems, which each sub-problem serves as a subroutine. In particular, Problem 2 is the first sub-problem. As Theorem 1 shows that Problem 2 is NP-hard, we aim to design an approximation algorithm which we denote as OptSupplierSet$(p,q)$ (its detail is postpone to Section III-B). Algorithm OptSupplierSet$(p,q)$ takes the prices $(p,q)$ as an input, and returns an approximately optimal set of suppliers under $(p,q)$. We use OptSupplierSet$(p,q)$ as an oracle to search for the optimal pricing parameter $(p,q)$. Formally, we aim to solve the following sub-problem:

Note that OptSupplierSet$(p,q)$ returns an approximately optimal set of suppliers for each given $(p,q)$, Problem 3 returns an approximately optimal price. We aim to design an approximation algorithm for Problem 3, which we denote as OptPrice$(\texttt{OptSupplierSet})$ (its detail is postpone to Section III-C). One needs to supply OptPrice$(\texttt{OptSupplierSet})$ with algorithm OptSupplierSet, and OptPrice$(\texttt{OptSupplierSet})$ returns an approximately optimal $(p,q)$. We next proceed to present the design and analysis of OptSupplierSet$(p,q)$ and OptPrice$(\texttt{OptSupplierSet})$.

Submodular analysis. First, note that once $p$ and $q$ are given, the set of participating requesters $\widetilde{R}(p)$ and the set of potential participating suppliers $\widetilde{S}(p)$ are given. Our objective is to select $\mathcal{M}\in\widetilde{S}(p)$ with the constraint $\mathcal{M}\leq b$, so as to maximize the objective function of Problem 2, i.e., revenue $R(p,q,\mathcal{M})$, where $p$ and $q$ are given and $q=\alpha p$. When $q=\alpha p$, the $R(p,q,\mathcal{M})$ can be derived as:

where $l^{s}$ and $l^{e}$ are the start node and the end node of each link $l\in\mathcal{M}\times\widetilde{R}(p)$. Based on the above closed-form expression of $R(p,q,\mathcal{M})$, the following theorem shows the sub-modularity and monotonicity of $R(p,q,\mathcal{M})$ with respect to $\mathcal{M}$.

Theorem 2 states that $R(p,q,\mathcal{M})$ is monotonously increasing and submodular with respect to $\mathcal{M}$ for each given $p$ and $q$ with $q=\alpha p$.

The OptSupplierSet$(p,q)$ algorithm. Based on Theorem 2, Algorithm 1 specifies a greedy algorithm to implement OptSupplierSet$(p,q)$. The core idea of Algorithm 1 is that we select suppliers one by one. Each time we select the supplier that achieves the largest marginal improvement in the revenue.

Perfect search. Now we consider the case that given OptSupplierSet$(p,q)$ outlined in Algorithm 1, we can obtain exact optimal price $(p,q)$ for Problem 3. The objective is to understand the impact of the approximate optimal supplier set returned by OptSupplierSet$(p,q)$ on the optimal price $(p,q)$. We state this impact in the following theorem.

Discretized search. Note that $q=\alpha p$. We therefore discretize the domain of $p$, i.e., $[0,1]$, uniformly:

where $\epsilon\in(0,1]$ is price search step the The OSN operator can control $\epsilon$ to adjust the number of points in $\mathcal{A}(\epsilon)$. The OSN operator can use exhaustive search method to select the optimal price $\mathcal{A}(\epsilon)$, denoted by $p_{\text{DS}}^{\ast}$. Algorithm 2 outlines this discretized search algorithm. We denote $q_{\text{DS}}^{\ast}=\alpha p_{\text{DS}}^{\ast}$. The set of supplier is then $\hat{\mathcal{M}}^{\ast}(p_{\text{DS}}^{\ast},q_{\text{DS}}^{\ast}).$ The following theorem states the theoretical guarantee of this method.

Datasets. We evaluate our algorithms on four public datasets, whose overall statistics is summarized in Table I.

$\bullet$ Residence [4]. This dataset contains friendship connections between 217 residents, who live at a residence hall in the Australian National University campus.

$\bullet$ Blogs [4]. This dataset contains hyperlinks between blogs in the context of 2004 US election. Blogs are mapped as nodes and hyperlinks are mapped as directed links.

$\bullet$ Facebook [5]. It is a page-page network of verified Facebook sites where nodes correspond to official Facebook pages and edges to mutual likes between pages.

$\bullet$ DBLP [6]. This dataset contains a sub-network of the co-author network of the DBLP network. Scholars who have published papers in major conferences (those considered in DBLP) are mapped as nodes. Each co-author relationship between two scholars is mapped as two directed edges between these two scholars with different directions.

Parameter setting. To reflect the real-world setting that only a small portion of users in an OSN is interested in the social visibility boosting service, we select $\gamma$ fraction of users uniformly at random from the user population $\mathcal{U}$ as requesters $\mathcal{R}$, and another $\gamma$ fraction of users uniformly at random from the user population $\mathcal{U}$ as suppliers $\mathcal{S}$. We set $\gamma$ as 0.05, 0.25, 0.5 and 0.1 for dataset Residence, Blogs, Facebook and DBLP respectively. Here we select different $\gamma$ on different datasets, in order to reveal the impact of size of requesters and suppliers on our algorithm. For each requesters $u\in\mathcal{R}$, valuation $p_{u}$ is sampled from Beta distribution $B(3,6)$, and $q_{u}$ is sampled from Beta distribution $B(6,3)$. Throughout the experiments, we fixed $\alpha=0.6$ for the OSN operator, i.e., the OSN operator keeps 40% of the payment from the requesters as the transaction fee.

Metrics & baselines. We use $R(p,q,\mathcal{M})$, the revenue of the OSN operator as the evaluation metric. To understand the accuracy and running time of our OptSupplierSet algorithm, i.e., Algorithm 1, we compare it with the following two baselines: (1) Brute, which selects the optimal set of participating suppliers under each given prices $(p,q)$ via exhaustive search; (2) TopVis, which selects suppliers with the top-$b$ social visibility from the potential supplier set under each given prices $(p,q)$. To evaluate our OptPrice algorithm, i.e., Algorithm 2, we vary the search step $\epsilon$ from 0.2, 0.1, 0.05, 0.025 to 0.0125.