A random algorithm for profit maximization in online social networks

作     者：Chen, Tiantian Liu, Bin Liu, Wenjing Fang, Qizhi Yuan, Jing Wu, Weili 

作者机构：Ocean Univ China Sch Math Sci Qingdao 266100 Peoples R China Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2020年第803卷

页      面：36-47页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Natural Science Foundation of China China Postdoctoral Science Foundation [2016M600556] Qingdao Postdoctoral Application Research Project Natural Science Foundation of Shandong Province of China [ZR2017QA010] Fundamental Research Funds for the Central Universities 

主　　题：Profit maximization Approximation algorithm Sampling Social network 

摘      要：Given a social network G and a positive integer k, the influence maximization problem seeks for k nodes in G that can influence the largest number of nodes. This problem has found important applications, and a large amount of works have been devoted to identifying the few most influential users. But most of existing works only focus on the diffusion of a single idea or product in social networks. However, in reality, one company may produce multiple kinds of products and one user may also have multiple adoptions. For multiple kinds of different products with different activation costs and profits, it is crucial for the company to distribute the limited budget among multiple products in order to achieve profit maximization. The Profit Maximization with Multiple Adoptions (PM(2)A) problem aims to seek for a seed set within the budget to maximize the overall profit. In this paper, a Randomized Modified Greedy (RMG) algorithm based on the Reverse Influence Sampling (RIS) technique is presented for the PM(2)A problem, which could achieve a (1 - 1/e -epsilon)-approximate solution with high probability and is also the best performance ratio of the PM(2)A problem. Comprehensive experiments on three real-world social networks are conducted, and the results demonstrate that our RMG algorithm outperforms the algorithm proposed in [16] and other heuristics in terms of profit maximization, and could better allocate the budget. (C) 2019 Elsevier B.V. All rights reserved.