›› 2016, Vol. 31 ›› Issue (4): 759-775.doi: 10.1007/s11390-016-1661-3

Special Issue: Artificial Intelligence and Pattern Recognition

• Special Section on Data Management and Data Mining 2016 • Previous Articles     Next Articles

Budget Allocation for Maximizing Viral Advertising in Social Networks

Bo-Lei Zhang1, Student Member, CCF, Zhu-Zhong Qian1,*, Member, CCF, ACM, IEEE, Wen-Zhong Li1, Member, CCF, ACM, IEEE, Bin Tang1, Member, CCF, ACM, IEEE Sang-Lu Lu1, Senior Member, CCF, Member, ACM, IEEE, and Xiaoming Fu2, Senior Member, IEEE, Member, ACM   

  1. 1 State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China;
    2 Institute of Computer Science, University of G¨ottingen, G¨ottingen 37077, Germany
  • Received:2016-02-29 Revised:2016-05-12 Online:2016-07-05 Published:2016-07-05
  • Contact: Zhu-Zhong Qian E-mail:qzz@nju.edu.cn;
  • About author:Bo-Lei Zhang received his B.S. degree in computer science from Nanjing University, Nanjing, in 2006. He is a Ph.D. candidate in the Department of Computer Science & Technology and the State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing. His research interests include information diffusion and influence analysis in social networks.
  • Supported by:

    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 social 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.

[1] Kempe D, Kleinberg J, Tardos É. Maximizing the spread of influence through a social network. In Proc. the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Aug. 2003, pp.137-146.

[2] Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N. Cost-effective outbreak detection in networks. In Proc. the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Aug. 2007, pp.420-429.

[3] Chen W, Wang Y, Yang S. Efficient influence maximization in social networks. In Proc. the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Jun. 2009, pp.199-208.

[4] Demaine E D, Hajiaghayi M, Mahini H, Malec D L, Raghavan S, Sawant A, Zadimoghadam M. How to influence people with partial incentives. In Proc. the 23rd International Conference on World Wide Web, April 2014, pp.937-948.

[5] Tang Y, Xiao X, Shi Y. Influence maximization:Near-optimal time complexity meets practical efficiency. In Proc. the 2014 ACM SIGMOD International Conference on Management of Data, Jun. 2014, pp.75-86.

[6] Marshall A. Principles of Economics:Unabridged Eighth Edition (8th edition). Cosimo, Inc., 2009.

[7] Ioannidis S, Chaintreau A, Massoulié L. Optimal and scalable distribution of content updates over a mobile social network. In Proc. IEEE INFOCOM, Apr. 2009, pp.1422-1430.

[8] Richardson M, Domingos P. Mining knowledge-sharing sites for viral marketing. In Proc. the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Jul. 2002, pp.61-70.

[9] Domingos 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.

[10] Lou 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.

[11] Chen W, Wang C, Wang Y. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In Proc. the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Jul. 2010, pp.1029-1038.

[12] Chen W, Yuan Y, Zhang L. Scalable influence maximization in social networks under the linear threshold model. In Proc. the 10th IEEE International Conference on Data Mining (ICDM), Dec. 2010, pp.88-97.

[13] Hartline J, Mirrokni V, Sundararajan M. Optimal marketing strategies over social networks. In Proc. the 17th International Conference on World Wide Web, Apr. 2008, pp.189-198.

[14] Chen W, Lu P, Sun X, Tang B, Wang Y, Zhu Z A. Optimal pricing in social networks with incomplete information. In Proc. the 7th Int. Workshop on Internet and Network Economics, Dec. 2011, pp.49-60.

[15] Arthur D, Motwani R, Sharma A, Xu Y. Pricing strategies for viral marketing on social networks. In Proc. the 5th Int. Workshop on Internet and Network Economics, Dec. 2009, pp.101-112.

[16] Singer Y, Mittal M. Pricing mechanisms for crowdsourcing markets. In Proc. the 22nd International Conference on World Wide Web, May 2013, pp.1157-1166.

[17] Bloch F, Quérou N. Pricing in networks. Technical Report, Ecole Polytechnique, 2008. https://www.econbiz.de/Re-cord/pricingin-networks-bloch-francis/10008794143, May 2016.

[18] Candogan O, Bimpikis K, Ozdaglar A. Optimal pricing in networks with externalities. Operations Research, 2012, 60(4):883-905.

[19] Akhlaghpour H, Ghodsi M, Haghpanah N, Mirrokni V S, Mahini H, Nikzad A. Optimal iterative pricing over social networks. In Proc. the 6th Int. Workshop on Internet and Network Economics, Dec. 2010, pp.415-423.

[20] Lu W, Lakshmanan L V. Profit maximization over social networks. In Proc. the 12th IEEE International Conference on Data Mining (ICDM), Dec. 2012, pp.479-488.

