Back to Search Start Over

A Random Algorithm for Profit Maximization with Multiple Adoptions in Online Social Networks

Authors :
Chen, Tiantian
Liu, Bin
Liu, Wenjing
Fang, Qizhi
Yuan, Jing
Wu, Weili
Source :
Theoretical Computer Science, 2020
Publication Year :
2021

Abstract

Online social networks have been one of the most effective platforms for marketing and advertising. Through "word of mouth" effects, information or product adoption could spread from some influential individuals to millions of users in social networks. Given a social network $G$ and a constant $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. Given 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. 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-\varepsilon)$-approximate solution with high probability. Compared with the algorithm proposed in [16] that achieves a $\frac{1}{2}(1-1/e^{2})$-approximate solution, our algorithm provides a better performance ratio which 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.<br />Comment: 21 pages, 6 figures

Details

Database :
arXiv
Journal :
Theoretical Computer Science, 2020
Publication Type :
Report
Accession number :
edsarx.2101.06239
Document Type :
Working Paper
Full Text :
https://doi.org/10.1016/j.tcs.2019.03.028