Adaptive rumor spreading

Abstract

El esparcimiento de rumores es un modelo intuitivo para la difusión de información en una red social. Una entidad que controla la red, por ejemplo el proveedor del servicio, desea acelerar el proceso de esparcimiento del rumor, de forma tal que se maximice la cantidad de información entregada. Este problema, definido a grandes rasgos, ha sido objeto de múltiples investigaciones en el último tiempo, entre otros como marketing viral y maximización de influencia. Un enfoque natural y ausente en los estudios previos es la adaptividad. En este trabajo se abordan las siguientes preguntas: ¿cómo el controlador puede usar la información del estado de la red para acelerar el proceso de rumor? y ¿cuánto beneficio se obtiene de tal conocimiento? Un concepto novedoso es la comunicación oportunista en redes; cada agente de la red social comparte información (noticias, actualización de software, etc.) con otros usuarios al momento de estar momentáneamente en rango (vía wi-fi, bluetooth, etc.), de esta forma se evita la saturación de la infraestructura que soporta la red. Con esta motivación se estudia un modelo a tiempo continuo, donde cada par de nodos se comunica de acuerdo a un proceso de Poisson de cierta tasa y el rumor se transmite siempre que alguno estuviera informado. Las anteriores comunicaciones no tienen costo para el controlador, pero si éste lo desea puede informar a cualquier nodo pagando un costo unitario por ello. En vez de la usual restricción de presupuesto se fija un deadline, en tal tiempo todos los nodos deben estar informados, debiendo pagar el controlador un costo unitario por cada nodo que no haya obtenido el rumor antes del deadline. Una estrategia no-adaptativa puede informar sólo al comienzo del periodo y cuando se cumple el deadline, pagando por todos aquellos nodos que no se comunicaron nunca con otro nodo informado. Una estrategia adaptativa puede intervenir la red en cualquier instante, usando toda la información disponible hasta ese entonces, en particular sabiendo cuales nodos tienen el rumor en cada momento. El resultado principal de este trabajo es que en el caso homogéneo, donde cada par de nodos se encuentra con la misma tasa, el beneficio de la adaptividad está acotado por una constante. La demostración requiere un entendimiento profundo del proceso estocástico que domina el sistema, que se cree ya una contribución interesante. Adicionalmente, se presenta una extensión natural del caso homogéneo, donde el controlador está interesado sólo en un conjunto de nodos y no en toda la red social, se demuestra que en este escenario el beneficio de la adaptividad también está acotado por una constante. Finalmente, se muestra que, sin el supuesto de homogeneidad, el beneficio de la adaptividad puede crecer de forma no acotada.