Discount Allocation for Revenue Maximization in Online Social Networks

Viral marketing through online social networks (OSNs) has aroused great interests in the literature. However, the fundamental problem of how to optimize the "pure gravy" of a marketing strategy through influence propagation in OSNs still remains largely open. In this paper, we consider a practical setting where the "seed nodes" in an OSN can only be probabilistically activated by the product discounts allocated to them, and make the first attempt to seek a discount allocation strategy to maximize the expected difference of profit and cost (i.e., revenue) of the strategy. We show that our problem is much harder than the conventional influence maximization issues investigated by previous work, as it can be formulated as a nonmonotone and non-submodular optimization problem. To address our problem, we propose a novel "surrogate optimization" approach as well as two randomized algorithms which can find approximation solutions with constant performance ratios with high probability. We evaluate the performance of our approach using real social networks. The extensive experimental results demonstrate that our proposed approach significantly outperforms previous work both on the revenue and on the running time.