Revenue Maximization in Campaigns with a Viral-Driven Presale and a Conformity-Driven Sales Phase
by Tianyou Gao, Keishi Tajima
Abstract
We study the Revenue Maximization (RM) problem in a two-phase
marketing scenario consisting of a presale phase and an official sale
phase. In the presale phase, users are influenced through social
diffusion and are offered discounts. In the official phase, mass-media
influence is modeled as a community-based stochastic process,
incorporating conformity effects within communities. This scenario
better reflects real-world marketing practices. However, the resulting
RM problem is NP-hard and non-submodular, rendering traditional greedy
approaches ineffective. To address this, we employ the sandwich
approximation (SA) strategy to provide theoretical
guarantees. Furthermore, we propose the Community-Based Greedy
Algorithm (CBGA), which incorporates a general improvement strategy
applicable to greedy selection methods based on Monte Carlo simulation
or Reverse Influence Sampling. CBGA adopts a divide-and-conquer
approach by performing greedy selection within each community, thereby
improving the runtime efficiency. The integration of CBGA with the SA
strategy yields a structure-dependent theoretical guarantee, with the
approximation quality determined by the number of boundary nodes
between communities. We further extend our model to more general
settings. We experimentally validate that CBGA matches the performance
of all baselines but runs faster on six real-world datasets.
revenue maximization;
influence propagation model;
social networks;
influence maximization
Published in World Wide Web, Vol.28, 72:1-32, Springer, 2025
/ Fax: +81(Japan) 75-753-5978 / Office: Research Bldg. #7, room 404