Output–Input Ratio Maximization for Online Social Networks: Algorithms and Analyses

Shengminjie Chen, Wenguo Yang, Yapu Zhang, Suixiang GaoIEEE Transactions on Computational Social Systems 2022 · DOI

Abstract

In the last few decades, profit maximization (PM), which is mainly considered for maximizing net profits, i.e., the difference between gain and cost, has been a prominent issue for online social networks (OSNs). However, the output-to-input ratio, which is an important metric in economics, is also worth studying for OSNs. In this article, we present a novel problem that considers the PM problem from the ratio of gain and cost, known as output-to-input ratio maximization (OIRM). Unfortunately, it is neither submodular nor supermodular. The hill-climbing greedy algorithm for solving this problem is a <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$1-e^{-(1-c_{g})}$ </tex-math></inline-formula> approximation algorithm, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$c_{g}$ </tex-math></inline-formula> is the curvature of the monotone submodular set function <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula> . To speed up the hill-climbing greedy algorithm, we propose the threshold decrease algorithm and prove that its approximation ratio is <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$1-e^{-(1-c_{g})^{2}}-\epsilon $ </tex-math></inline-formula> . In addition, based on the relationship between classical net PM and OIRM, the algorithms for solving PM can also solve OIRM. Finally, we evaluate the performance of our algorithms using massive experiments on real datasets. To the best of our knowledge, this is the first time to study the OIRM in viral marketing.
BibTeX
@article{chen2022outputinput,
  author = {Shengminjie Chen and Wenguo Yang and Yapu Zhang and Suixiang Gao},
  title = {{Output–Input Ratio Maximization for Online Social Networks: Algorithms and Analyses}},
  journal = {IEEE Transactions on Computational Social Systems},
  year = {2022},
  doi = {10.1109/tcss.2022.3151496},
}

Loading related content...

Figure