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

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.

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.

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.