From viral marketing to social advertising: ad allocation under social influence

dc.contributor
Universitat Pompeu Fabra. Departament de Tecnologies de la Informació i les Comunicacions
dc.contributor.author
Aslay, Çiğdem
dc.date.accessioned
2017-03-22T11:10:11Z
dc.date.available
2017-03-22T11:10:11Z
dc.date.issued
2016-12-16
dc.identifier.uri
http://hdl.handle.net/10803/401679
dc.description.abstract
This thesis constitutes one of the first investigations that lie at the intersection of social influence propagation, viral marketing, and social advertising. The objective of this thesis is to take the algorithmic aspects of viral marketing out of the lab, and further enhance these aspects to account for the real world social advertisement models, by drawing on the viral marketing literature to study social influence aware ad allocation for social advertising. To this end, we take a first step towards enabling social influence online analytics in support of viral marketing decision making, and propose efficient influence indexing framework that can accurately answer topic-aware viral marketing queries with milliseconds response time. We then initiate investigation in the area of social advertising through the viral marketing lens, aligned with real world social advertisement models, and introduce two fundamental optimization problems, regarding the allocation of ads to social network users under social influence. We devise greedy approximation algorithms with provable approximation guarantees for the novel problems introduced. We also develop scalable versions of our approximation algorithms by leveraging the notion of reverse reachability sampling on social graphs, and experimentally confirm that our algorithms are scalable and deliver high quality solutions.
en_US
dc.description.abstract
Aquesta tesi constitueix una de les primeres investigacions en la intersecció entre propagació d'influència social, màrqueting viral i publicitat social. L'objectiu d'aquesta tesi és treure els aspectes algorítmics de màrqueting viral fora del laboratori, i millorar-los per tenir en compte els models de publicitat del món real en xarxes socials, fent ús de la literatura del màrqueting viral per estudiar l'assignació d'anuncis basada en la influència social per a la publicitat en xarxes socials. Amb aquesta finalitat, hem pres un primer pas cap al desenvolupament de anàlisi d'influència social en línia que ajudin en la presa de decisions en el màrqueting viral, i proposem un marc per a la indexació eficient d'influència que pugui respondre amb precisió a les consultes de màrqueting viral orientades a temes específics amb temps de resposta de mil·lisegons. A continuació, comencem una investigació en l'àrea de la publicitat social a través de la lent del màrqueting viral, en línia amb models de publicitat del món real, i introduïm dos nous problemes d'optimització pel que fa a l'assignació d'anuncis als usuaris de la xarxa social sota la influència social, amb garanties d'aproximació demostrables. També desenvolupem una versió escalable dels nostres algoritmes d'aproximació aprofitant la noció de presa de mostres d'accessibilitat inversa en grafs socials, i confirmem experimentalment que els nostres algoritmes són escalables i ofereixen solucions d'alta qualitat.
en_US
dc.description.abstract
Esta tesis constituye una de las primeras investigaciones en la intersección entre propagación de influencia social, marketing viral y publicidad social. El objetivo es sacar los aspectos algorítmicos de marketing viral fuera del laboratorio, y mejorarlos para tener en cuenta los modelos de publicidad del mundo real en redes sociales, haciendo uso de la literatura de marketing viral para estudiar asignación de anuncios basada en la influencia social. Con este fin, tomamos un primer paso hacia el desarrollo de análisis de influencia social en línea que ayuden en la toma de decisiones en el marketing viral, y proponemos un marco para la indexación eficiente de influencia que pueda responder con precisión a las consultas de marketing viral orientadas a temas específicos con tiempo de respuesta de milisegundos. A continuación, iniciamos una investigación en el área de la publicidad social a través de la lente del marketing viral, en línea con modelos de publicidad del mundo real, e introducimos dos nuevos problemas de optimización respecto a la asignación de anuncios a los usuarios de la red social bajo la influencia social, con garantías de aproximación demostrables. También desarrollamos una versión escalable de nuestros algoritmos de aproximación aprovechando la noción de toma de muestras de accesibilidad inversa en grafos sociales, y confirmamos experimentalmente que nuestros algoritmos son escalables y ofrecen soluciones de alta calidad.
en_US
dc.format.extent
138 p.
en_US
dc.format.mimetype
application/pdf
dc.language.iso
eng
en_US
dc.publisher
Universitat Pompeu Fabra
dc.rights.license
L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/4.0/
dc.rights.uri
http://creativecommons.org/licenses/by-nc-nd/4.0/
*
dc.source
TDX (Tesis Doctorals en Xarxa)
dc.subject
Influence maximization
en_US
dc.subject
Viral marketing
en_US
dc.subject
Social advertising
en_US
dc.subject
Submodular functions
en_US
dc.subject
Social influence
en_US
dc.subject
Similarity search
en_US
dc.subject
Reverse reachability sampling
en_US
dc.subject
Approximation algorithms
en_US
dc.subject
Social networks
en_US
dc.subject
Influència de maximització
en_US
dc.subject
Màrqueting viral
en_US
dc.subject
Publicitat social
en_US
dc.subject
Funcions submodulars
en_US
dc.subject
Influència social
en_US
dc.subject
Recerca de similitud
en_US
dc.subject
Presa de mostres d'accessibilitat inversa
en_US
dc.subject
Algoritmes d'aproximació
en_US
dc.subject
Xarxes socials
en_US
dc.title
From viral marketing to social advertising: ad allocation under social influence
en_US
dc.type
info:eu-repo/semantics/doctoralThesis
dc.type
info:eu-repo/semantics/publishedVersion
dc.subject.udc
62
en_US
dc.contributor.authoremail
cigdem.aslay@upf.edu
en_US
dc.contributor.director
Baeza-Yates, Ricardo
dc.contributor.director
Bonchi, Francesco
dc.embargo.terms
cap
en_US
dc.rights.accessLevel
info:eu-repo/semantics/openAccess
dc.description.degree
Programa de doctorat en Tecnologies de la Informació i les Comunicacions


Documents

tca.pdf

2.141Mb PDF

Aquest element apareix en la col·lecció o col·leccions següent(s)