Change search
ReferencesLink to record
Permanent link

Direct link
Social Network Monetization via Sponsored Viral Marketing
Max-Planck-Institut fur Informatik.
eBay Research Labs, eBay Inc..
Denison University.
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0003-4468-2675
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)
Abstract [en]

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.
Keyword [en]
social networks, approximation algorithms
National Category
Computer Science
URN: urn:nbn:se:kth:diva-165844DOI: 10.1145/2745844.2745853ScopusID: 2-s2.0-84955571246OAI: diva2:808911
ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS), June 2015

QC 20150714

Available from: 2015-04-29 Created: 2015-04-29 Last updated: 2015-07-14Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopusACM Digital Library

Search in DiVA

By author/editor
Na Nongkai, Danupon
By organisation
Theoretical Computer Science, TCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 96 hits
ReferencesLink to record
Permanent link

Direct link