期刊文献+

Budget Allocation for Maximizing Viral Advertising in Social Networks 被引量:1

Budget Allocation for Maximizing Viral Advertising in Social Networks
原文传递
导出
摘要 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.
出处 《Journal of Computer Science & Technology》 SCIE EI CSCD 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.
关键词 social network influence maximization information diffusion submodular optimization social network, influence maximization, information diffusion, submodular optimization
  • 相关文献

参考文献36

  • 1Kempe D, Kleinberg J, Tardos l~. Maximizing the spread of influence through a social network. In Proc. the 9th A CM SIGKDD International Conference on Knowledge Discov- ery and Data Mining, Aug. 2003, pp.137-146.
  • 2Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N. Cost-effective outbreak detection in networks. In Proc. the 13th ACM SIGKDD International Confer- ence on Knowledge Discovery and Data Mining, Aug. 2007, pp.420-429.
  • 3Chen W, Wang Y, Yang S. Efficient influence maximization in social networks. In Proe. the 15th ACM SIGKDD In- ternational Conference on Knowledge Discovery and Data Mining, 3un. 2009, pp.199-208.
  • 4Demaine E D, Hajiaghayi M, Mahini H, Malec D L, Ragha- van S, Sawant A, Zadimoghadam M. How to influence peo- ple with partial incentives. In Proc. the 23rd International Conference on World Wide Web, April 2014, pp.937-948.
  • 5Tang Y, Xiao X, Shi Y. Influence maximization: Near- optimal time complexity meets practical efficiency. In Proc. the 2013 ACM SIGMOD International Conference on Management of Data, Jun. 2014, pp.75-86.
  • 6Marshall A. Principles of Economics: Unabridged Eighth Edition (8th edition). Cosimo, Inc., 2009.
  • 7Ioannidis S, Chaintreau A, Massouli6 L. Optimal and scal- able distribution of content updates over a mobile social network. In Proe. IEEE INFOCOM, Apr. 2009, pp.1422- 1430.
  • 8Richardson M, Domingos P. Mining knowledge-sharing sites for viral marketing. In Proc. the 8th A CM SIGKDD In- ternational Conference on Knowledge Discovery and Data Mining, Jul. 2002, pp.61-70.
  • 9Domingos P, Richardson M. Mining the network value of customers. In Proc. the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Aug. 2001, pp.57-66.
  • 10Lou T, Tang J. Mining structural hole spanners through information diffusion in social networks. In Proc. the 22nd International Conference on World Wide Web, May 2013, pp.825-836.

同被引文献2

引证文献1

二级引证文献1

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部