A Random Algorithm for Profit Maximization in Online Social Networks

Simple item page
dc.contributor.VIAF56851698 (Wu, W)
dc.contributor.authorChen, T.
dc.contributor.authorLiu, B.
dc.contributor.authorLiu, W.
dc.contributor.authorFang, Q.
dc.contributor.authorYuan, Jing
dc.contributor.authorWu, Weili
dc.contributor.utdAuthorYuan, Jing
dc.contributor.utdAuthorWu, Weili
dc.date.accessioned2019-11-08T21:46:16Z
dc.date.available2019-11-08T21:46:16Z
dc.date.created2019-03-26
dc.descriptionFull text access from Treasures at UT Dallas is restricted to current UTD affiliates (use the provided Link to Article).
dc.description.abstractGiven 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²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²A problem, which could achieve a (1-1/e-ε)-approximate solution with high probability and is also the best performance ratio of the PM²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. ©2019 Elsevier B.V.
dc.description.departmentErik Jonsson School of Engineering and Computer Science
dc.description.sponsorshipNational Natural Science Foundation of China (11871442), China Postdoctoral Science Foundation (2016M600556), Qingdao Postdoctoral Application Research Project (2016156), Natural Science Foundation of Shandong Province of China (ZR2017QA010), and the Fundamental Research Funds for the Central Universities (201964006).
dc.identifier.bibliographicCitationChen, T., B. Liu, W. Liu, Q. Fang, et al. 2019. "A random algorithm for profit maximization in online social networks." Theoretical Computer Science in press, doi: 10.1016/j.tcs.2019.03.028
dc.identifier.issn0304-3975
dc.identifier.urihttps://hdl.handle.net/10735.1/7090
dc.language.isoen
dc.publisherElsevier B.V.
dc.relation.urihttps://dx.doi.org/10.1016/j.tcs.2019.03.028
dc.rights©2019 Elsevier B.V. All Rights Reserved.
dc.source.journalTheoretical Computer Science
dc.subjectProfit
dc.subjectSocial networks
dc.subjectApproximation algorithms
dc.subjectBudget
dc.subjectProfit
dc.subjectInfluence
dc.subjectPerformance
dc.titleA Random Algorithm for Profit Maximization in Online Social Networks
dc.type.genrearticle

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
JECS-7069-260374.06-LINK.pdf
Size:
165.14 KB
Format:
Adobe Portable Document Format
Description:
Link to Article
Download

Collections

Wu, Weili