[21] Zhu Y, Lu Z, Bi Y, Wu W, Jiang Y, Li D. Influence and profit:Two sides of the coin. In Proc. the 13th IEEE International Conference on Data Mining (ICDM), Dec. 2013, pp.1301-1306.

[22] Singer Y. How to win friends and influence people, truthfully:Influence maximization mechanisms for social networks. In Proc. the 5th ACM International Conference on Web Search and Data Mining, Feb. 2012, pp.733-742.

[23] Doo M, Liu L. Probabilistic diffusion of social influence with incentives. IEEE Trans. Services Computing, 2014, 7(3):387-400.

[24] Yang Y, Mao X, Pei J, He X. Continuous influence maximization:What discounts should we offer to social network users? In Proc. ACM SIGMOD, June 26-July 1, 2016. (to be appeared)

[25] Manski C F. Maximum score estimation of the stochastic utility model of choice. Journal of Econometrics, 1975, 3(3):205-228.

[26] Zadimoghaddam M, Roth A. Efficiently learning from revealed preference. In Proc. the 8th Int. Workshop on Internet and Network Economics, Dec. 2012, pp.114-127.

[27] Anagnostopoulos A, Kumar R, Mahdian M. Influence and correlation in social networks. In Proc. the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Aug. 2008, pp.7-15.

[28] Cha M, Haddadi H, Benevenuto F, Gummadi P K. Measuring user influence in twitter:The million follower fallacy. In Proc. the 4th ICWSM, May 2010.

[29] Lin S, Wang F, Hu Q, Yu P S. Extracting social events for learning better information diffusion models. In Proc. the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Aug. 2013, pp.365-373.

[30] Bakshy E, Karrer B, Adamic L A. Social influence and the diffusion of user-created content. In Proc. the 10th ACM Conference on Electronic Commerce, Jul. 2009, pp.325-334.

[31] Nemhauser G L, Wolsey L A, Fisher M L. An analysis of approximations for maximizing submodular set functions. Mathematical Programming, 1978, 14(1):265-294.

[32] Vondrak J. Optimal approximation for the submodular welfare problem in the value oracle model. In Proc. the 40th Annual ACM Symposium on Theory of Computing, May 2008, pp.67-74.

[33] Leskovec J, Kleinberg J, Faloutsos C. Graph evolution:Densification and shrinking diameters. ACM Trans. Knowledge Discovery from Data (TKDD), 2007, 1(1):Article No. 2.

[34] McAuley J J, Leskovec J. Learning to discover social circles in ego networks. In Proc. Advances in Neural Information Processing Systems, Dec. 2012, pp.548-558.

[35] Mislove A E. Online social networks:Measurement, analysis, and applications to distributed information systems[Ph.D. Thesis]. Rice University, Houston, 2009.

[36] Fu K W, Chan C H, Chau M. Assessing censorship on microblogs in China:Discriminatory keyword analysis and the real-name registration policy. IEEE Internet Computing, 2013, 17(3):42-50.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Tai Juwei; Wang Jue; Chen Xin;. A Syntactic-Semantic Approach for Pattern Recognition and Knowledge Representation[J]. , 1988, 3(3): 161 -172 .
[2] Cai Shijie; Zhang Fuyan;. A Fast Algorithm for Polygon Operations[J]. , 1991, 6(1): 91 -96 .
[3] LIU Bin; LU Zengxiang; GAN Quan; FENG Ao; WANG Pu;. Infomarker—A New Internet Information Service System[J]. , 2000, 15(3): 300 -304 .
[4] Ji-Gang Wu and Thambipillai Srikanthan. Power Efficient Sub-Array in Reconfigurable VLSI Meshes[J]. , 2005, 20(5): 647 -653 .
[5] Jing Li, Thomas Fang Zheng, William Byrne, and Dan Jurafsky. A Dialectal Chinese Speech Recognition Framework[J]. , 2006, 21(1): 106 -115 .
[6] Wen-Cheng Wang, Feng Wei, and En-Hua Wu. View Dependent Sequential Point Trees[J]. , 2006, 21(2): 181 -188 .
[7] Gang Xu and Guo-Zhao Wang. AHT Bézier Curves and NUAHT B-Spline Curves[J]. , 2007, 22(4): 597 -607 .
[8] Jian-Hua Feng, Yu-Guo Liao, and Yong Zhang. HCH for checking containment of XPath fragment[J]. , 2007, 22(5): 736 -748 .
[9] Zhen Cao, Zhi Guan, Zhong Chen, Member, IEEE, Jian-Bin Hu, and Li-Yong Tang. Towards Risk Evaluation of Denial-of-Service Vulnerabilities in Security Protocols[J]. , 2010, 25(2): 375 -inside back cover .
[10] Javier Tejada-Cárcamo, Hiram Calvo, Alexander Gelbukh, and Kazuo Hara. Unsupervised WSD by Finding the Predominant Sense Using Context as a Dynamic Thesaurus[J]. , 2010, 25(5): 1030 -1039 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved