Towards Profit Maximization for Online Social Network Providers

Jing Tang, Xueyan Tang, Junsong Yuan

Introduction

Traditional viral marketing research focuses on Influence Maximization (IM), which aims to select a set of seed users to maximize the expected number of influenced nodes. However, for Online Social Network (OSN) providers, maximizing reach often incurs significant operational costs, such as bandwidth and cloud computing expenses associated with data traffic. This paper introduces the Profit Maximization problem, where the objective is to maximize net profit—defined as the difference between the revenue generated from influence and the associated infrastructure costs.

Problem Formulation

The profit function is modeled as $P(S) = B(S) - C(S)$, where $B(S)$ represents the benefit (revenue) and $C(S)$ represents the cost. While both $B(S)$ and $C(S)$ are typically submodular and monotone, their difference $P(S)$ is neither. This makes the problem a "Difference of Submodular" (DS) optimization, which is NP-hard and lacks the standard greedy guarantees found in traditional IM.

The Prune and Search Framework

To address this challenge, the authors propose a two-phase "Prune and Search" framework designed to handle non-submodular objectives efficiently.

Phase 1: Iterative Pruning

The core innovation is the IterativePrune algorithm. By leveraging the properties of submodularity, the algorithm identifies nodes that are guaranteed to be in the optimal seed set and nodes that can be safely excluded. This process iteratively tightens the search space into a small "candidate lattice."

The IterativePrune algorithm reduces the search space by identifying nodes that must be included or excluded from the optimal set.

Once the search space is pruned, heuristic algorithms are applied to find the near-optimal seed set within the reduced lattice. The authors utilize a standard Greedy approach and a Modular-Modular (ModMod) algorithm, which approximates the submodular functions with linear bounds to iteratively solve the problem.

Experimental Evaluation

The framework was evaluated on the Google+ and LiveJournal datasets. A key finding was the effectiveness of the pruning phase: it reduced the search space by up to 98.3% for Google+ and 83.7% for LiveJournal.

Performance comparison of various algorithms across Google+ and LiveJournal datasets, showing profit and running time relative to the number of samples.

As shown in the experimental results, the pruning phase not only ensures profitability by avoiding "cost-blind" selections but also leads to a speedup of up to three orders of magnitude. The heuristic algorithms achieved high approximation quality, reaching over 98% of the theoretical upper bound on the Google+ dataset.

Conclusion

By shifting the focus from reach to net profit, this work provides a more realistic framework for OSN providers. The proposed Prune and Search framework effectively handles the non-submodular nature of profit maximization, offering significant computational savings and superior profitability compared to traditional influence maximization techniques.

Summary updated

BibTeX
@inproceedings{tang2018towards,
  author = {Jing Tang and Xueyan Tang and Junsong Yuan},
  title = {{Towards Profit Maximization for Online Social Network Providers}},
  booktitle = {INFOCOM},
  year = {2018},
  doi = {10.1109/infocom.2018.8485975},
}
Figure