Social Network Monetization via Sponsored Viral Marketing
2015 (English)In: SIGMETRICS '15 Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, ACM Digital Library, 2015, 259-270 p.Conference paper (Refereed)
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 apolynomial-time O (log n)-approximation algorithm for max-imizing the expected revenue, where n is the number of nodes (i.e., users) in the social network, and show that nopolynomial-time O (log1-εn)-approximation algorithm ex-ists, unlessNPDTIME(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(n1-ε)-approximation algorithm. We perform exper-iments on several data sets to compare our provable algo-rithms to several heuristic baselines.
Place, publisher, year, edition, pages
ACM Digital Library, 2015. 259-270 p.
social networks, approximation algorithms
IdentifiersURN: urn:nbn:se:kth:diva-165844DOI: 10.1145/2745844.2745853ScopusID: 2-s2.0-84955571246OAI: oai:DiVA.org:kth-165844DiVA: diva2:808911
ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS), June 2015
QC 201507142015-04-292015-04-292015-07-14Bibliographically approved