Social Network Monetization via Sponsored Viral Marketing

Abstract

Viral marketing is a powerful tool for online advertising and sales because it exploits the influence people have on one another. While this marketing technique has been beneficial for advertisers, it has not been shown how the social network providers such as Facebook and Twitter can benefit from it. In this paper, we initiate the study of sponsored viral marketing where a social network provider that has complete knowledge of its network is hired by several advertisers to provide viral marketing. Each advertiser has its own advertising budget and a fixed amount they are willing to pay for each user that adopts their product or shares their ads. The goal of the social network provider is to gain the most revenue from the advertisers. Since the products or ads from different advertisers may compete with each other in getting users' attention, and advertisers pay differently per share and have different budgets, it is very important that the social network providers start the "seeds" of the viral marketing of each product at the right places in order to gain the most benefit.

We study both when advertisers have limited and unlimited budgets. In the unlimited budget setting, we give a tight approximation algorithm for the above task: we present a polynomial-time O(log n)-approximation algorithm for maximizing the expected revenue, where n is the number of nodes (i.e., users) in the social network, and show that no polynomial-time O(log^1-ε n)-approximation algorithm exists, unless NP ⊆ DTIME}(n^{poly log n}). In the limited budget setting, we show that it is hopeless to solve the problem (even approximately): unless P = NP, there is no polynomial-time O(n^1-ε)-approximation algorithm. We perform experiments on several data sets to compare our provable algorithms to several heuristic baselines.

References

1. D. Agrawal, C. Budak, and A. El Abbadi. Information diffusion in social networks: observing and affecting what society cares about. In CIKM, pages 2609--2610, 2011.
2. D. Agrawal, C. Budak, and A. El Abbadi. Information diffusion in social networks: Observing and influencing societal interests. PVLDB, 4(12):1512--1513, 2011.
3. A. Anagnostopoulos, R. Kumar, and M. Mahdian. Influence and correlation in social networks. In KDD'08.
4. L. Backstrom, D. Huttenlocher, J. Kleinberg, and X. Lan. Group formation in large social networks: membership, growth, and evolution. In KDD '06.
5. S. Bharathi, D. Kempe, and M. Salek. Competitive influence maximization in social networks. In WINE, 2007.
6. A. Borodin, M. Braverman, B. Lucier, and J. Oren. Strategyproof mechanisms for competitive influence in networks. In WWW, 2013.
7. A. Borodin, Y. Filmus, and J. Oren. Threshold models for competitive influence in social networks. In WINE, 2010.
8. C. Budak, D. Agrawal, and A. El Abbadi. Limiting the spread of misinformation in social networks. In WWW, pages 665--674, 2011.
9. G. Călinescu, C. Chekuri, M. Pál, and J. Vondrák. Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput., 40(6):1740--1766, 2011. Also in IPCO'07 and STOC'08.
10. T. Carnes, C. Nagarajan, S. M. Wild, and A. van Zuylen. Maximizing influence in a competitive social network: a follower's perspective. In ICEC, pages 351--360, 2007.
11. P. Chalermsook, J. Chuzhoy, S. Kannan, and S. Khanna. Improved hardness results for profit maximization pricing problems with unlimited supply. In APPROX-RANDOM, pages 73--84, 2012.
12. P. Chalermsook, B. Laekhanukit, and D. Nanongkai. Graph products revisited: Tight approximation hardness of induced matching, poset dimension, and more. In SODA, 2013.
13. S. Datta, A. Majumder, and N. Shrivastava. Viral marketing for multiple products. In ICDM, 2010.
14. P. S. Dodds and D. J. Watts. A generalized model of social and biological contagion. Journal of Theoretical Biology, 2005.
15. P. Domingos and M. Richardson. Mining the network value of customers. In KDD, pages 57--66, 2001.
16. J. Edwards. Chart: Facebook's sponsored stories are way more effective than display ads. Business Insider, 2012.
17. A. Efrati. Google expected to surpass facebook in display-ad sales. The Wall Street Journal, 2012.
18. S. Fiegerman. Google will overtake facebook in u.s. display ad revenue this year {report}. Mashable Business, 2012.
19. M. Fisher, G. Nemhauser, and L. Wolsey. An analysis of approximations for maximizing submodular set functions-II. In M. Balinski and A. Hoffman, editors, Polyhedral Combinatorics, volume 8 of Mathematical Programming Studies, pages 73--87. Springer Berlin Heidelberg, 1978.
20. M. Gladwell. The Tipping Point: How Little Things Can Make a Big Difference. 2002.
21. S. Goldberg and Z. Liu. The diffusion of networking technology. In SODA, 2013.
22. J. Goldenberg, B. Libai, and E. Muller. Talk of the Network: A Complex Systems Look at the Underlying Process of Word-of-Mouth. Marketing Letters, 2001.
23. S. Goyal and M. Kearns. Competitive contagion in networks. In STOC, pages 759--774, 2012.
24. M. Granovetter. Threshold Models of Collective Behavior. The American Journal of Sociology, 1978.
25. J. D. Hartline, V. S. Mirrokni, and M. Sundararajan. Optimal marketing strategies over social networks. In WWW, pages 189--198, 2008.
26. X. He, G. Song, W. Chen, and Q. Jiang. Influence blocking maximization in social networks under the competitive linear threshold model. In SDM, pages 463--474, 2012.
27. C.-C. Huang and Z. Svitkina. Donation center location problem. In FSTTCS, pages 227--238, 2009.
28. D. Kempe, J. Kleinberg, and E. Tardos. Maximizing the spread of influence through a social network. In KDD'03.
29. J. Leskovec, L. A. Adamic, and B. A. Huberman. The dynamics of viral marketing. ACM Trans. Web, 2007.
30. M. E. J. Newman. Spread of epidemic disease on networks. Physical Review E, 2002.
31. M. Richardson and P. Domingos. Mining knowledge-sharing sites for viral marketing. In KDD, pages 61--70, 2002.
32. E. M. Rogers. Diffusion of Innovations. Simon and Schuster, 2003.
33. M. Rogowsky. Will facebook generate more revenue than google? Quora, 2012.
34. D. M. Romero, B. Meeder, and J. Kleinberg. Differences in the mechanics of information diffusion. In WWW '11.
35. S. Shirazipourazad, B. Bogard, H. Vachhani, A. Sen, and P. Horn. Influence propagation in adversarial setting: how to defeat competition with least amount of investment. In CIKM, 2012.
36. S. Simon and K. R. Apt. Choosing products in social networks. In WINE, 2012.
37. V. Tzoumas, C. Amanatidis, and E. Markakis. A game-theoretic analysis of a competitive diffusion process over social networks. In WINE, 2012.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms

• Theory of computation

  • Randomness, geometry and discrete structures