Journal
IEEE TRANSACTIONS ON SYSTEMS MAN CYBERNETICS-SYSTEMS
Volume 52, Issue 9, Pages 5567-5578Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TSMC.2021.3129276
Keywords
Adaptation models; Games; Social networking (online); Companies; Adaptive systems; Approximation algorithms; Optimization; Adaptive startegy; approximation alogrithm; collaborate game model; nonsubmodularity; online social networks (OSNs); stochastic optimization
Funding
- National Science Foundation [1747818, 1907472]
- Div Of Information & Intelligent Systems
- Direct For Computer & Info Scie & Enginr [1907472] Funding Source: National Science Foundation
Ask authors/readers for more resources
This study addresses the revenue maximization problem in social networks, utilizing adaptive seeding strategies and a collaboration game model to compute revenue based on user activities. It introduces the RM problem under size and community budget constraints, and proposes RMSBSolver and RMCBSolver to address the problems in various scenarios with theoretical guarantees. Additionally, data-dependent approximation ratios are provided for general nonsubmodular cases, and the effectiveness and accuracy of the solutions are demonstrated through experiments on real datasets.
Revenue maximization (RM) is one of the most important problems in social networks, which attempts to find a small subset of users that make the expected revenue maximized. It has been studied in depth before. However, most of the existing literature was based on nonadaptive seeding strategies and simple information diffusion models. It considered the number of influenced users as a measurement unit to quantify the revenue. Until the emergence of the collaborate game model, it considered the activity as a basic object to compute the revenue. An activity initiated by a user can only influence those users whose distances are within k-hop from the initiator. Based on that, we adopt an adaptive seed strategy and formulate an RM under the size budget (RMSB) problem. If taking into account the product's promotion, we extend it to an RM under the community budget problem, where the influence can be distributed over the whole network uniformly. We can prove that our objective function is adaptive monotone and not adaptive submodular, but it is adaptive submodular in some special cases. We study these two problems under both the special submodular cases and general nonsubmodular cases, and propose RMSBSolver and RMCBSolver to solve them with strong theoretical guarantees, respectively. In particular, we give a data-dependent approximation ratio by adaptive primal curvature for the RMSB in general nonsubmodular cases. Finally, we evaluate our proposed algorithms by conducting experiments on real datasets, and show the effectiveness and accuracy of our solutions.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available