Social network ad allocation and optimization: a geometric mapping-based approach
Tóm tắt
With the increasing popularity of online social networks (SNS), many advertisers choose to post their advertisements (ads) within SNS. Advertising activity on SNS has grown rapidly and is now a billion-dollar business. For example, Facebook has reached more than 1 million active advertisers who contribute 90% of its revenue. In the SNS advertising model, advertisers participating in a SNS ad campaign benefit from the effects of viral marketing and network diffusion. Modern SNS serve as advertising agents and take advantage of the network diffusion to attract advertisers and charge for the cascading impressions. The optimal ad allocation task is the problem of choosing the ad allocation plan that maximizes revenue for the SNS. Considering that users have diffusion abilities and limited daily impressions, and advertisers have various bidding prices and budget concerns, a feasible plan that obeys the constraints is difficult to find. The solution to this problem lies in the space of
$${\mathbb {N}}_0^{|Ads|\times |Users|}$$
, which makes direct optimization unattractive. In this work, we study SNS advertising business models and formulate the SNS ad allocation problem. We show the problem is NP-hard and propose two dimension reduction schemes together with novel relaxation techniques. Our dimension reduction technique is formulated based on SNS user profile-based bidding scenario as well as social influence-based billing policies. We show the core ideas for dimension reduction are applicable to generalized assignment problems in bipartite graphs. We further draw connections between geometric mapping for complex network and the SNS ad allocation problem and map the SNS onto 2-D geometric space in order to relax the problem to geometric region allocation problems. We develop an optimization framework and solve the relaxed problem as a series of linear programs. Our proposed method is able to reduce the dimensionality of the original problem significantly, run two to four orders of magnitude faster, and reach 95% of the optimal solution. In addition, we discuss several extensions of our approach, including shape design in the geometric space for incorporating domain constraints in allocation strategies, more comprehensive real-world social influence models, as well as an alternative relaxation approach and its application in generalized assignment problems.
Tài liệu tham khảo
Bakshy E, Eckles D, Yan R, and Rosenn I (2012a) Social influence in social advertising: evidence from field experiments. In: Proceedings of the 13th ACM conference on electronic commerce. ACM, pp 146–161
Bakshy E, Rosenn I, Marlow C, Adamic L (2012b) The role of social networks in information diffusion. In: Proceedings of the 21st international conference on world wide web. ACM, pp 519–528
Bernstein MS, Bakshy E, Burke M, Karrer B (2013) Quantifying the invisible audience in social networks. In: Proceedings of the SIGCHI conference on human factors in computing systems. ACM, pp 21–30
Braun M, Moe WW (2012) Online advertising response models: incorporating multiple creatives and impression histories. Available at SSRN 1896486
Chakrabarty D, Goel G (2010) On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP. SIAM J Comput 39(6):2189–2211
Clemons EK (2009) The complex problem of monetizing virtual electronic social networks. Decisi Support Syst 48(1):46–56
Dow PA, Adamic LA, Friggeri A (2013) The anatomy of large Facebook cascades. In: Proceedings of the seventh international conference on weblogs and social media (ICWSM 2013)
Facebook (2013a) News feed FYI: a window into news feed. https://www.facebook.com/business/news/News-Feed-FYI-A-Window-Into-News-Feed. Accessed 16 Oct 2014
Facebook (2013b) One million thank yous. http://newsroom.fb.com/News/639/One-Million-Thank-Yous. Accessed 22 Feb 2014
Facebook (2014a) Advertise on Facebook. https://www.facebook.com/ads/create/. Accessed 02 Mar 2014
Facebook (2014b) Campaign cost & budgeting. https://www.facebook.com/help/www/318171828273417. Accessed 16 Feb 2014
Faloutsos M, Faloutsos P, Faloutsos C (1999) On power-law relationships of the internet topology. In: Proceedings of the conference on applications, technologies, architectures, and protocols for computer communication (SIGCOMM ’99). ACM, pp 251–262
Gao P, Miao H, Baras JS (2014) Social network ad allocation via hyperbolic embedding. In 53rd IEEE conference on decision and control. IEEE, pp 4875–4880
Goel S, Hofman J, Sirer MI (2012a) Who does what on the web: studying web browsing behavior at scale. In: Proceedings of the 6th international conference on weblogs and social media (ICWSM 2012)
Goel S, Watts DJ, Goldstein DG (2012b) The structure of online diffusion networks. In: Proceedings of the 13th ACM conference on electronic commerce (EC ’12). ACM, pp 623–638
Hernandez JM, Kleiberg T, Wang H, Mieghem Piet Van (2007) A qualitative comparison of power law generators. Power 24:26
Hof R (2013) You know what’s cool? 1 Million advertisers on Facebook. http://www.forbes.com/sites/roberthof/2013/06/18/you-know-whats-cool-1-million-advertisers-on-facebook/. Accessed 20 Oct 2014
Johnson R (2010) Scaling Facebook to 500 million users and beyond. https://www.facebook.com/note.php?note_id=409881258919. Accessed 16 Dec 2013
Karande C, Mehta A, Srikant R (2013) Optimizing budget constrained spend in search advertising. In: Proceedings of the sixth ACM international conference on web search and data mining. ACM, pp 697–706
Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. In: Proceedings of the ninth ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 137–146
Konect network dataset – KONECT (2016). http://konect.uni-koblenz.de/networks
Krioukov D, Papadopoulos F, Kitsak M, Vahdat A, Boguñá M (2010) Hyperbolic geometry of complex networks. Phys Rev E 82(3):036106
Kunegis J (2013) KONECT—the koblenz network collection. In: Proceedings of the international conference on world wide web companion, pp 1343–1350. http://userpages.uni-koblenz.de/~kunegis/paper/kunegis-koblenz-network-collection.pdf
Leskovec J (2009) Stanford network analysis package. http://snap.stanford.edu/
Leskovec J, Adamic LA, Huberman BA (2007) The dynamics of viral marketing. ACM Trans Web (TWEB) 1(1):5
McAuley JJ, Leskovec J (2012) Learning to discover social circles in ego networks. In: NIPS, vol 2012, pp 548–556
Mehta A, Saberi A, Vazirani U, Vazirani V (2007) Adwords and generalized online matching. J ACM (JACM) 54(5):22
Mehta A et al (2013) Online matching and ad allocation. Found Trends Theor Comput Sci 8(4):265–368
Miao H, Gao P, Hajiaghayi M, Baras JS (2015) Hypercubemap: optimal social network ad allocation using hyperbolic embedding. In: Proceedings of the 2015 IEEE/ACM international conference on advances in social networks analysis and mining. ACM, pp 357–362
Mislove A, Marcon M, Gummadi KP, Druschel P, Bhattacharjee B (2007) Measurement and analysis of online social networks. In: Proceedings of the 7th ACM SIGCOMM conference on internet measurement. ACM, pp 29–42
Newman MEJ (2003) The structure and function of complex networks. SIAM Rev 45(2):167–256
Papadopoulos F, Psomas C, Krioukov D (2015) Network mapping by replaying hyperbolic growth. IEEE/ACM Trans Netw 23(1):198–211
Salesforce (2013) The Facebook ads benchmark report. http://www.salesforcemarketingcloud.com/wp-content/uploads/2013/06/The-Facebook-Ads-Benchmark-Report.pdf. Accessed 02 Mar 2014
Schlauch WE, Horvát EÁ, Zweig KA (2015) Different flavors of randomness: comparing random graph models with fixed degree sequences. Soc Netw Anal Min 5(1):1–14
Yahoo! (2005) Webscope A1: Yahoo! Search marketing advertiser bidding data. http://webscope.sandbox.yahoo.com/
Yuan S, Wang J (2012) Sequential selection of correlated ads by POMDPs. In: Proceedings of the 21st ACM international conference on information and knowledge management. ACM, pp 515–524