Maximizing the Spread of Influence through a Social Network Using Partial Incentives

Abstract

We study a generalization of the widely studied discrete influence maximization problem. We consider that instead of marketers using a budget to send free products to a few influencers, they can provide discounts to partly incentivize a larger set of influencers with the same budget. We show that this problem is an instance of maximizing the multilinear extension of a monotone submodular set function subject to an L₁ constraint and characterize its optimal solution in terms of the solutions to the discrete influence maximization problem. We then use this characterization to propose and analyze an efficient (1 - 1/e)-approximation algorithm. We also show that with negligible additional work, this algorithm also allows the marketer to evaluate cost-benefit trade-offs over a range of budgets. Furthermore, we performed small-scale experiments on synthetic and real-world social networks to demonstrate our optimal solution characterization and greedy approximation. We also performed large-scale experiments on real-world social networks to show the performance and scalability of our method in contrast to methods proposed for other generalizations of influence maximization. Moreover, we demonstrated the practicality of our method in evaluating the cost-benefit tradeoffs involving budget selection for desired influence and profit maximization.