Output–Input Ratio Maximization for Online Social Networks

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 $1-e^{-(1-c_{g})}$ approximation algorithm, where $c_{g}$ is the curvature of the monotone submodular set function $g$ . To speed up the hill-climbing greedy algorithm, we propose the threshold decrease algorithm and prove that its approximation ratio is $1-e^{-(1-c_{g})^{2}}-\epsilon $ . 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

Algorithm · Approximation algorithm · Arithmetic · Bounded function · Combinatorics · Discrete mathematics · Greedy algorithm · Mathematical optimization · Maximization · Notation · Submodular set function · Complexity and Algorithms in Graphs · Graphene research and applications · Mathematics · Mobile Crowdsensing and Crowdsourcing

• Cost-effective outbreak detection in networks

  Open Access•Jure Leskovec, Andreas Krause et al.•Proceedings of the 13th ACM…•2007

  Add to list

• Scalable influence maximization for prevalent viral marketing in large-scale social networks

  Open Access•Wei Chen, Chi Wang et al.•Proceedings of the 16th ACM…•2010

  Add to list