Budget Allocation for Maximizing Viral Advertising in Social Networks  

作　　者：Bo—LeiZhang Zhu-Zhong Qian Wen-Zhong Li Bin Tang Sang-Lu Lu Xiaoming Fu 

机构地区：[1]State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China [2]Institute of Computer Science, University of G5ttingen, G5ttingen 37077, Germany

出　　处：《Journal of Computer Science & Technology》2016年第4期759-775,共17页计算机科学技术学报（英文版）

基　　金：This work was partially supported by the National Natural Science Foundation of China under Grant Nos. 61373128, 61321491, 61472181, 91218302, the Natural Science Foundation of Jiangsu Province of China under Grant No. BK20151392, Jiangsu Key Technique Project （Industry） under Grant No. BE2013116, EU FP7 IRSES MobileCloud Project under Grant No. 612212, the Program B for Outstanding Ph.D. Candidate of Nanjing University, and the Collaborative Innovation Center of Novel Software Technology and Industrialization of Jiangsu Province of China.

摘　　要：Viral advertising in social networks has arisen as one of the most promising ways to increase brand awareness and product sales. By distributing a limited budget, we can incentivize a set of users as initial adopters so that the advertising can start from the initial adopters and spread via sociM links to become viral. Despite extensive researches in how to target the most influential users, a key issue is often neglected： how to incentivize the initial adopters. In the problem of influence maximization, the assumption is that each user has a fixed cost for being initial adopters, while in practice, user decisions for accepting the budget to be initial adopters are often probabilistic rather than deterministic. In this paper, we study optimal budget allocation in social networks to maximize the spread of viral advertising. In particular, a concave probability model is introduced to characterize each user＇s utility for being an initial adopter. Under this model, we show that it is NP-hard to find an optimal budget allocation for maximizing the spread of viral advertising. We then present a novel discrete greedy algorithm with near optimal performance, and further propose scaling-up techniques to improve the time-efficiency of our algorithm. Extensive experiments on real-world social graphs are implemented to validate the effectiveness of our algorithm in practice. The results show that our algorithm can outperform other intuitive heuristics significantly in almost all cases.Viral advertising in social networks has arisen as one of the most promising ways to increase brand awareness and product sales. By distributing a limited budget, we can incentivize a set of users as initial adopters so that the advertising can start from the initial adopters and spread via sociM links to become viral. Despite extensive researches in how to target the most influential users, a key issue is often neglected： how to incentivize the initial adopters. In the problem of influence maximization, the assumption is that each user has a fixed cost for being initial adopters, while in practice, user decisions for accepting the budget to be initial adopters are often probabilistic rather than deterministic. In this paper, we study optimal budget allocation in social networks to maximize the spread of viral advertising. In particular, a concave probability model is introduced to characterize each user＇s utility for being an initial adopter. Under this model, we show that it is NP-hard to find an optimal budget allocation for maximizing the spread of viral advertising. We then present a novel discrete greedy algorithm with near optimal performance, and further propose scaling-up techniques to improve the time-efficiency of our algorithm. Extensive experiments on real-world social graphs are implemented to validate the effectiveness of our algorithm in practice. The results show that our algorithm can outperform other intuitive heuristics significantly in almost all cases.

关 键 词：social network influence maximization information diffusion submodular optimization 

分 类 号：TP393.4[自动化与计算机技术—计算机应用技术] F713.8[自动化与计算机技术—计算机科学与技术]