Multi-Grade Revenue Maximization for Promotional and Competitive Viral Marketing in Social Networks

作     者：Teng, Ya-Wen Shi, Yishuo Yang, De-Nian Tai, Chih-Hua Yu, Philip S. Chen, Ming-Syan 

作者机构：Acad Sinica Inst Informat Sci Taipei 115201 Taiwan Wenzhou Univ Stat & Informat Sci Wenzhou 325060 Zhejiang Peoples R China Acad Sinica Res Ctr Informat Technol Innovat Taipei 115201 Taiwan Natl Taipei Univ Comp Sci & Informat Engn New Taipei City 104380 Taiwan Univ Illinois Comp Sci Chicago IL 60607 USA Natl Taiwan Univ Elect Engn Taipei 106319 Taiwan 

出 版 物：《IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING》 (IEEE Trans Knowl Data Eng)

年 卷 期：2025年第37卷第3期

页      面：1339-1353页

核心收录：

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

基　　金：Institute for Information Industry, Ministry of Science and Technology, Taiwan, III National Science Foundation, NSF, (III-2106758, POSE-2346158) National Science Foundation, NSF Ministry of Education, MOE, (MOE 113L9009) Ministry of Education, MOE Academia Sinica, AS, (AS-IV-114- M06) Academia Sinica, AS National Science and Technology Council, NSTC, (110-2221-E-001-014-MY3, 113-2223-E-002-011, 113- 2221-E-305-007, 112- 2221-E-001-010-MY3, 113-2221-E-001-016-MY3) National Science and Technology Council, NSTC National Natural Science Foundation of China, NSFC, (12101464) National Natural Science Foundation of China, NSFC 

主　　题：Pricing Cost accounting Resource management Social networking (online) Companies Approximation algorithms Investment Psychology Diffusion models Time complexity Social influence revenue maximization coupons 

摘      要：In this paper, we address the problem of revenue maximization (RM) for multi-grade products in social networks by considering pricing, seed selection, and coupon distribution. Previous works on RM often focus on a single product and neglect the use of coupons for promotion. We propose a new optimization problem, Revenue Maximization of Multi-Grade Product(RMMGP), to simultaneously determine pricing, seed selection, and coupon distribution for multi-grade products with both promotional and competitive relationships between grades in order to maximize revenue through viral marketing. We prove the hardness and inapproximability of RMMGP and show that the revenue function is not monotone or submodular. To solve RMMGP, we design an approximation algorithm, namely Data-Dependent Revenue Maximization (DDRM), and propose the Pricing-Seeding-Coupon allocation (PriSCa) algorithm, which uses the concepts of Worth Receiving Probability, Pricing-Promotion Alternating Framework, and Independent/Holistic Customer-Grade Determinant sets. Our experiments on real social networks, using valuation distributions from ***, demonstrate that PriSCa and DDRM achieve on average 1.5 times higher revenue than state-of-the-art approaches. Additionally, PriSCa is efficient and scalable on large datasets.