Pricing Strategies for Maximizing Viral Advertising in Social Networks

Viral advertising in social networks is playing an important role for the promotions of new products, ideas and innovations. It usually starts from a set of initial adopters and spreads via social links to become viral. Given a limited budget, one central problem in studying viral advertising is

influence maximization

, in which one needs to target a set of initial adopters such that the number of users accepting the advertising afterwards is maximized. To solve this problem, previous works assume that each user has a fixed cost and will spread the advertising as long as the provider offers a benefit that is equal to the cost. However, the assumption is oversimplified and far from real scenarios. In practice, it is crucial for the provider to understand how to incentivize the initial adopters.

In this paper, we propose the use of concave probability functions to model the user valuation for sharing the advertising. Under the new pricing model, we show that it is NP-hard to find the optimal pricing strategy. Due to the hardness, we then propose a discrete greedy pricing strategy which has a constant approximation performance guarantee. We also discuss how to discretize the budget to provide a good trade-off between the performance and the efficiency. Extensive experiments on different data sets are implemented to validate the effectiveness of our algorithm in practice.