Identificación de Nodos Influyentes en una Red Social

de Microblogging

Sr. Diego Gabriel Alonso Directores: Dr. Ariel Monteserin y Dr. Luis Berdun

Facultad de Ciencias Exactas ­ UNICEN

Tesis para obtener el Título de Grado de Ingeniería de Sistemas

Tandil , Abril 2016

Índice General 1. Introducción........................................................................................3

1.1. Contexto y Motivación..............................................................3 1.2. Propuesta.................................................................................4 1.3. Estructura del Documento........................................................6

2. Estado del Arte...................................................................................7 2.1. Las Redes Sociales.................................................................7 2.2. La Influencia en las Redes Sociales........................................9 2.3. Modelos de Propagación de Influencia..................................11

2.3.1. Campos Aleatorios de Markov...................................12 2.3.2. Linear Threshold Model (LT)......................................15 2.3.3. Independent Cascade Model (IC)..............................16 2.3.4. Trivalency Model (TR)................................................18 2.3.5. Credit Distribution Model (CD)...................................19

2.4. Trabajos Relacionados...........................................................25 3. Enfoque.............................................................................................29

3.1. Modelo Conceptual................................................................39 3.2. Obtención de Información de la Red Social...........................31 3.3. Generación de Estructuras....................................................37

3.3.1. Grafo Social...............................................................38 3.3.2. Registro de Propagaciones.......................................43

3.4. Obtención del Conjunto de Semillas......................................49 3.4.1. Generación de Entradas del Influence Models..........49 3.4.2. Ejecución del Influence Models.................................53

3.5. Interpretación de Resultados.................................................55 3.6. Visualización de los Resultados.............................................56

4. Implementación de TSeedS.............................................................60 4.1. Diseño del Sistema................................................................60 4.2. Monitoreo de Redes Sociales................................................62 4.3. Filtros......................................................................................63 4.4. Interacción..............................................................................63 4.5. Interfaz de Twitter...................................................................64 4.6. Procesamiento de Información..............................................66

1

4.7. Grafo Social............................................................................67 4.8. Usuario...................................................................................68 4.9. Registro de Propagaciones y Acción.....................................70 4.10. Volcado de Información.......................................................72 4.11. Ejecución del Influence Models............................................75 4.12. Interpretación de Resultados...............................................76 4.13. Histórico de Semillas............................................................76 4.14. Visualización de la Aplicación..............................................78

5. Resultados Experimentales.............................................................83 5.1. Estructura de los Experimentos.............................................83 5.2. Caso de Estudio 1: Fútbol......................................................86

5.2.1. Análisis de Información..............................................86 5.2.1.1. Filtrado de Interacciones...............................86 5.2.1.2. Información Adicional....................................89 5.2.1.3. Generación del Grafo Social.........................90

5.2.2. Análisis de Resultados...............................................92 5.2.2.1. Variabilidad del Seed Set..............................92 5.2.2.2. Semillas Seleccionadas.................................94

5.3. Caso de Estudio 2: Política..................................................103 5.3.1. Análisis de Información............................................104

5.3.1.1. Filtrado de Interacciones.............................104 5.3.1.2. Información Adicional..................................106 5.3.1.3. Generación del Grafo Social.......................108

5.3.2. Análisis de Resultados.............................................109 5.3.2.1. Variabilidad del Seed Set............................110 5.3.2.2. Semillas Seleccionadas...............................111

5.4. Comparativa de Casos de Estudio.......................................119 6. Conclusiones..................................................................................122

6.1 Contribuciones......................................................................122 6.2 Limitaciones..........................................................................123 6.3 Trabajos a Futuro..................................................................124

Referencias.........................................................................................126

2

1. Introducción En este capítulo se describe de manera general el contexto, la motivación y el

objetivo del presente trabajo. Además se presenta la estructura del documento para una mejor comprensión del resto de los capítulos.

1.1. Contexto y Motivación Con el éxito de las redes sociales y microblogs como Facebook, Flickr y

Twitter, el fenómeno de la influencia ejercida por los usuarios y su propagación ha atraído recientemente el interés de los científicos de la computación y de los especialistas de marketing. Uno de los problemas claves del fenómeno del análisis de la influencia es la identificación de los usuarios influyentes, es decir, aquellos usuarios cuya opinión impacta en los gustos o acciones de otros usuarios. Para determinar cuáles son los usuarios influyentes de una red es necesario analizar la propagación de la influencia en las redes sociales. Este análisis es de gran utilidad ya que permite comprender, entre otras cosas, cómo se difunde la información y cómo se realiza la adopción de innovaciones y modas en una red social [1].

En primer lugar, es importante definir qué es considerado influencia en las redes sociales. La asunción básica es que cuando los usuarios ven a sus contactos de la red realizar una acción, ellos tal vez decidan llevarla a cabo también. Sin embargo, esto puede ocurrir por diversas razones, entre ellas, puede que lo hayan oído fuera de la red social, puede que la acción ya sea popular en sí misma, o puede que genuinamente hayan sido influenciados por sus contactos [2]. Para aclarar este punto, se va a tomar como definición de influencia una perspectiva basada en el seguimiento de las relaciones de los usuarios en dichas redes. Es decir, si observamos a un usuario v realizando una acción a en un tiempo t, y un usuario u (que tiene una relación con v) realiza la misma acción en un plazo corto de tiempo , digamost + Δ, entonces podemos pensar que la accióna se propagó de v a u. En caso de observar que esto sucede frecuentemente para diferentes acciones, entonces podemos concluir que el usuario v está ejerciendo influencia sobre el usuario u, convirtiéndose el usuario v en un usuario influyente [1].

Motivados por el diseño de estrategias virales de marketing, en [3] plantean un problema algorítmico para las redes sociales: “si podemos intentar convencer a un subconjunto de individuos de adquirir un nuevo producto o innovación, y el objetivo es desencadenar una cascada de adopciones futuras, ¿a qué conjunto de individuos debemos apuntar?”.

De manera formal, Kempe trata lo antes mencionado y lo define como el problema de maximización de influencia [3]. Dicho problema busca determinar k nodos (llamados semillas) en la red, de manera tal que al activarlos se maximice la

3

propagación de la influencia esperada. Este problema ha recibido gran atención por parte de la comunidad de la minería de datos en la última década [1, 3, 4].

Por otra parte, el tiempo es un factor fundamental en estos análisis de influencia. Está probado que un tiempo sublogarítmico es suficiente para propagar una novedad a todos los nodos de la red [5]. También está argumentado que la naturaleza instantánea de estas redes influye en la velocidad en la que estos eventos se desarrollan [6].

En este contexto, dado el gran dinamismo de las redes sociales actuales surge la necesidad de analizar la evolución de los usuarios influyentes en un determinado período de tiempo y sobre una temática específica.

1.2. Propuesta El objetivo principal del presente trabajo es desarrollar un enfoque que

permita, durante un intervalo de tiempo, identificar los nodos más influyentes de la red social Twitter en base a una temática específica. Además se busca poder 1

visualizar la evolución de la influenciabilidad de los usuarios de manera dinámica en el tiempo.

Este enfoque es materializado en la herramienta “TSeedS: Twitter Seed Set”, que determina minuto a minuto los usuarios más influyentes (en base a una temática) en la red social Twitter. TSeedS permite la visualización de los resultados a través de gráficos. De esta forma, con el transcurso del tiempo pueden estudiarse diversos aspectos de la influencia del usuario y de la temática. En la Figura 1.1, se muestra un esquema conceptual de la herramienta propuesta.

1 Twitter: https://twitter.com/

4

Figura 1.1. Esquema conceptual de la herramienta TSeedS.

Para lograr este objetivo, inicialmente se escuchan interacciones de la red

social Twitter en tiempo real filtrando las mismas por categoría. También se filtran por tiempo con el objetivo de analizar sólo las interacciones recientes. Paralelamente tras el arribo de cada una de las interacciones escuchadas, se genera información que luego será utilizada por una herramienta externa denominada Influence Models. Esta herramienta permite obtener el conjunto de nodos influyentes de una red. Finalmente los resultados se interpretan y muestran en tiempo real permitiendo un análisis dinámico de la influenciabilidad de los usuarios.

La herramienta Influence Models se basa en un modelo de propagación de influencia denominado “Credit Distribution Model” (CD). El CD permite aprender las probabilidades de los enlaces entre nodos a partir de propagaciones pasadas que fueron registradas. A través de un único scan del registro de propagaciones distribuye créditos a los posibles influenciadores, retrayendo hacia atrás la red de propagación. Según análisis realizados el CD logra mejores resultados en cuanto a semillas influenciadoras, tiempo de respuesta y memoria utilizada que los demás modelos existentes (Linear Threshold, Trivalency, Independent Cascade) [4].

En el caso particular de Twitter las acciones cuya propagación deberá ser registrada corresponde con los Tweets, Retweets yReplies. Es decir que se deberá armar un modelo de propagación de acciones a partir de las interacciones escuchadas y las relaciones de los usuarios de la red social.

5

1.3. Estructura del Documento El resto del documento, se encuentra dividido en capítulos y secciones. En el

Capítulo 2, se presenta el Estado del Arte en que se encuentra la investigación relacionada con el problema tratado. En el mismo se brinda información detallada sobre: las redes sociales, su evolución y su impacto en la sociedad; el concepto de influencia y sus diversas aplicaciones; distintos modelos de propagación de influencia existentes; y diversos trabajos relacionados con la problemática actual de los nodos influyentes en las redes sociales.

En el Capítulo 3, se describe en forma detallada el enfoque propuesto por el presente trabajo. Se propone una visión de alto nivel sobre las etapas del enfoque y aspectos tenidos en cuenta. Además se define un ejemplo como hilo conductor para facilitar la comprensión de los conceptos explicados.

En el Capítulo 4, se detalla el diseño e implementación de la herramienta TSeedS que materializa el enfoque presentado. Asimismo, se presentan diagramas sobre el diseño de la herramienta y se especifican particularidades de implementación.

El Capítulo 5 describe la ejecución de los experimentos propuestos y los resultados obtenidos. Con la utilización de gráficos y tablas se ilustran de forma detallada los resultados de interés.

Finalmente, en el Capítulo 6, se presentan las conclusiones del presente trabajo junto con las limitaciones de la herramienta y posibles extensiones o mejoras a futuro.

6

2. Estado del Arte Este capítulo es la base teórica sobre que la se sustenta la presente tesis. El

mismo, contiene los antecedentes del problema, las diferentes teorías que lo abordan y características del mismo. Además se definen conceptos fundamentales para la comprensión del trabajo realizado y se analizan diversas técnicas relacionadas.

El capítulo se encuentra organizado de la siguiente forma: En la sección 2.1 se describe brevemente el concepto de redes sociales, su evolución y los volúmenes de usuarios. Basándonos en la red sobre la que luego se desarrollará el enfoque, en esta misma misma sección se profundiza sobre la red social Twitter (impacto a nivel usuario y global, formas de uso, conceptos particulares).

En la sección 2.2, se profundiza el área de redes sociales que es de interés en el presente trabajo, la influencia. En la misma, se incluyen definiciones del concepto, importancia en la actualidad, múltiples aplicaciones y diferenciación con conceptos relacionados.

En la sección 2.3, sobre la base del problema principal a resolver, se analizan y exponen diferentes modelos y estrategias estudiadas. Particularmente, el modelo a utilizar en el presente trabajo se explica en la sección 2.3.5.

Finalmente en la sección 2.4 se brinda una breve descripción de diversos trabajos relacionados con el ranking de usuarios en redes sociales y los análisis de influenciabilidad de los mismos.

2.1. Las Redes Sociales En informática, la World Wide Web (WWW) es conocida como un sistema de

distribución de documentos interconectados y accesibles a través de Internet. Aunque desde otro punto de vista, la red informática mundial puede describirse como una fuente de información a nivel global para diversos servicios (noticias, educación, anuncios, información) en distintas áreas (política, deportes, religión, trabajo, etc.). Además con el advenimiento de la Web 2.0 que revoluciona el concepto de red, las formas de comunicación, e Internet que adopta características nuevas de colaboración y participación, este fenómeno es también denominado la Web Social [7]. Andreas M. Kaplan y Michel Haenlein, de la Universidad de Indiana, definen los medios o redes sociales como "un grupo de aplicaciones basadas en Internet que se desarrollan sobre los fundamentos ideológicos y tecnológicos de la Web 2.0, y que permiten la creación y el intercambio de contenidos generados por el usuario" [7]. El cambio antes mencionado se evidencia mayormente a nivel usuario, ya que de ser solo un consumidor de la WWW, el individuo comienza a interactuar y contribuir con la misma con múltiples usuarios de diversas maneras.

7

Entre las redes sociales más destacadas en la actualidad pueden mencionarse, Facebook con aproximadamente 1590 millones de usuarios activos , 2

YouTube con más de 1000 millones , y Twitter con una cifra cercana a los 320 3

millones . 4

Redes Sociales de Microblogging: Twitter El Microblogging es un servicio que permite a sus usuarios publicar y enviar

mensajes breves a través de sitios web, mensajería instantánea, aplicaciones ad hoc o smartphones (celulares inteligentes). Dentro de sus principales características se destacan, la sintetización y la sencillez ya que en la gran mayoría de los sistemas de Microblogging el tope de escritura es de alrededor de 140 caracteres. Su uso es variado y dentro de los más conocidos se pueden denotar Tumblr, Posterous, Typepad, Soup.io y Twitter, siendo este último el líder en la actualidad.

La plataforma Twitter[8] fue creada y lanzada en el año 2006, y, en la actualidad, además de rondar los 320 millones de usuarios, genera aproximadamente 65 millones de tweets (mensajes en dicha plataforma) al día. La esencia de esta red social se basa en que sus usuarios puedan expresarse libremente a través de mensajes, respetando siempre su límite de longitud que es de 140 caracteres. Cada usuario posee un perfil, el cual puede ser público o privado y cuenta con información personal que el mismo individuo provee. Los denominados tweets son publicados en el perfil de dicho usuario, junto con su fecha de publicación. Los usuarios pueden suscribirse a otros usuarios entrando al perfil del usuario de interés, y de esta manera se establecen relaciones de followers (seguidores) y following (los que se siguen). Además los distintos seguidores pueden realizar distintas acciones con los mensajes de otros usuarios (re­publicar o hacer retweet, citar, responder y marcar como favorito o indicar “me gusta”). Al hacer un retweet, en el perfil del usuario que lo realiza aparecerá el mensaje publicado por el usuario original que lo emitió. A su vez, en el caso de citar, aparecerá el tweet original entrecomillado y aparte un mensaje complementario del usuario que está realizando la cita. Por otra parte, responder a un mensaje implica etiquetar al usuario original utilizando el símbolo “@” (arroba) seguido del nombre de usuario deseado. En adición, puede indicarse como favorito un tweet simplemente realizando un click sobre un corazón (o anteriormente una estrella) que figuran en la parte inferior de dicho tweet. La herramienta también provee un servicio de mensajería privada entre usuarios, denominado “Direct Message” (DM).

La plataforma además permite que los usuarios resalten palabras de su mensaje precediendo las mismas con el símbolo “#” (numeral), y dicha connotación

2 Actualizado a diciembre de 2015 https://newsroom.fb.com/company­info/ 3 Actualizado a marzo del 2016 https://www.youtube.com/yt/press/es­419/statistics.html 4 Actualizado a diciembre de 2015 en https://about.twitter.com/es/company

8

se denomina hashtag. La utilización de los hashtags permite la discusión de diversos temas de manera global, formando grupos de discusión que usen la misma etiqueta de texto tras el símbolo numeral. Twitter analiza la cantidad de publicaciones con un determinado hashtag y elabora una lista con los denominados “Trending Topic” o TT. Un TT indica una palabra o frase que está dentro de las más repetidas en un momento concreto. Como se mencionó previamente, Twitter realiza una lista con dichos tópicos y el usuario puede visualizar qué se está diciendo sobre el tema y participar. Cabe destacar, que dicha lista puede distinguirse según la localización geográfica (países o ciudades), por ejemplo, cuáles son los TT globales en dicho momento o cuáles son en Argentina o cuáles son en Buenos Aires.

Uno de los puntos importantes de Twitter es la diseminación veloz de temáticas en tiempos concretos. De esta manera puede ser utilizado como un motor de búsqueda. Un claro ejemplo que propone Johnson en “How Twitter will change the way we live”, orientado a lo deportivo, es que si se busca un artículo interesante sobre un jugador se recurre a Google, en cambio si se está buscando sobre su actuación o rendimiento en tiempo real en un partido se recurre a Twitter. También enuncia lo importante que se ha vuelto la plataforma para las personas y negocios [9]. De hecho, la herramienta ha sido utilizada en diversas áreas de interés como propagadora de información. Por ejemplo, para promocionar marcas por usuarios famosos con gran número de seguidores como Jorge Rial y el sitio de noticias BigBangNews[10]. Otro ejemplo, es cuando se utilizó para la elección presidencial en Irán en 2009, donde otros medios de comunicación se encontraban restringidos [11]. También se la ha utilizado en situaciones de emergencia como el tsunami en Japón en 2011 [12]. Por otro lado, hay que destacar que en múltiples ocasiones Twitter ha sido censurado, por ejemplo, en China para evitar la discusión sobre el 20mo aniversario de la masacre de Tiananmen Square. Allí gran cantidad de ciudadanos se concentraron en el lugar para protestar pero no podían hacerlo de manera virtual [13].

2.2. La Influencia en las Redes Sociales

La Real Academia Española define el concepto de influencia como el “poder, valimiento, autoridad de alguien para con otra u otras personas o para intervenir en un negocio” [14]. Al adaptar dicho concepto al contexto de las redes sociales, la asunción básica es que cuando los usuarios ven a uno de sus contactos de la red realizar una acción, ellos decidan llevarla a cabo también. Sin embargo, esto puede ocurrir por diversas razones, entre ellas, puede que lo hayan oído fuera de la red social, puede que la acción sea popular en sí misma, o puede que genuinamente hayan sido influenciados por sus contactos [2]. Para aclarar este punto, se define

9

influencia desde una perspectiva basada en el seguimiento de las relaciones de los usuarios en dichas redes. Si se observa a un usuario “v” realizando una acción en un tiempo “t”, y un usuario “u” (amigo de “v”) realizando la misma acción en un corto plazo (t+Δ), entonces se puede pensar que la acción “a” se propagó de “v” a “u”. En caso de observarse que dicho suceso ocurre de manera frecuente para diversas acciones, entonces se puede concluir que el usuario “v” ejerce cierta influencia sobre el usuario “u”, convirtiendo al usuario “v” en un usuario influyente [1].

Con el éxito de las redes sociales y microblogs, el fenómeno de la influencia ejercida por los usuarios y la propagación de información, ha atraído el interés de los científicos de la computación y de los especialistas de marketing [15,16,17,18]. Entre las diversas aplicaciones que existen sobre dicho fenómeno se destacan el Marketing Viral, la Recomendación Personalizada y los Rankings en Redes Sociales. En el caso del Marketing Viral la idea es identificar los usuarios más influyentes en una red que puedan activar una cadena de propagación de “boca en boca”, de manera que con un costo reducido de marketing se alcance una gran parte de la red en cuestión. Encontrar esos determinados usuarios también llamados key users es el punto crítico que ha recibido y recibe mucha atención en los últimos años. En [19] se muestra una investigación donde se aplican distintos modelos teóricos al marketing viral, aunque se profundiza en cómo nuevos productos o tecnologías se propagan a través de la población. Se parte de modelos que han sido examinados en la literatura económica y en la sociología, como los juegos de interacción local[20], los modelos en cascada[21,22], los modelos con umbral[3], y los modelos basados en campos aleatorios de Markov[23,24]. El análisis se realiza sobre dos problemas fundamentales, el de la maximización de la influencia y el de estudiar las propiedades de los grafos que permiten o prohíben la propagación contagiosa de los productos. Por otro lado, en [25] se estudia la “difusión de las innovaciones” y se propone un modelo que parte de un juego de coordinación en la red, donde se premia a los nodos que siendo vecinos realicen las mismas acciones. Luego dicho modelo se adapta con teoría de comportamientos en cascada y su relación con el Marketing Viral.

En el caso de la Recomendación Personalizada, en [26] se propone un modelo del flujo de la información basado en la velocidad de difusión. Dicho modelo permite identificar hacia dónde debería fluir la información (predicción) y quién la recibirá más rápidamente (ranking/clasificación). Para lograr el segundo objetivo mencionado, estima el tiempo esperado para que la información llegue a un usuario específico en la red. Además propone un algoritmo “DiffusionRank” para clasificar a los usuarios basándose en qué tan rápido la información fluye a través de los mismos. Luego aplica dicho modelo y el algoritmo antes mencionado sobre dos conjuntos de datos y demuestran las mejoras en la Recomendación automática respecto al modelo “Collaborative Filtering” y el modelo de difusión uniforme de información (EABIF). Para realizar el experimento y poder comparar los modelos, se dividen los datasets en dos partes (entrenamiento y testeo).

10

En el caso de la Clasificación o Ranking en las Redes Sociales, en [27] se plantea el problema de la maximización de la viralidad en redes de microblogging. El trabajo se basa en las publicaciones y re­publicaciones de lo que se denominan “memes” (pequeños fragmentos de texto, imágenes, audio o videos). En este paper se propone un análisis empírico de la propagación de memes en la red Yahoo! y se define un modelo de esparcimiento de los mismos. Luego profundiza en el problema del ranking de memes, propone heurísticas de cómo la propagación ocurre en una red social real y finalmente reporta los resultados obtenidos de todos los estudios realizados.

Por otra parte, pueden indicarse diversas investigaciones para la diferenciación del concepto de influencia respecto de otros factores comoHomophily o Correlation [28,29,30,31]. Homophily es un término definido por sociólogos en los años ‘50 para explicar la tendencia de los individuos a asociarse y enlazarse con otros similares. Este factor asume selección, es decir, el hecho de que es la similitud entre usuarios lo que deriva en la creación de nuevas conexiones. Crandall en [29] además propone un framework para analizar las interacciones entre la influencia social y este factor antes definido. Anagnostopoulos en [28] desarrolla técnicas (como test aleatorio o test de inversión de aristas) para separar influencia del concepto de correlación. En el trabajo , se ejemplifica que en la red social Flickr, la correlación social que existe al etiquetar no puede ser atribuida a la influencia.

Además cabe destacar diversos análisis realizados sobre los efectos de la propagación de la influencia a nivel social [32,33]. Por ejemplo, Christakis y Fowler en [32] reportan los efectos de la influencia social sobre la propagación de la obesidad, el consumo de tabaco, el consumo de alcohol y otros hábitos no saludables.

2.3. Modelos de Propagación de Influencia

Para resolver el problema de la maximización de la influencia planteado en el Capítulo 1 se analizaron diversos modelos. A modo de recordatorio, lo que plantean Domingos y Richardson en [23] es: si podemos intentar convencer a un subconjunto de individuos de adquirir un nuevo producto o innovación, y el objetivo es desencadenar una cascada de adopciones futuras, ¿a qué conjunto de individuos debemos apuntar?. Kempe en [3], de manera formal, trata dicho tema como el problema de la maximización de influencia. Este consiste en determinar “k” nodos (llamados semillas) en la red, de manera que al ser activados se maximice la propagación de la influencia esperada.

A continuación se describen los distintos modelos y estrategias estudiadas para resolver el problema en cuestión.

11

2.3.1. Campos Aleatorios de Markov Los primeros en considerar la propagación de la influencia y la identificación

de los usuarios influyentes bajo una perspectiva de minería de datos fueron Domingos y Richardson [23,24]. Éstos modelan el problema con Campos Aleatorios de Markov y heurísticas para la selección de los usuarios. Un Campo Aleatorio de Markov es un modelo gráfico no dirigido representando la distribución articulada de un conjunto aleatorio de variables, donde los vértices son variables, y las aristas representan dependencias entre variables. Esto se aplica en el contexto de la propagación de influencia, modelando solo el estado final de la red como un extenso conjunto de variables aleatorias interdependientes [34].

En particular, la función de marketing que buscan maximizar es el aumento de las ganancias esperadas que, en otras palabras, es la diferencia entre la ganancia esperada obtenida de emplear una estrategia de marketing y la que se espera obtener al no utilizar ningún tipo de estrategia. Para ello en [23], previo a explicar el modelo, distinguen dos tipos de valores de cliente. Por un lado, se distingue el valor intrínseco (intrinsic value) del cliente, que es su valor basado en los productos que normalmente consume o es de su agrado comprar. Por otro lado, se distingue el valor de red (network value) de un cliente, que es más alto cuando este produce una influencia positiva en las probabilidades de compra del producto de los demás usuarios.

El modelo considera “n” posibles clientes y la variable “Xi” como un valor lógico donde Xi=1 es equivalente a haber comprado siendo “marketed” (se aplicó estrategia sobre dicho cliente), y Xi=0 es cualquier otro caso. Además se consideran vecinos (N=neighbors) de Xi a los clientes que directamente lo influyen. El producto en cuestión con sus atributos se toma como Y = Y1,..,Ym. A su vez, el plan de marketing a seguir se define como M = M1,..,Mn donde Mi es la acción de marketing a aplicar sobre el cliente i. Estas acciones pueden ser de diversos tipos, un valor lógico por ejemplo donde si Mi=1 se le ofreció un descuento al cliente y Mi=0 en cualquier otro caso; una variable continua que indique el tamaño del descuento ofrecido al cliente; o una variable nominal que indique la acción seleccionada sobre el cliente de un conjunto de posibles acciones a realizar. Con los conceptos explicados construyen la siguiente fórmula:

es un valor entre 0 y 1 que mide qué tan independiente es Xi

es la probabilidad interna de Xi de comprar el producto es el efecto de los vecinos en Xi

12

Para calcular dicho efecto de los vecinos, proponen un modelo lineal simple: donde wij representa cuánto es influenciado “i” por su vecino “j”.

Hay que tener en cuenta que el valor total de dicha sumatoria es 1, siempre wij >= 0 , y wij=0 solo si “j” no es vecino de “i”. Destacan que los modelos lineales tienen buena performance, especialmente cuando los datos están esparcidos, y proveen significativas ventajas computacionales.

La idea detrás del estudio es calcular el plan óptimo de marketing para un producto que aún no ha sido integrado en el mercado. En ese caso, el estado de los vecinos no se conoce y es por ello que los autores derivan una fórmula que permite computar P(Xi=1|Y,M) que es la siguiente:

Luego suponen M como un vector de valores lógicos donde se considera un solo tipo de acción de marketing como se redactó previamente. Con las suposiciones siguientes, definen el aumento de ganancia esperado (Expected Lift in Profit) del cliente como valor intrínseco: donde: c = costo de marketing de un cliente (es una constante) r0= ingreso obtenido de la compra sin aplicar estrategia de marketing r1= ingreso obtenido de la compra si se aplica estrategia de marketing fi1(M) = resultado de que Mi=1 para todos los i fi0(M) = resultado de que Mi=0 para todos los i El ELP global de un plan de marketing en particular es entonces:

El ELP total de un cliente es: Por ende, su valor de red equivale a la la diferencia entre su valor total y su

valor intrínseco. Pero retomando el objetivo inicial, se centran en encontrar el M que maximice ELP(Y,M). Para ello, suponen Δi(Y) como el efecto de red de un cliente “i”

13

para un producto de atributos “Y” (nótese que valor de red no es lo mismo que efecto de red). De manera recursiva (comienza siendo 1, y se itera entre 10­20 veces hasta converger) determinan que:

Finalmente muestran que la ELP para el cliente “i” para cualquier acción de

marketing “z” es:

De allí, derivan respecto de “z” y asumiendo diferenciable ΔPi(z,Y), calculan

la acción “z” que maximiza el ELPiz,total(Y,M), que es en definitiva el Mi que maximiza ELP(Y,M). Por lo tanto, desde el efecto de red de los clientes (Δi(Y)) pueden directamente calcular el plan de marketing óptimo.

Este modelo es aplicado al sitio Epinions, en el cual los miembros redactan reseñas o reviews de productos, incluyendo un rating (de 0 a 5 estrellas), a más de cientos de miles de productos. Además como incentivo, los “reviewers” reciben dinero cada vez que su reseña es leída. Es importante destacar, que también, los usuarios pueden listar los reviewers en los que confían.

Con más de 75 mil usuarios, 500 mil aristas en sus redes de confianza, y 586 mil reseñas sobre 104 mil productos, en [23] plantean que Epinions es el sitio ideal para ser fuente de experimentos en redes sociales y marketing viral.

Para este caso de aplicación, asumen que es más factible que un usuario compre un producto si existe una reseña de una de sus personas de confianza. De esta manera consideran que toda la gente de confianza posee el mismo nivel de influencia, ya que en Epinions no se provee otra información. Por otro lado, para definir el vector de atributos del producto Y, utilizan un solo atributo que es la categoría a la que pertenece.

En los experimentos tras aplicar este modelo al contexto antes explicado, se denota que el marketing viral es al menos igual de bueno que el marketing directo, y en la mayoría de los casos es mejor por un gran margen. El criterio es la ganancia esperada, sin embargo, también analizan otro aspecto como es la velocidad. En este caso, la diferencia es extremadamente grande ya que de tardar minutos u horas en hallar el plan de marketing óptimo, en este modelo lineal se encuentra tras 1.05 segundos. Además demuestran que al borrar aristas conocidas en la red, el sistema arroja aún mejores resultados que el marketing directo. La idea es que con un pequeño conocimiento de la red, los métodos de marketing viral aplicados siguen superando al marketing directo.

14

2.3.2. Linear Threshold Model (LT) Kempe en [3] analiza la cuestión como un problema de optimización discreta,

obteniendo garantías de aproximación demostrables en varios modelos preexistentes procedentes de la sociología matemática. En particular, se basa en dos modelos de propagación fundamentales, denominados Linear Threshold Model (LT) e Independent Cascade Model (IC). Este último será explicado en la siguiente subsección (2.3.3). Sin embargo, cabe destacar que en ambos modelos, en un tiempo dado, cada nodo es activo o inactivo, y su tendencia a activarse aumenta de manera monótona a medida que más de sus vecinos se vuelven activos.

Este modelo se basa en una red social G, representada por un grafo dirigido, donde los nodos son los clientes o adquisidores de la innovación (o producto en cuestión). Kempe se centra en el caso progresivo en el cual un nodo inactivo puede volverse activo pero no al revés. En el LT cada nodo “v” es influenciado por un vecino “w” de acuerdo a un peso “bv,w” de manera que la suma de los distintos pesos de cada vecino sobre v no supera el valor 1. La dinámica del proceso es la siguiente: cada nodo v elige un umbral θv uniformemente al azar del intervalo [0,1]; esto representa la fracción ponderada de los vecinos de v que deben volverse activos para que dicho nodo también se active. Dada una elección al azar de los umbrales, y un conjunto inicial de nodos A0 activos (con todos los demás nodos inactivos), el proceso de difusión se desarrolla de manera determinista en pasos discretos: en la etapa “t”, todos los nodos que estaban activos en el paso “t­1” permanecen en dicho estado, y se activa cualquier nodo v para el cual el peso total de sus vecinos activos es al menos θv (umbral de v, como se muestra a continuación).

El hecho de la selección al azar de los umbrales es con la intención de modelar la falta de conocimiento sobre sus valores. En definitiva, lo que se hace es promediar sobre los posibles valores de umbral para todos los nodos (en otra clase de enfoques se toman por ejemplo todos los umbrales con valor 0.5 [35,36,37]).

Respecto a la problemática a tratar, en [3] definen la influencia de un conjunto de nodos A, denotada σ(A), como el número de nodos activos esperado al finalizar el proceso. Se denota de esa manera ya que A es el conjunto inicial de nodos activos, denominado A0. El problema de maximización de influencia requiere un parámetro “k”, de manera de encontrar un conjunto de “k” nodos de máxima influencia.

Como se indicó en el inicio de esta sección Kempe busca obtener garantías de aproximación demostrables, para ello utiliza teoría de funciones submodulares. Se dice que una función “f” es submodular si satisface una propiedad natural de

15

“rendimientos decrecientes”: la ganancia marginal de agregar a un conjunto S es al menos tan alta como la ganancia de agregar el mismo elemento a un superconjunto de S. Formalmente, satisfacen lo siguiente: f(S∪ v) ­ f(S) >= f(T∪ v) ­ f(T), para todos los elementos v y para todos los pares de conjuntos S ⊆ T. Suponiendo que se tiene una función f submodular, que solo toma valores no negativos y es monótona en el sentido de que agregar elementos al conjunto no hace decrecer a f, el deseo de Kempe es encontrar un conjunto S de “k” elementos para la cual f(S) es maximizada. La estrategia en [3] es considerar que la función de influencia resultante σ() es submodular. De manera desarrollada y demostrando algunos teoremas y afirmaciones, prueba lo explicado anteriormente. Mediante la simulación del proceso de difusión y el muestreo de los conjuntos activos resultantes, Kempe expresa que se puede obtener de manera arbitraria aproximaciones cercanas a σ(A) con alta probabilidad.

En sus experimentos, comparan su algoritmo Greedy (sobre los modelos LT e IC) con heurísticas basadas en los grados de los nodos y la centralidad dentro de 5

la red , así como con la elección al azar de los nodos a seleccionar . Las heurísticas 6 7

mencionadas son comúnmente usadas en la sociología como estimaciones de la influencia de los nodos [38]. La red que eligen es de co­autores, obteniendo los datos de una lista completa de papers sobre la sección de teorías de física de arXiv. La idea es que cada nodo es un investigador que posee al menos un paper con uno o más co­autores. El grafo resultante posee 10748 nodos y cerca de 53000 aristas. Los resultados obtenidos respecto a la cantidad de nodos activados en base a la selección de nodos activos iniciales tras ejecutar su algoritmo Greedy sobre el LT son superiores en gran porcentaje a las heurísticas de selección de nodos de alto grado, o la de nodos centrales, y aún mayor comparado con la selección al azar. Kempe sostiene que esto sucede ya que las heurísticas no tienen en cuenta ciertos efectos de la red. En particular, no tienen en cuenta el hecho de que muchos de los nodos centrales o de alto grado que incorporan pueden estar en cluster (es decir, agrupados o conectados), por ende no es necesario seleccionar a todos ellos.

2.3.3. Independent Cascade Model (IC)

Basado en teoría de probabilidades y trabajos sobre la interacción de sistemas de partículas [39,40], surgen los modelos dinámicos en cascada para procesos de difusión. El modelo de este tipo que es investigado en el contexto del

5 High­degree nodes heuristic: elige nodos en orden decreciente de grados. 6 Centrality heuristic: basada en la asunción de que un nodo con una ruta corta a otros nodos en la red va a tener más chances de influenciarlos. Por ello, se seleccionan nodos con el fin de aumentar la distancia media a otros nodos en la red. 7 Random Selection: tomada como base, es el resultado de seleccionar los nodos uniformemente al azar.

16

marketing [21,22] es el Independent Cascade Model. Como se explica en la subsección 2.3.2, en este modelo al igual que en el LT, en un tiempo dado, cada nodo es activo o inactivo, y su tendencia a activarse aumenta de manera monótona a medida que más de sus vecinos se vuelven activos.

Análogamente al LT, el IC comienza con un conjunto inicial de nodos activos denotado como A0, y de allí el proceso se desarrolla en pasos discretos. En particular, la dinámica de este modelo es la siguiente: cuando un nodo “v” primero es activado en una etapa “t”, se le da una sola chance de activar cada uno de sus vecinos inactivos “w”; tiene éxito con una probabilidad pv,w que es un parámetro del sistema. En caso de que “w” posea múltiples nuevos vecinos activos, los intentos de los mismos se hacen de manera secuencial y en un orden arbitrario. Si “v” tiene éxito, entonces “w” se vuelve activo en la etapa “t+1”. Indistintamente del éxito de “v”, este ya no puede seguir intentando activar “w” en las siguientes etapas. De esta manera, el proceso se ejecuta hasta que no existan más activaciones posibles.

La problemática a tratar, es definida de igual forma que para el Linear Threshold Model en [3], donde la influencia de un conjunto de nodos A, denotada σ(A), es el número de nodos activos esperado al finalizar el proceso. En consecuencia, el problema de maximización de influencia requiere un parámetro “k”, de manera de encontrar un conjunto de “k” nodos de máxima influencia.

Kempe utiliza la misma estrategia que para el LT, que consiste en considerar que la función de influencia resultante σ() es submodular (concepto explicado en subsección anterior). A través de un teorema y una afirmación, y las demostraciones de las mismas, prueba que la suposición es correcta. En primera instancia, aplica las probabilidades (p) a las aristas de manera uniforme en un valor entre 0.01 y 0.1. En caso de paralelismo de aristas, es decir, si “u” y “v” tuviesen “cu,v” aristas paralelas, entonces se asume que la probabilidad de “u” de activar “v” equivale a: 1 ­ (1­p)cu,v. El IC con dicha aplicación de probabilidades “p” en las aristas, tiene la propiedad de que los nodos de alto grado no sólo tienen la oportunidad de influir en muchos otros nodos, sino también de ser influenciado por ellos. Es por ello, que Kempe estudia el caso particular del IC, denominado “Weighted Cascade” (WC), en el cual a cada arista de un nodo “u” a uno “v” se le asigna la probabilidad 1/dv de activar “v” (siendo dv el grado del nodo “v”). Es decir, en aristas de nodos de alto grado, la probabilidad asignada es más pequeña. Esta especie de cascada con ponderaciones se asemeja al LT en que el número de vecinos esperados que tendría éxito en la activación de un nodo “v” es 1.

Como se desarrolla en la subsección anterior, en [3] los experimentos comparan un algoritmo Greedy (sobre los modelos LT e IC) con heurísticas basadas en los grados de los nodos y la centralidad dentro de la red, así como con la elección al azar de los nodos a seleccionar. Los resultados arrojan un patrón similar de diferencias porcentuales respecto del IC con Greedy y con las heurísticas (a favor del Greedy como en el LT). Sin embargo, cabe destacar que la escala es

17

diferente entre el LT y el IC en un 25% de mayor alcance de nodos activados a favor del Linear Threshold Model.

2.3.4. Trivalency Model (TR) De manera similar a los modelos LT e IC, en el Trivalency Model las

probabilidades a los enlaces entre nodos se asignan siguiendo un criterio. En este caso, el TR se basa en que a cada arista u→v de manera uniformemente al azar se le asigna un valor de probabilidad perteneciente al conjunto 0.1; 0.01; 0.001. Los valores de dicho conjunto corresponden a niveles de influencia y dependen del tipo de relación. Por ejemplo en este caso podría decirse que existen tres niveles de influencia que son alto (0.1), medio (0.01) o bajo (0.001).

Tras la investigación de diferentes papers en los que se utiliza este modelo [4, 41, 42], resulta interesante destacar la heurística propuesta en [41]. Particularmente, se parte del problema de escalabilidad presentado por el algoritmo Greedy de Kempe en [3] (tratado en subsecciones anteriores). La heurística en cuestión gana eficiencia restringiendo computaciones en las regiones de influencia local (directa) de los nodos. La idea principal del esquema es usar estructuras de arborescencia local de cada nodo para aproximar la propagación de influencia. 8

Primero computar las rutas de máxima influencia (MIP) entre cada par de nodos en la red utilizando el algoritmo de ruta más corta de Dijkstra, ignorando MIPs con probabilidad menor a cierto umbral, restringiendo así la influencia a una región local. Luego une los MIPs que empiezan y terminan en cada nodo, formando las estructuras de arborescencia que representan la región de influencia local de cada nodo. El detalle es que en esta heurística propuesta solo se considera influencia propagada a través de la arborescencia local antes mencionada. Este modelo lo denominan en [41] como MIA (maximum influence arborescence).

Luego demuestran que la propagación de influencia en MIA es submodular y que, es por ello que, el simple algoritmo greedy puede garantizar un gran porcentaje de la solución optimal. Dicho algoritmo sobre el modelo MIA es muy eficiente por dos razones: la computación de la propagación de la influencia marginal en las estructuras de arborescencia puede resolverse con recursión eficiente; la otra razón, es que tras seleccionar una semilla con la mayor propagación de influencia, solo necesita actualizar las estructuras de arborescencia local relacionadas con dicha semilla para la selección de la próxima. Sin embargo, puede ocurrir que una semilla si este en el MIP de otra semilla sj hacia un nodo “v”, en tal caso la influencia de sj hacia “v” está completamente bloqueada por si. Para aproximar mejor la propagación de influencia, en el mismo paper, proponen extender el MIA para habilitar a sj en casos como el anterior a encontrar una ruta alternativa hacia “v” que no pase por si. La dinámica de esta extensión consiste en que al seleccionar la

8 Arborescencia es un árbol en un grafo dirigido donde todas sus aristas están apuntando hacia la raíz (in­arborescence) o todas apuntando hacia fuera de la raíz (out­arborescence).

18

semilla siguiente, para cada nodo “v” se calcula su arborescencia (hacia la raíz ­ in) de manera que cada semilla candidata “w” ∈ V tenga su camino hacia “v” sin pasar a través de ninguna semilla contenida en S. Como resultado, todas las semillas seleccionadas forman una secuencia S de acuerdo al orden de selección, de forma que toda semilla “s” en S tiene una ruta a todos los nodos “v” que no pasan a través de ninguna semilla en el prefijo de S precediendo “s”. Este tratamiento permite tener un algoritmo eficiente y es denominado PMIA (prefix excluding MIA).

Los experimentos realizados en [41] sobre diversos datasets (Amazon, NetHEPT, Epinions y DBLP) muestran que bajo la aplicación de distintas heurísticas (PMIA, PageRank, random, Greedy) se obtienen mejores resultados sobre el modelo WC (Weighted Cascade) visto en la subsección anterior que sobre el Trivalency Model.

2.3.5. Credit Distribution Model (CD) En los modelos vistos en las subsecciones anteriores (LT, IC, TR) se asignan

las probabilidades a los enlaces entre nodos siguiendo diversos criterios, como igual valor a todos los enlaces o aleatoriamente entre un conjunto predefinido. A diferencia de estos, el Credit Distribution Model permite aprender las probabilidades a partir de propagaciones anteriores que fueron registradas. Está demostrado que se logran mejores resultados obteniendo las probabilidades de los enlaces de la manera recientemente mencionada [1, 4]. En particular Goyal, Bonchi y Lakshmanan, desarrollan dos experimentos sobre datasets provistos por las redes sociales Flixster y Flickr . Cabe aclarar que realizan pruebas tomando ambos 9 10

datasets en su totalidad y también de manera parcial como muestra la tabla a continuación:

Tras los experimentos realizados, concluyen que todos los métodos que

utilizan probabilidades basadas en asunciones ad hoc seleccionan conjuntos muy diferentes de los métodos que usan registros de propagación para aprender las mismas. A su vez, la aplicación de ruido sobre el aprendizaje de probabilidades, no afecta de manera drástica la selección de las semillas. En tercer lugar, como se enunció previamente, el aprendizaje de las probabilidades obtuvo mejores resultados en cuanto a la propagación de la influencia (respecto al conjunto de

9 Flixster: uno de los principales sitios en lo que respecta al feedback o rating de películas, tanto como red social como mobile [43]. Una acción aquí se considera al usuario puntuando a una película. 10 Flickr: una plataforma popular de compartimiento de fotos. Una acción aquí es es un usuario uniéndose a un grupo de interés (por ejemplo, “Autoretrato Nikon” o “HDR Panoramas”).

19

semillas seleccionado), que las probabilidades que son asignadas por los demás métodos.

En [4], definen como objetivo de su trabajo, proponer una solución escalable a la maximización de influencia con garantía de aproximación. Para ello es preciso indicar el contexto y notaciones particulares para explicar los conceptos y fórmulas. Dado un grafo social G = (V,E) con nodos V, correspondientes a los usuarios; aristas dirigidas no ponderadas E, correspondientes a los vínculos sociales entre los mismos; y un log de acciones, en donde se establece una relación L (Usuario, Acción, Tiempo), y una tupla (u, a, t)∈ L indica que el usuariou realizó la accióna en un tiempo t. Además, se asume que un usuario realizó al menos una acción, y se define la función t(u, a) que retorna el tiempo en el que dicho usuario llevó a cabo dicha acción. Se dice entonces, que una accióna se propaga de un nodou a unov, si y sólo si, u yv están socialmente vinculados, yu hace la acción a antes quev. En otras palabras, se determina que u influenció a v.

Este enfoque, asume a “path(S, u)” como una variable aleatoria que indica si existe un camino directo del conjunto S hacia u con el valor 1, y en cualquier otro caso toma el valor 0. De esta manera formulan que la propagación esperada de un conjunto S (semillas iniciales) es la suma de las probabilidades de cada nodo u (perteneciente a V) de ser activado por dicho conjunto S:

σm(S) = ∑ueV Pr[path(S, u) = 1] La idea es estimar directamente Pr[path(S, u) = 1] usando los rastros de

propagación que se poseen en el log de acciones. Para ello, se necesitaría un enorme número de registros de propagaciones correspondientes a diversas combinaciones, donde cada rastro tuviese como conjunto iniciador precisamente al conjunto requerido S. Como resulta impracticable hallar un log de acciones donde esto sea real, se propone un enfoque diferente para estimar Pr[] tomando una perspectiva “u­centric”. En esta se asignan créditos a los posibles influenciadores de un nodo u, siempre que u realice una acción.

La notación siguiente será utilizada en el desarrollo de la dinámica del modelo y es extraída de [4]:

Simbología Significado

Au Número de acciones realizadas por u.

Nin(u,a) Vecinos de u que realizaron la acción a, antes que él. Es decir, potenciales influenciadores sobre dicha acción.

γv,u(a) Crédito de influencia directo designado a v por influenciar a u en la acción a.

Γv,u(a) Total de crédito asignado a v por influenciar a u en la acción a.

20

kv,u Total de créditos asignados a v por influenciar a u en todas las acciones.

Γx,uW(a) Total de crédito asignado a x por influenciar a u en la acción a, considerando los caminos que están completamente contenidos en W ⊆ V.

τv,u Tiempo promedio tomado por las acciones para propagarse del usuario v al usuario u.

Cuando un usuario u realiza una acción a, se le asigna crédito de influencia

directa (γv,u(a)) a todo nodo v ∈ Nin(u,a). En primera instancia, explican que se le asigna la misma cantidad de créditos a dichos nodosv, aunque luego enuncian una asignación más sofisticada. La restricción es que la suma de los créditos directos asignados a los vecinos no puede superar el valor 1. La idea también es distribuir los créditos transitivamente hacia atrás en el grafo de propagación G(a), de manera que no solo u asigne créditos a los usuarios v ∈ Nin(u,a), sino que a su vez pasen créditos a sus predecesores en G(a) y así sucesivamente. Esto permite definir la adjudicación total de créditos a un usuario v por influenciar a u en la acción a, correspondiendo a múltiples rutas de propagación:

donde la base de la recursión es Γv,v(a) =1.

A continuación se muestra un breve ejemplo, sobre el grafo representado en la Figura 2.1, cuya asignación de créditos directos es γv,u(a) = 1/din(u,a):

Figura 2.1: Grafo de influencia con aristas etiquetadas con créditos directos.

Partiendo de dicho grafo, el total de créditos asignados av por influenciar au

en la acción a, correspondiendo a múltiples rutas de propagación equivale a:

De igual manera, se define el total de crédito concedido a un conjunto de

nodos S ⊆ V por influenciar al usuario u en la acción a de la siguiente forma:

21

si v ∈ S; cualquier otro caso;

Utilizando nuevamente el grafo de la Figura 1, el resultado de la fórmula recientemente expresada, tomando como conjunto S a v,z, sería:

Lo siguiente a considerar, sería trasladar los conceptos anteriores a todo el

log de acciones. De esta forma, teniendo en cuenta los nodos u y v, el total de los créditos de influencia entregado a v por u para todas las acciones A, se obtiene simplemente tomando el total de créditos de todas las acciones y normalizando por el número de acciones realizadas por u (Au). Esto es así ya que el usuariou asigna créditos hacia atrás a sus potenciales influenciadores, y se formula de esta manera:

Que para el caso del conjunto de nodos S ⊆ V, se definiría de la siguiente

forma: donde kS,u corresponde a Pr[path(S,u) = 1].

Volviendo a la ecuación de la propagación esperada de un conjunto S, que fue enunciada con anterioridad en esta subsección, σm(S) = ∑ueV Pr[path(S, u) = 1], al indicar σcd(S) como el total de créditos de influencia asignados a S por toda la red social, se define:

Siendo esta la función que se desea maximizar.

Luego de trabajos previos realizados [44], Goyal, Bonchi y Lakshmanan

observaron que la influencia decae con el tiempo en una moda exponencial y que algunos usuarios son más influenciables que otros. Es por ello, que proponen que la asignación de crédito directo sea de la siguiente forma:

Donde tv,u como se explicó en la tabla de notación, es el tiempo promedio

tomado por las acciones para propagarse del usuario v al usuario u. El término exponencial logra el efecto deseado de la influencia decayendo en el tiempo. Por

22

otro lado, infl(u) representa la influenciabilidad, que denota qué tan propenso es el usuario u a la influencia del contexto social. Más precisamente, infl(u) es definida como la cantidad de acciones que u lleva a cabo bajo la influencia de al menos uno de sus vecinos.

Una vez comprendido lo anterior se procede al problema de maximización de influencia que bajo este enfoque (CD model) queda expresado como: Dado un grafo social dirigido G=(V,E), un log de acciones L, y un entero k <= |V|, encontrar un conjunto S ⊆ V, |S| = k, que maximice σcd(S).

Partiendo de allí, en [4] proceden a demostrar que el problema es NP­hard y 11

es por ello que buscan un algoritmo de aproximación. Para desarrollarlo, primero prueban que la función σcd(S) es monótona y submodular. Una vez comprobado, proceden en la formalización de un algoritmo. En el caso de modelos como el IC y el LT, el algoritmo de Greedy no garantiza eficiencia en sí mismo ya que requiere determinar las ganancias marginales de un nodo candidato respecto al actual conjunto de semillas, y lo realiza con costosas simulaciones Montecarlo (MC). En 12

el caso del CD, la ganancia marginal puede ser directamente computada desde el log de acciones L. Una sencilla manera de hacerlo sería, escanear L en cada iteración, lo que resultaría muy ineficiente. Motivados por ello, proponen que considerando el superíndice W ⊆ V en la función Γ(∙), se induce a dicha función, a ser evaluada en el sub­grafo generado por los nodos en W. De esta manera, Γx,uW(a) es el total de créditos asignados al nodo x por influenciar al nodo u a realizar la acción a considerando los caminos que son contenidos completamente en el sub­grafo generado por V(a) ∩ W. Que, en otras palabras, es el sub­grafo del grafo de propagación para la accióna, generado por dichos nodos. Cuando el superíndice no está presente, el grafo considerado es todo el grafo de propagación para la acción a, es decir, Γx,u(a) = Γx,uV(a)(a). Además debe ser destacado que el crédito directo es siempre asignado considerando todo el grafo de propagación. En consecuencia, explotando algunas propiedades del modelo, logran determinar la ganancia marginal de una manera eficiente que puede resumirse del siguiente modo (citado/traducido de [4]):

11 NP­hard: en teoría de complejidad computacional, es el conjunto de problemas de decisión que contiene los problemas H, tales que todo problema L en NP puede ser transformado polinomialmente en H. Es un problema al menos tan difícil como NP, pero no necesariamente es NP. Entonces si se puede encontrar unalgoritmo A que resuelve uno de los problemas H de NP­hard entiempo polinómico, es posible construir un algoritmo que trabaje en tiempo polinómico para cualquier problema de NP ejecutando primero la reducción de este problema en H y luego ejecutando el algoritmo A. 12 Simulación Montecarlo: consiste en crear un modelo matemático del sistema a analizar, identificando aquellas variables (inputs del modelo) cuyo comportamiento aleatorio determina el comportamiento global del sistema. Luego se lleva a cabo un experimento que genera muestras aleatorias (valores concretos) para dichos inputs, y se analiza el comportamiento del sistema. Tras repetir n veces este experimento, se dispone de n observaciones sobre del sistema, lo cual es útil para entender el funcionamiento del mismo.

23

1. Inicialmente, escanear el log y determinar Γv,u(a) para todas las combinaciones de v, u y a. Notar que al comienzo, S=∅y por consiguiente ΓS,x(a)=0 para todas las combinaciones de x y a.

2. En cada iteración del método Greedy, el nodo que provee la máxima ganancia marginal es agregado al conjunto de semillas. En este paso, adoptan la idea de optimización de CELF (del inglés, Cost­Effective Lazy Forward selection) [45].

3. Para determinar la ganancia marginal de un nodox eficientemente, utilizan un teorema que muestra lo siguiente:

En palabras, dice que la ganancia marginal de un nodox es igual a la suma de las ganancias marginales normalizadas de x en todas las acciones.

4. Una vez que un nodo es agregado al conjunto de semillas, los valores de Γv,uV­S(a) y ΓS,x(a) (obtenidos en el ítem 3) son actualizados usando los siguientes lemas:

a. Donde este valor es el crédito total asignado al nodov menos el crédito que le fue asignado por los caminos que pasan por el nodo x. Esto surge de la suposición de que se agrega x al conjunto de semillas y entonces debe determinarse Γv,uW­x(a). Considerando el sub­grafo generado por los nodos W = V­S.

b. Este lema muestra cómo actualizar incrementalmente el crédito total asignado a un conjunto S por un nodo u, luego de que x es añadido a dicho conjunto.

Una vez definido el algoritmo, realizan experimentos sobre los datasets antes

mencionados de las redes Flixster y Flickr. Los resultados obtenidos son mejores en todos los ámbitos de comparación que los obtenidos por los modelos LT e IC. Los criterios comparados son la precisión de las semillas predichas, la calidad de la selección de semillas, el tiempo de ejecución y la escalabilidad. Además realizan experimentos adicionales sobre el CD y el algoritmo de maximización de influencia basado en el mismo, para explorar el impacto del tamaño del conjunto de datos de

24

entrenamiento sobre la calidad de la solución, y el impacto del umbral de truncamiento en la calidad, el tiempo de ejecución y el uso de memoria.

En resumen, el Credit Distribution Model calcula directamente la propagación de influencia explotando datos históricos, evitando así la necesidad de aprender las probabilidades, y además evitando las costosas simulaciones Montecarlo que es la forma estándar de estimar la diseminación de la influencia. En base a esto, en [4] desarrollan un algoritmo eficiente para la maximización de la influencia que es, en adición, altamente escalable.

2.4. Trabajos Relacionados Los trabajos relacionados con la influencia en redes sociales, en su mayoría

apuntan a la determinación de usuarios más influyentes y diversas estadísticas. Es decir, la aplicación de la influencia que analizan es el ranking o clasificación de usuarios, y no el problema de maximización planteado en la presente tesis. De todas maneras, se destaca que a nivel científico, sí se plantean diversos algoritmos y heurísticas para resolver de manera eficiente el problema y se comparan los resultados bajo distintos criterios.

Respecto a las aplicaciones o servicios web que son utilizados en la actualidad para la clasificación de usuarios, es interesante exponer algunas de sus características. Una de las herramientas gratuitas más conocidas es Klout [46], que mide la influencia social que tenga una persona a través de las redes sociales a las cuales pertenece (Facebook, Twitter, Instagram, Google+, LinkedIn, Wikipedia, YouTube, Flickr, Blogger, Wordpress, Tumblr, etc.). Dicha influencia se ve reflejada en un puntaje denominado Klout Score (0 a 100) que se basa en combinaciones de atributos que son medidos por esta aplicación, como la proporción de reacciones que genera un usuario respecto al contenido que comparte. Por ejemplo, generar cien retweets de diez tweets contribuye más a la puntuación, que generar los mismos retweets pero de mil tweets. También tiene en cuenta factores como lo selectiva que es la que gente que interactúa con el contenido del usuario. Es decir, si el que interactúa acostumbra a compartir o relacionarse en más publicaciones, menos contribuyen sus interacciones. Además considera más importante obtener cien retweets de personas distintas, que cien de una misma. Por último destacan que proveen un sistema de detección de comportamientos fraudulentos como robots de spam para no afectar las puntuaciones.

El promedio de los usuarios de Klout es de 40 y se considera como un Influencer (influyente) a aquellas personas con un índice alto por encima de la media, es decir, los que pertenecen al grupo del 5% de usuarios con un valor superior a 60 están considerados como los más influyentes. No es un índice cuantitativo que mida el volumen de contenidos generados o de seguidores de una persona, sino la capacidad de influir que tiene al transmitir sus contenidos o, citado

25

del sitio web de Klout , “capacidad de generar acciones”. En Estados Unidos llegó a 13

utilizarse como criterio de selección para determinados empleos y para ofrecer a los Influencers promociones, regalos, productos y servicios exclusivos, llamados Perks.

A diferencia de establecer el Klout Score, otra de las herramientas conocidas como lo es Audiense (antes SocialBro) [47], utiliza el algoritmo de Kred para establecer el puntaje. En el caso de Kred [48], son solo dos redes sociales que se pueden conectar (Facebook y Twitter). El índice de Kred está compuesto a su vez por dos medidas, la influencia y el outreach (forma de interacción con el contenido de los seguidores). Lo que hace especial a esta herramienta es que no solo indica la influencia, sino la generosidad en las interacciones propias para con otros usuarios. Es decir, el usuario visto como seguidor (outreach) y como seguido (influencia). El puntaje de influencia se mide en una escala de 0 a 1000 y el del outreach de 1 a 12. La transparencia de las reglas a la hora de la medición también hacen particular a esta herramienta. Kred otorga una serie de puntos por cada interacción en las dos redes sociales que monitoriza. Por ejemplo, en la Tabla 2.1 se muestran valores para Twitter y en la Tabla 2.2 para Facebook, en la medición de la influencia.

Interacción Puntos De Influencia

Retweet o mención de una cuenta con menos de 10000 seguidores

10

Retweet o mención de una cuenta con más de 10000 seguidores

25

Retweet o mención de una cuenta con menos de 100000 seguidores

50

Nuevo seguidor 1

Tabla 2.1. Puntos de influencia otorgados por Kred en las interacciones de la red social Twitter. Extraída de http://home.kred/rules/ .

Interacción Puntos De Influencia

Una cuenta escribe en tu muro 20

Una cuenta comparte un link tuyo 20

Una cuenta te menciona 10

Una cuenta te menciona en un comentario 5

Una cuenta comenta en tus publicaciones 5

13 Sitio original de Klout donde trata el Klout Score: https://klout.com/corp/score

26

Recibir una invitación a un evento 5

Una cuenta indica que le gusta tu publicación 3

Añadir un nuevo amigo 1

Tabla 2.2. Puntos de influencia otorgados por Kred en las interacciones de la red social Facebook. Extraída de http://home.kred/rules/ .

Por otro lado, también se establecen valores para los puntos de outreach

como se muestran en las Tablas 2.3 y 2.4 para Twitter y Facebook, respectivamente.

Interacción Puntos De Outreach

Retweet 10

Respuesta o Mención 10

Seguir a una cuenta 1

Tabla 2.3. Puntos de outreach otorgados por Kred en las interacciones de la red social Twitter. Extraída de http://home.kred/rules/ .

Interacción Puntos De Outreach

Publicar en el muro de alguien 20

Mencionar o etiquetar a alguien en una publicación 10

Mencionar o etiquetar a alguien en un comentario 5

Comentar en una publicación 5

Indicar “Me Gusta” en una publicación 3

Hacerse amigo de alguien 1

Tabla 2.4. Puntos de outreach otorgados por Kred en las interacciones de la red social Facebook. Extraída de http://home.kred/rules/ .

La escala para determinar el nivel de outreach se basa en la siguiente tabla

de conversión:

Puntos 100 270 729 1968 5314 14349 38742 104604 282430 762560 2058911

Nivel 1 2 3 4 5 6 7 8 9 10 11

27

Tabla 2.5. Tabla de conversión de puntos a niveles de outreach. Extraída de http://home.kred/rules/ .

Según un estudio realizado por Kred [49], en 2011, la mayoría de los usuarios (37%) se encuentran en el rango entre 451 y 600 puntos de influencia, y el 29% entre 301 y 450. Además, el 21% entre 601 y 800, y notoriamente solo el 0.1% entre 800 y 1000 puntos.

De todas maneras, cabe destacar que Audiense es una herramienta paga que como se mencionó anteriormente tiene integrado en su plataforma el algoritmo de Kred.

También existen otras herramientas dirigidas a la influencia en una sola red social, como LinkedIn Pulse sobre LinkedIn [50], CircleCount [51] y Circlescope [52] sobre Google+, Booshaka [53] sobre Facebook, o Quantico [54], Followerwonk [55], Klear (antes Twtrland) [56] y Topsy [57] sobre Twitter. Lo interesante de todas estas herramientas y las dos explicadas anteriormente (Audiense­Kred y Klout), es que ofrecen múltiples opciones muy similares. Uno de los asuntos es la aplicación de filtros que resulta sumamente importante ya que todas lo proveen. En la mayoría se puede filtrar por diversas categorías con su temática, o por keywords (palabras claves), o por idioma, o por geolocalización. Incluso algunas de ellas permiten refinar los filtros y segmentar la búsqueda por antigüedad de una cuenta, el ratio de seguidores y seguidos, entre otras opciones. Otro de los asuntos que comparten es la información que se visualiza en los resultados de las búsquedas y rankings. En general se muestra el perfil del usuario, contactos, un puntaje de influencia, interacciones recientes, horas de mayor actividad, alcance, temáticas más recurrentes, ubicación geográfica e incluso algunas herramientas muestran información de los seguidores o seguidos por el usuario en cuestión.

Sin embargo, otra de las características en común de las herramientas analizadas es que no tienen en cuenta el factor tiempo a la hora de determinar la influencia de los usuarios. Tampoco se establecen de manera clara las categorizaciones o temáticas. Es decir, en qué se basan para definir que un usuario o una interacción pertenecen a cierta categoría. Además como se mencionó previamente lo que resuelven es el problema de Ranking o Clasificación de usuarios pero no el de maximización de influencia. Si bien es importante determinar la influencia individual de cada usuario de la red, seleccionar a un conjunto de ellos no nos asegura la maximización de la influencia. Un claro ejemplo es cuando dos usuarios son muy influyentes pero sus seguidores son los mismos o conjuntos muy similares. Con seleccionar a uno de ellos bastaría para cubrir dicho conjunto de usuarios, y elegir a los dos no aumentaría significativamente el alcance de las semillas sobre la red.

28

3. Enfoque En este capítulo se describe el enfoque propuesto para la identificación de

nodos influyentes en una red social de Microblogging. En particular se trabaja sobre la red social Twitter. Este enfoque es materializado en la herramienta “TSeedS: Twitter Seed Set”, que determina minuto a minuto los usuarios más influyentes (en base a una temática) en la red social antes mencionada. Además permite la visualización de los resultados a través de gráficos. De esta forma, con el transcurso del tiempo pueden estudiarse diversos aspectos de la influencia del usuario y de la temática.

En la sección 3.1 se presenta el modelo conceptual del enfoque. En esta sección se introducen cada una de las etapas desde la captura de la información hasta la determinación de los usuarios más influyentes y su evolución en el tiempo.

En las secciones siguientes se describen las distintas etapas presentadas en la sección 3.1. En particular, la sección 3.2 describe la primera etapa, en la que se obtiene la información de la red social. Luego en la sección 3.3. se describe la generación de estructuras internas (segunda etapa). Estas refieren al Grafo Social y al Registro de Propagaciones que son profundizadas en 3.3.1 y 3.3.2.

En la sección 3.4 se describe la tercera etapa que refiere a la determinación del conjunto de semillas con la utilización de una herramienta externa. En la sección 3.4.1 se indican las entradas que se requieren en dicha herramienta y la generación de las mismas. En la sección 3.4.2 se describe el algoritmo que utiliza la herramienta y distintas funciones que la misma ofrece.

En la sección 3.5, se describe cómo se deben interpretar los resultados obtenidos (cuarta etapa) por la herramienta antes mencionada. Finalmente, en la sección 3.6 se analiza la quinta etapa del presente enfoque. Además se introduce brevemente, a los distintos análisis que permite realizar la visualización de resultados. Esta última realizada a través de gráficos sobre el usuario y su influencia en función del tiempo.

Cabe destacar que en 3.2 se presenta un listado de interacciones de la red social Twitter que será utilizado como hilo conductor de la explicación de las etapas posteriores para facilitar la comprensión del lector.

3.1. Modelo Conceptual Este trabajo busca definir un enfoque que nos brinde el conjunto de usuarios

influyentes de una red social dada una temática, dicha red social de la cual obtener información y un intervalo de tiempo,. Además se busca que la propagación de la influencia sea maximizada si se convence a los nodos indicados (usuarios influyentes) de realizar una acción. El enfoque parte de obtener información de una

29

red social realizando un filtrado por categorías en tiempo real. Como fue descrita en la sección 2.1.1, la red social en cuestión es Twitter. Por ende, lo expresado anteriormente sobre obtener información corresponde a escuchartweets,retweets y respuestas (replies) en tiempo real y procesar dichas interacciones como acciones. La red social se formará entonces con los usuarios participantes en dichas interacciones. Sobre dicha red social se seleccionará un conjunto de semillas que maximice la propagación de la influencia. Luego, con el avance del tiempo, se podrá visualizar en un gráfico, la posición de los usuarios en el conjunto de semillas, según su nivel de influencia. En la Figura 3.1 se ilustra un modelo conceptual del sistema.

Figura 3.1. Modelo conceptual del enfoque propuesto.

La Figura 3.1 nos muestra cómo a partir del análisis de las interacciones de

los usuarios de Twitter se obtiene la información sobre la cual se trabajará. Para esto, en la etapa 1 del enfoque se aplica un conjunto de filtros a fin de acotar los datos con los que se generará la información. Por su parte, la herramienta permite acotar la información a una temática específica, así como también a un rango temporal e idioma de los tweets a procesar.

Una vez que la información es obtenida, se procede a consolidarla en un Grafo Social y un Registro de Propagaciones. Las estructuras resultantes de esta segunda etapa permiten establecer las relaciones existentes entre los usuarios contenidos en la información obtenida.

30

La tercera etapa refiere a la Obtención del Conjunto de Semillas utilizando la herramienta Influence Models. Esta etapa se subdivide en dos partes que corresponden al volcado de la información (transcurrida cierta ventana de tiempo) y a la ejecución de la herramienta antes mencionada. La primera parte, refiere a la generación de las entradas en el formato que la herramienta Influence Models exige. La segunda parte, refiere a la ejecución de la herramienta bajo la configuración deseada.

La cuarta etapa se materializa, luego de la ejecución del Influence Models, en la Interpretación de los Resultados obtenidos. Estos resultados son el conjunto de semillas y su influencia marginal. Previamente en el presente trabajo se describió el problema de maximización de influencia social como al problema de obtener un conjunto de “k” nodos que al “estimularlos” la influencia sobre la red social es maximizada. Dicho conjunto de nodos se denomina Seed Set o conjunto de semillas.

Finalmente, como una quinta etapa, se encuentra lo referido a la Visualización de los Resultados. Esta etapa permite apreciar de forma sencilla la evolución de la influencia de cada usuario que es o fue al menos una vez semilla durante la ejecución de TSeedS.

En las secciones siguientes se describen en detalle las etapas antes mencionadas. Para una mejor comprensión, se establece un ejemplo que aborda desde la primera etapa de la escucha de interacciones hasta la última de la visualización de los resultados.

3.2. Obtención de Información de la Red Social

En esta etapa se monitorea en tiempo real las interacciones y acciones de la red social Twitter y se filtran aquellas que resultan de interés. Para ello, Twitter provee una API que establece un canal directo con el flujo de información proveniente de la red en tiempo real. Esto último se conoce también como streaming. Sobre este mismo canal se aplica el primer filtro de interés que es el de la categoría. Dicho filtro indica que el tweet, retweet o respuesta (reply) será tenido en cuenta en la herramienta sólo si contiene alguna de las palabras indicadas en la configuración. Dichas palabras se conocen como “keywords” (palabras claves) y un conjunto de las mismas definen la categoría de interés. A continuación se ilustra un pequeño ejemplo de la aplicación de este filtro, donde se presentan las keywords especificadas en el archivo de configuración y una serie de tweets escuchados por el stream en distintos horarios.

31

Figura 3.2. Keywords de interés de la categoría.

Como se mencionó anteriormente en la Figura 3.2 se presenta el listado de

palabras que definen a la categoría deseada. Como puede apreciarse se definen palabras con y sin acento para no perder los casos con errores de ortografía. También se definen las palabras compuestas que se desea encontrar.

Usuario Acción Tiempo Texto

@deportes102 Tweet 16.38 Importante cruce por el grupo A de copa libertadores entre river y the strongest

@maria304 Reply 17.52 @deportes102 vamos the strongest, a vencer a los argentinos y que viva el fútbol

@geoinfotravel Tweet 17.54 A lot of people was swimming along The River Plate in Arizona last Friday

@deportes102 Tweet 21.54 River plate se impone en el Monumental con un contundente 6­0

@jorge123 Tweet 21.54 Importante lavarse los dientes antes de ir a dormir para eliminar malos olores en la boca

@matias209 Reply 21.56 @deportes102 Que grande millonario que ganas de estar allí!

@laura301 Retweet 21.59 Boca juniors se mete en octavos de copa libertadores tras vencer a racing de visitante

@ezequiel403 Retweet 22.02 Boca juniors se mete en octavos de copa libertadores tras vencer a racing de visitante

@ines506 Retweet 22.06 River plate se impone en el Monumental con un contundente 6­0

@90minutos Tweet 22.08 En breve estaremos con una nueva edición de 90 Minutos de Fútbol por Fox

@anibal598 Reply 22.10 @roberto105 mejor dedicate a la jardinería y dejá el fútbol!

Tabla 3.1. Interacciones interceptadas por el stream de Twitter.

32

La Tabla 3.1 contiene un listado de 11 interacciones escuchadas en el canal de streaming previo a la aplicación de filtros.

Cuando se aplica el filtro de categorías antes explicado, las interacciones que no cumplen con el mismo son descartadas. En la Tabla 3.2 se presentan los resultados de la aplicación del filtro. Con color naranja se remarcan aquellostweets, retweets y replies que conforman interacciones consideradas no válidas. En las interacciones válidas (aquellas con fondo de color celeste) se marca con color rojo las palabras que hicieron que se cumpla el filtro aplicado. Como se expresó antes, esto se ilustra en la Tabla 3.2.

Usuario Acción Tiempo Texto

@deportes102 Tweet 16.38 Importante cruce por el grupo A decopa libertadores entre river y the strongest

@maria304 Reply 17.52 @deportes102 vamos the strongest, a vencer a los argentinos y que viva el futbol!

@geoinfotravel Tweet 17.54 A lot of people was swimming along The

River Plate in Arizona last Friday

@deportes102 Tweet 21.54 River plate se impone en el Monumental con un contundente 6­0

@jorge123 Tweet 21.54 Importante lavarse los dientes antes de ir a dormir para eliminar malos olores en la boca

@matias209 Reply 21.56 @deportes102 Que grande millonario que ganas de estar allí!

@laura301 Retweet 21.59 Boca juniors se mete en octavos decopa libertadores tras vencer a racing de visitante

@ezequiel403 Retweet 22.02 Boca juniors se mete en octavos decopa libertadores tras vencer a racing de visitante

@ines506 Retweet 22.06 River plate se impone en el Monumental con un contundente 6­0

@90minutos Tweet 22.08 En breve estaremos con una nueva edición de 90 Minutos de Fútbol por Fox

@anibal598 Reply 22.10 @roberto105 mejor dedicate a la jardinería y dejá el fútbol!

Tabla 3.2. Interacciones del stream bajo la aplicación del filtro de categoría.

33

El siguiente filtro que se aplica sobre elstreamestá relacionado con el idioma que utilizan los usuarios. Este filtro se propone con el objetivo de intentar mejorar la categoría en cuestión y no dando lugar a distintos posibles significados de las keywords. Es decir, se busca que una palabra en un idioma no se confunda con el uso de la misma palabra en otro idioma. Cabe destacar que no siempre este filtro optimiza la categoría, ya que existen casos en los que las palabras, en especial los nombres propios, se encuentran bien utilizados y sin embargo no sobrepasan este filtro. De todas maneras, los idiomas de interés pueden indicar de manera indirecta un filtro por geolocalización del usuario (país de origen). En la Figura 3.3, se ilustra un listado de los idiomas habilitados por el filtro de idioma y en la Tabla 3.3 se muestran en color naranja las interacciones que (tras sobrepasar el primer filtro) no atraviesan el actual filtro de idioma.

Figura 3.3. Lista de idiomas permitidos. es (español) ­ und (indeterminado)

Usuario Acción Tiempo Texto

@deportes102 Tweet 16.38 Importante cruce por el grupo A de copa libertadores entre river y the strongest

@maria304 Reply 17.52 @deportes102 vamos the strongest, a vencer a los argentinos y que viva el futbol!

@geoinfotravel Tweet 17.54 A lot of people was swimming along The River Plate in Arizona last Friday

@deportes102 Tweet 21.54 River plate se impone en el Monumental con un contundente 6­0

@laura301 Retweet 21.59 Boca juniors se mete en octavos de copa libertadores tras vencer a racing de visitante

@ezequiel403 Retweet 22.02 Boca juniors se mete en octavos de copa libertadores tras vencer a racing de visitante

@ines506 Retweet 22.06 River plate se impone en el Monumental con un contundente 6­0

@90minutos Tweet 22.08 En breve estaremos con una nueva edición de 90 Minutos de Fútbol por Fox

34

@anibal598 Reply 22.10 @roberto105 mejor dedicate a la jardinería y dejá el fútbol!

Tabla 3.3. Interacciones del stream bajo la aplicación del filtro de idioma. La interacción rechazada en la Tabla 3.3, se debe a que la cuenta

@geoinfotravel acusa que su idioma es inglés. En el caso que el idioma de dicha cuenta hubiese sido español o indeterminado la interacción habría sido aceptada, ya que no se detecta el idioma sobre el contenido deltweet sino sobre la cuenta que lo envió.

El tercer filtro que se aplica está relacionado directamente con el factor temporal del enfoque. Con este filtro se busca sólo analizar la información que se determina reciente y dentro de una cierta ventana de validez que también es configurable. A modo de ejemplo se considerará como válida a una interacción cuyo origen no supere los 60 minutos respecto del tiempo actual. Este filtro se aplica sólo en las acciones de retweet y reply, ya que los tweets se escuchan en tiempo real y por ende siempre son del momento. Sin embargo, si bien las dos interacciones entre usuarios antes mencionadas también son del momento, la diferencia radica en que el tweet de origen con el que se relacionan puede ser extremadamente antiguo. Por ejemplo, cuando se está respondiendo un tweet que ya tiene dos días de antigüedad. Partiendo de la base que las interacciones que se utilizan a modo de ejemplo fueron escuchadas por el stream en el horario en el que se indican, en la Tabla 3.4 se ilustran en naranja las que no pasan el filtro temporal. Además en la Figura 3.4 se muestra el contenido de la configuración que se desea utilizar como ventana temporal.

Figura 3.4. Parámetros temporales expresados en minutos

en el archivo de configuración correspondiente.

Usuario Acción Tiempo Texto

@deportes102 Tweet 16.38 Importante cruce por el grupo A de copa libertadores entre river y the strongest

@maria304 Reply 17.52 @deportes102 vamos the strongest, a vencer a los argentinos y que viva el futbol!

@deportes102 Tweet 21.54 River plate se impone en el Monumental con un contundente 6­0

@laura301 Retweet 21.59 Boca juniors se mete en octavos de copa libertadores tras vencer a racing de visitante

35

@ezequiel403 Retweet 22.02 Boca juniors se mete en octavos de copa libertadores tras vencer a racing de visitante

@ines506 Retweet 22.06 River plate se impone en el Monumental con un contundente 6­0

@90minutos Tweet 22.08 En breve estaremos con una nueva edición de 90 Minutos de Fútbol por Fox

@anibal598 Reply 22.10 @roberto105 mejor dedicate a la jardinería y dejá el fútbol!

Tabla 3.4. Interacciones del stream bajo la aplicación del filtro temporal.

En este filtro puede apreciarse que la interacción de la cuenta @maria304 es invalidada ya que ocurre pasados los 60 minutos. Este caso es fácilmente comprobado ya que además la acción original realizada por @deporte102 había sido escuchada por el stream en tiempo real. Por otro lado, la interacción de @ines506 si logra pasar el filtro ya que la acción original de @deporte102 se encuentra dentro del límite establecido de una hora. Nuevamente esto es comprobado ya que dicha acción original había sido escuchada por el stream en tiempo real.

Sin embargo, puede ocurrir que la interacción original no haya sido interceptada por el stream. Esto puede suceder por diversas razones, como el uso interrumpido (no continuo) de la herramienta o la antigüedad de las acciones que se referencian. Estos casos también son ilustrados en la Tabla 3.4, donde se puede notar que las interacciones de @laura301 y @ezequiel403 se determinan como válidas a pesar de que no se visualiza el tweet original de la cuenta @bocaoficial en el listado de interacciones. En estos casos utilizando la API de Twitter se logra acceder a la acción original y ésta se agrega a la lista de interacciones a registrar. Por otro lado, también puede verse que la interacción de la cuenta @anibal598 es tomada como inválida. Esto último se debe a que tras obtener la acción referenciada en la interacción se descubre que ésta tiene un tiempo de origen superior a los 60 minutos. Esto es es algo habitual en la red social Twitter, donde en múltiples oportunidades puede visualizarse cómo diversas cuentas retweetean o responden a tweets de días atrás o incluso hasta años. Esto es precisamente lo que se desea rechazar con el filtro temporal, interacciones que tienen un inicio anterior al de la ventana temporal que se está considerando.

En la Tabla 3.5 se listan las interacciones que finalmente serán utilizadas en la segunda etapa, tras haber atravesado los filtros anteriores. Nótese que el recuadro rojo se ubica sobre la acción que fue incorporada a la lista en base a las interacciones que la referencian y que fueron observadas inicialmente y en tiempos válidos. Es importante destacar que el streaming de Twitter provee sólo un

36

porcentaje de la totalidad de los tweets que se producen en un instante de tiempo. Este es el motivo por el cual es posible observar unretweet y no el original, a pesar de estar ambos dentro de la ventana temporal.

Usuario Acción Tiempo Texto

@deportes102 Tweet 16.38 Importante cruce por el grupo A de copa libertadores entre river y the strongest

@bocaoficial Tweet 21.49 Boca juniors se mete en octavos decopa libertadores tras vencer a racing de visitante

@deportes102 Tweet 21.54 River plate se impone en el Monumental con un contundente 6­0

@laura301 Retweet 21.59 Boca juniors se mete en octavos de copa libertadores tras vencer a racing de visitante

@ezequiel403 Retweet 22.02 Boca juniors se mete en octavos de copa libertadores tras vencer a racing de visitante

@ines506 Retweet 22.06 River plate se impone en el Monumental con un contundente 6­0

@90minutos Tweet 22.08 En breve estaremos con una nueva edición de 90 Minutos de Fútbol por Fox

Tabla 3.5. Interacciones finales tras la aplicación de los filtros y la agregación de acciones referenciadas.

En esta etapa se logra obtener la información del canal de Twitter y

completarla con solicitudes para obtener aquella información adicional faltante. Sin embargo, esto último no se vio evidenciado en la presente sección ya que la información que se solicita está relacionada con las relaciones entre usuarios y la detección de nodos intermedios. Estos conceptos se describen en la siguiente sección donde se puede apreciar que se aporta información adicional a la obtenida por el canal para la Generación de las Estructuras.

3.3. Generación de Estructuras

Como se mencionó con anterioridad, una vez obtenidas las interacciones correspondientes, se procede a establecer las relaciones entre los usuarios en un grafo dirigido y adjuntar las interacciones al registro de propagaciones. En las

37

subsecciones siguientes, se profundiza en la generación de ambas estructuras. Para poder visualizar lo realizado en esta etapa, se continúa con el ejemplo proveniente de la etapa anterior.

3.3.1. Grafo Social Para generar esta estructura, al arribar una interacción o acción válida se

procede a ingresar el usuario al sistema. Si el usuario no existe en el grafo es creado y agregado. En caso de ya pertenecer al grafo, el mismo queda sin cambios. Para identificar a los usuarios, Twitter utiliza un valor numérico único para poder manejar el volumen de usuarios de la red. Sin embargo, para trabajar dentro de la herramienta TSeedS se provee un mapeo local de dichos números a fin de optimizar el manejo de la clave de identificación de los usuarios.

A continuación se muestra cómo se arma el Grafo Social y el mapeo de los usuarios para el ejemplo que se utilizó en la etapa 1.

Interacción 1:

@deportes102 Tweet 16.38 Importante cruce por el grupo A de copa libertadores entre river y the strongest

Usuario identificado

ScreenName:@deporte102 ID:345679030240 Tras el arribo de la interacción en cuestión, se verifica que el usuario no está

ingresado en el sistema. Por ende, el usuario es creado y se le asigna un identificador normalizado para el mapeo local en la herramienta. El resultado del Grafo se ilustra en la Figura 3.5 junto con la tabla de mapeo.

Figura 3.5. Grafo Social y tabla de mapeo tras arribo de la interacción 1.

Interacción 2:

@deportes102 Tweet 21.54 River plate se impone en el Monumental con un contundente 6­0

38

Usuario identificado ScreenName:@deporte102 ID:345679030240 Tras el arribo de la interacción 2, se verifica que el usuario ya se encuentra

ingresado en el sistema. Por ende, el Grafo Social y la tabla de mapeo se mantienen de igual forma que la ilustrada previamente en la Figura 3.5. Interacción 3:

@laura301 Retweet 21.59 Boca juniors se mete en octavos de copa libertadores tras vencer a racing de visitante

Referencia Interacción:

@bocaoficial Tweet 21.49 Boca juniors se mete en octavos de copa libertadores tras vencer a racing de visitante

Usuarios identificados

ScreenName:@bocaoficial ScreenName:@laura301 ID:914390 ID:45608594845

Arista dirigida @laura301 → @bocaoficial Al arribar la interacción 3 (el retweet) y, junto con él, el tweet original, se

procede a verificar la existencia de los usuarios en el Grafo Social. Primero se comprueba que la cuenta asociada al tweet original no está ingresada. En base a ello, se crea y agrega el usuario al Grafo y se le asigna un identificador normalizado. De manera análoga sucede con el usuario que realiza el retweet. Dicho usuario no estaba ingresado, por ende, se le asigna un ID normalizado y se lo añade al Grafo. En este caso, debe además añadirse una arista dirigida para indicar quién realizó originalmente la acción.

Figura 3.6. Grafo Social y tabla de mapeo tras arribo de la interacción 3.

39

Interacción 4:

@ezequiel403 Retweet 22.02 Boca juniors se mete en octavos de copa libertadores tras vencer a racing de visitante

Referencia Interacción:

@bocaoficial Tweet 21.49 Boca juniors se mete en octavos de copa libertadores tras vencer a racing de visitante

Usuarios identificados

ScreenName:@bocaoficial ScreenName:@ezequiel403 ID:914390 ID:43758475

Arista dirigida

@ezequiel403 → @bocaoficial

Si bien la interacción 4 es extremadamente similar a la interacción 3, en este caso, el usuario del tweet original ya se encuentra ingresado en el sistema. Por ende, sólo se añade la cuenta que realizó el retweet y se le asigna un ID normalizado. Además se agrega la arista dirigida para indicar quién realizó la acción originalmente.

Figura 3.7. Grafo Social y tabla de mapeo tras arribo de la interacción 4.

Sin embargo, esta interacción anterior puede analizarse de distinta manera.

Motivados por el conocimiento de que en Twitter, un usuario puede realizar un retweet sin necesariamente seguir a dicha persona, se propone analizar el camino establecido entre el usuario original y el que interactúa. En nuestro ejemplo, se enuncia que @ezequiel403 retweetea de @bocaoficial. Con la utilización de otra API provista por Twitter se consulta si dicha cuenta que hace el retweet sigue a la del tweet original. La respuesta resulta ser que no, y por ello se decide buscar un usuario entre los que realizaron el retweet (el más reciente) de dicho tweet y que sea seguido por @ezequiel403. Para poder concretar dicha búsqueda se consulta a

40

Twitter por los retweets más recientes del tweet en cuestión. Teniendo estos retweets, se analizan las relaciones de los usuarios que los realizaron con la cuenta de interés previamente mencionada (@ezequiel403). Un posible caso sería, que de de dicha información resulte que @laura301 hizo retweet y también es seguida por @ezequiel403. Con esta información se determinaría que la relación es dirigida en sentido @ezequiel403 hacia @laura301 y no hacia @bocaoficial de manera directa como se pensaba en un principio. Es importante recordar que una arista y su dirección, indican quién realizó la acción originalmente y hacia quién se propagó. En este caso, la acción que se propaga es un retweet y no un tweet.

Sin embargo, otro posible caso podría ser que se identifique un retweet reciente de una cuenta que sigue @ezequiel403 pero que, a diferencia del caso anterior, el usuario no exista en el grafo. Por ende, la interacción no ha sido registrada. En dicho caso, la interacción y el usuario se agregan al sistema al igual que alguna vez se agregó la acción original de @bocaoficial. Además, podría ser que la relación entre el usuario intermediario y @bocaoficial tampoco sea directa, y que exista otro usuario intermediario lo que implicaría agregar dicho usuario e interacción también al sistema.

Es importante analizar esta forma de propagación de las relaciones ya que el Credit Distribution Model reparte créditos a sus influenciadores. Por lo tanto, al enlazar los nodos como corresponde, existiendo intermediarios o no, se obtendrían resultados más cercanos a la realidad. El agregado de intermediarios no necesariamente reduce la influenciabilidad de los originales, pero sí aumenta la de los nodos intermedios que definitivamente influencian a otros usuarios.

Tomando como ejemplo el caso en el que @ezequiel403 no sigue a @bocaoficial pero sí a @laura301, se ilustra en la Figura 3.8 cómo queda el Grafo Social representado. No se muestra la tabla de mapeo ya que se conserva en el mismo estado.

Figura 3.8. Grafo Social tras el arribo de la interacción 4

con inserción de nodo intermedio.

41

Finalmente se analizan las dos interacciones restantes (5 y 6 respectivamente), listadas a continuación:

@ines506 Retweet 22.06 River plate se impone en el Monumental con un contundente 6­0

@90minutos Tweet 22.08 En breve estaremos con una nueva edición de 90 Minutos de Fútbol por Fox

En la Figura 3.9 se ilustra la tabla de mapeo de identificadores y el Grafo

Social tras el procesamiento de las mismas, teniendo en cuenta que la cuenta @ines506 sigue a @deportes102.

Figura 3.9. Grafo Social y tabla de mapeo tras arribo de las interacciones 5 y 6.

También en dicha figura se puede observar que el ID 4534567988

corresponde a @ines506 y el ID 567567 a @90minutos.

A modo de resumen, se puede indicar que los nodos aislados representan a usuarios sobre los cuales sólo se ha detectado tweets aislados, sin ninguna otra interacción.Aquellos nodos de los que sólo salen aristas dirigidas hacia otros nodos, representan a usuarios sobre los cuales sólo se ha detectado retweets y replies realizados por los mismos. Contrariamente, aquellos nodos a los que sólo llegan aristas dirigidas desde otros nodos, representan a usuarios sobre los cuales sólo se ha detectado tweets realizados por los mismos e interacciones que los referencian. Por último, aquellos nodos de los que salen y llegan aristas dirigidas, puede indicar que se trata de un nodo intermedio, agregado por la búsqueda de la cadena de propagación de relaciones. O bien, puede indicar simplemente un usuario sobre el cual se ha detectado ambos tipos de interacciones,tweets(que no referencian otras interacciones), y retweets y/o replies (que sí referencian otras interacciones).

42

3.3.2. Registro de Propagaciones Mientras se lleva a cabo la incorporación del usuario al grafo se debe

registrar también la interacción en cuestión. Para esto se utiliza el Registro de Propagaciones o Log de Acciones. Cada entrada en dicho Log está compuesta de los campos: usuario, acción realizada y tiempo. Además se indica si la interacción posee usuario intermediario, ya que dicha información será utilizada en etapas posteriores. A continuación se muestran los pasos a seguir tras el arribo de cada interacción, de manera análoga a lo desarrollado anteriormente con el Grafo Social. Es importante aclarar que el ID de la acción también se normaliza por razones similares a las explicadas para el usuario. El Log siempre se mantiene ordenado en base al ID de las acciones y luego al tiempo. Interacción 1:

@deportes102 Tweet 16.38 Importante cruce por el grupo A de copa libertadores entre river y the strongest

Usuario identificado Acción

ScreenName:@deporte102 ID: 7853498053 ID:345679030240 Texto: Importante cruce por el grupo A de ID Normalizado: 1 copa libertadores entre river y the strongest

Tiempo: 16.38 (este valor en la herramienta se obtiene en milisegundos e incluye día, mes y año) Intermediario: No

Tras el arribo de la interacción en cuestión, se verifica que la acción no está ingresada en el sistema. Por ende, se crea una nueva entrada en el Log de Acciones y se le asigna un identificador normalizado para el mapeo local en la herramienta. En la Figura 3.10, se puede apreciar el estado final del Registro de Propagaciones tras el ingreso de la interacción 1.

Figura 3.10. Log de Acciones tras el arribo de la interacción 1.

Cabe destacar que como no hubo intermediario en la propagación de la

interacción, no se ubica ningún valor a la derecha del usuario en cuestión.

43

Interacción 2:

@deportes102 Tweet 21.54 River plate se impone en el Monumental con un contundente 6­0

Usuario identificado Acción

ScreenName:@deporte102 ID: 7853498068 ID:345679030240 Texto: River plate se impone en el ID Normalizado: 1 Monumental con un contundente 6­0

Tiempo 21.54 Intermediario No

Análogamente a lo ocurrido tras el arribo de la interacción 1, en el arribo de la presente interacción se verifica que la acción no está ingresada en el sistema. Por ende, se crea una nueva entrada en el Log de Acciones y se le asigna un identificador normalizado para el mapeo local en la herramienta. En la Figura 3.11, se puede apreciar el estado del Log de Acciones.

Figura 3.11. Log de Acciones tras el arribo de la interacción 2.

Interacción 3:

@laura301 Retweet 21.59 Boca juniors se mete en octavos de copa libertadores tras vencer a racing de visitante

Referencia Interacción:

@bocaoficial Tweet 21.49 Boca juniors se mete en octavos de copa libertadores tras vencer a racing de visitante

Usuarios identificados Acción ScreenName:@bocaoficial ScreenName:@laura301 ID: 7853498196 ID:914390 ID:45608594845 Texto: Boca juniors se ID Normalizado:2 ID Normalizado:3 mete en octavos de

copa libertadores tras vencer a racing de visitante.

44

Tiempo 21.49 Tiempo 21.59 Intermediario No Intermediario No

Tras el arribo de la interacción en cuestión, se verifica que la acción

referenciada no está ingresada en el sistema. Por ende se procede a crear una nueva entrada en el Log de Acciones con la interacción original y se le asigna un identificador normalizado para el mapeo local en la herramienta. Luego se procede a añadir otra entrada en el Log, esta vez con la interacción en cuestión. En la Figura 3.12, se puede apreciar el estado del Registro de Propagaciones tras el ingreso de la interacción referenciada y la que interacción que arriba al sistema.

Figura 3.12. Log de Acciones tras el arribo de la interacción 3.

Cabe destacar que como se mencionó previamente en esta sección, el Log

se mantiene ordenado primero por ID de Acción y luego por tiempo. Interacción 4:

@ezequiel403 Retweet 22.02 Boca juniors se mete en octavos de copa libertadores tras vencer a racing de visitante

Referencia Interacción:

@bocaoficial Tweet 21.49 Boca juniors se mete en octavos de copa libertadores tras vencer a racing de visitante

Usuarios identificados ScreenName:@bocaoficial ScreenName:@ezequiel403 ID:914390 ID:43758475 ID Normalizado:2 ID Normalizado:4 Tiempo 21.49 Tiempo 22.02

45

ScreenName:@laura301 ID:45608594845 ID Normalizado:3 Tiempo 21.59 Acción ID: 7853498196 Texto: Boca juniors se mete en octavos de copa libertadores tras vencer a racing de visitante. Intermediario No Intermediario No Intermediario Si (@laura301)

Tras el arribo de la interacción 4, se verifica que la acción referenciada está ingresada en el sistema. Además tras el análisis de propagación de relaciones realizado en la generación del Grafo Social se determina que existe un intermediario. Por ende, se procede a verificar que la acción del intermediario esté ingresada en el sistema. Tras ello, se identifica que el usuario @laura301 ya tiene una entrada en el Log con la realización de la acción. En consecuencia, la única entrada que debe ser añadida es la de dicha interacción. Entonces, se crea una nueva entrada en el Log de Acciones y se la inserta de manera ordenada. En la Figura 3.13, se puede apreciar el estado del Registro de Propagaciones tras el ingreso de la interacción que arriba al sistema.

Figura 3.13. Log de Acciones tras el arribo de la interacción 4.

Nótese que se indica entre paréntesis a la derecha del ID Normalizado del

usuario, el nodo intermedio por el que se realizó la acción. Interacción 5:

@ines506 Retweet 22.06 River plate se impone en el Monumental con un contundente 6­0

46

Referencia Interacción:

@deportes102 Tweet 21.54 River plate se impone en el Monumental con un contundente 6­0

Usuarios identificados Acción ScreenName:@deportes102 ScreenName:@ines506 ID:7853498068 ID:345679030240 ID:4534567988 Texto: River plate se ID Normalizado:1 ID Normalizado:5 impone en el

Monumental con un contundente 6­0

Tiempo 21.54 Tiempo 22.06 Intermediario No Intermediario No

Tras el arribo de la interacción 5, se verifica que la acción referenciada está ingresada en el sistema. En consecuencia, se procede a crear e insertar de manera ordenada una entrada al Log con la interacción que arribó al sistema. En la Figura 3.14, se puede apreciar el estado del Registro de Propagaciones tras el ingreso de dicha interacción.

Figura 3.14. Log de Acciones tras el arribo de la interacción 5.

La última interacción (número 6) se agrega de manera directa al igual que la

primera.

Interacción 6:

@90minutos Tweet 22.08 En breve estaremos con una nueva edición de 90 Minutos de Fútbol por Fox

47

En la Figura 3.15, se puede apreciar el estado del Log de Acciones tras la inserción de la entrada correspondiente a la interacción 6.

Figura 3.15. Log de Acciones tras el arribo de la interacción 6.

De esta manera, se da por finalizada la explicación de la segunda etapa del

enfoque propuesto. Además en las secciones antes descritas se ejemplifica paso paso la generación de las estructuras. En la Figura 3.16, se ilustra a modo de resumen el estado del Log de Acciones y del Grafo Social, tras el hilo conductor del ejemplo.

Figura 3.16. Log de Acciones y Grafo Social tras el arribo de

las interacciones del hilo conductor.

48

3.4. Obtención del Conjunto de Semillas

En esta sección se explica la etapa de Obtención del Conjunto de Semillas del enfoque propuesto. En esta etapa se utiliza la herramienta Influence Models [4]. En las siguientes subsecciones se enuncia lo referido a la construcción de las entradas que exige el Influence Models y a la ejecución misma de la herramienta. Además se continúa con el ejemplo propuesto como hilo conductor.

3.4.1. Generación de Entradas del Influence Models

Para obtener el conjunto de usuarios influyentes de la red, de manera que si se convenciera a los nodos indicados de realizar una acción, la propagación de la influencia sea maximizada, se analizaron diversos modelos y algoritmos que fueron desarrollados en el Capítulo 2. El modelo a utilizar en el presente enfoque será el Credit Distribution Model propuesto por Goyal, Bonchi y Lakshmanan en [4] junto su algoritmo de aproximación. Este modelo, mediante la utilización de datos históricos, calcula directamente la propagación de influencia y obtiene mejores resultados en cuanto a la precisión de semillas predichas, la calidad de la selección de las mismas, el tiempo de ejecución y la escalabilidad que modelos como el IC, el LT y el TR. Además, una de las características más importantes a destacar es que el CD tiene en cuenta los tiempos en que las acciones se propagan y los promedios de los mismos influyen al momento de la asignación de créditos por influencia. Este factor es fundamental para poder cumplir con el objetivo del trabajo.

El modelo CD y el algoritmo sobre el mismo que proponen en [4], se materializa en una herramienta denominada Influence Models, la cual fue desarrollada por Amit Goyal. Esta herramienta permite cinco maneras de funcionamiento:

­ Selección de Semillas para la Maximización de la Influencia bajo el CD. ­ Determinar la Verdadera Propagación de Influencia de un conjunto de semillas bajo el CD. ­ Experimentos de Predicción de Propagación. ­ Maximización de Influencia bajo los modelos LT e IC. ­ Generación de Archivos de Entrada.

49

El modo de trabajo se configura previamente a la ejecución de la herramienta y dependiendo del funcionamiento que se desee utilizar las entradas necesarias pueden variar. En el caso particular del presente enfoque, la función de interés es la primera del listado anterior. Para ello, se deben indicar algunos valores de configuración como la cantidad de semillas, el umbral de truncamiento y la cantidad de interacciones a considerar. Sin embargo, los que resultan de interés para el presente capítulo son los relacionados con el Grafo Social y el Log de Acciones.

Una de las entradas que se exige es denominada graphFile y la misma debe contener tuplas de 5 (cinco) columnas. Cada fila representa un enlace entre dos usuarios, los cuales son incluidos indicando su número de ID. Por otro lado, debe indicarse el tiempo promedio que toman en propagarse las acciones del primer usuario al segundo y viceversa. Dichos campos son fundamentales y se obtienen directamente desde la herramienta propuesta en este enfoque. Cabe destacar que el modo de Generación de Archivos que ofrece el Influence Models permite, tras la realización de dos scansdel Grafo Social y el Log de Acciones, generar el requerido graphFile. Sin embargo, para evitar la ejecución de ambos scans, se opta por generar dicha entrada directamente desde la herramienta propuesta TSeedS. De esta forma, sólo se debe ejecutar la selección de semillas.

Por otro lado, se debe proveer una entrada que contiene la información sobre las trazas de propagación, la cual se denomina actionsFile. La misma es la representación directa del Log de Acciones tal cual se mantiene la estructura dentro de la herramienta. En la misma se indica el ID del usuario, el ID de la acción realizada y el tiempo en que la realizó. Estando siempre ordenado por ID de acción primero y luego por tiempo como se explicó en la sección anterior.

Finalmente, la otra entrada que se debe generar contiene la información sobre la influenciabilidad del usuario y es llamadauserInflFile. Esta entrada también es obtenida de manera directa por la información contenida en la herramienta propuesta. Se debe indicar el ID del usuario, junto con el número de acciones que el usuario realizó del conjunto de entrenamiento (interacciones que pasaron el filtro) y el número de ellas en las cuales no fue el iniciador. En base a estos datos se determina un cuarto campo que es la influenciabilidad del usuario, la cual se determina en base a la división de las acciones realizadas que no inició sobre el total de acciones concretadas.

Retomando el ejemplo seleccionado como hilo conductor, a continuación se ilustra el estado final de las entradas exigidas por el Influence Models, utilizando el Log de Acciones y el Grafo Social provenientes de la sección anterior (ver Figura 3.17).

50

Figura 3.17. Resumen del Log de Acciones y Grafo Social tras la finalización de la segunda etapa.

Entradas Requeridas por el Influence Models

Como se expresó anteriormente, en las Figuras 3.18, 3.19 y 3.20 se puede

apreciar el estado de las distintas entradas exigidas por el Influence Models siguiendo el hilo conductor proveniente de la segunda etapa del enfoque propuesto.

Figura 3.18.Entrada GraphFile generada tras ejemplo conductor.

En la Figura 3.18 se puede apreciar que cada tupla contiene los campos

User1ID y User2ID, y permite representar los vínculos establecidos en el Grafo Social. Los otros dos campos que contiene la tupla permiten indicar el promedio temporal con el que se propagaron las acciones de un usuario hacia otro y viceversa. En el caso del ejemplo, es sencillo obtener este valor promedio ya que sólo una acción propagó entre cada par de usuarios. Por ende, simplemente se indican los minutos de diferencia entre la realización de la acción por el usuario de la izquierda respecto del tiempo en que la realizó el usuario de la derecha. De esta forma, se evidencia que la acción realizada por la cuenta @bocaoficial se propagó 10 minutos después a la cuenta @laura301. Dicha acción propagada por @laura301 se propaga desde la misma hacia @ezequel403 3 minutos después. Y por último la

51

acción realizada por la cuenta @deportes102 se propagó 12 minutos después a @ines506.

Figura 3.19.Entrada ActionsFile generada tras ejemplo conductor.

En la Figura 3.19, se puede apreciar la representación del Log de Acciones

en la entrada ActionsFile. Como se vio previamente en esta sección los campos a indicar son equivalentes a los almacenados en cada entrada del Log. La diferencia radica en que en el caso de una entrada con nodo intermedio, dicha información no es precisada en la entrada del Influence Models.

Figura 3.20.Entrada UserInflFile generada tras ejemplo conductor.

En la Figura 3.20, se observa el listado de usuarios que se encuentran en el

Grafo Social, junto con información adicional respecto de las acciones llevada a cabo. Allí se indica que @deportes102 ha realizado dos acciones y ha sido el iniciador en ambas. De manera similar se indica que @bocaoficial y @90Minutos han realizado una acción y han sido el iniciador de la misma. Por último, se indica que @laura301, @ezequiel403 y @ines506 han realizado una acción pero no son ellos quien la han iniciado. En base a esto último ocurre que el valor de influenciabilidad asignado en el cuarto campo de la tupla para dichos usuarios equivale a uno.

52

3.4.2. Ejecución del Influence Models Para un mejor entendimiento de la herramienta provista por Goyal, se

procede a la explicación del algoritmo propuesto en [4], el cual se introdujo de manera resumida en el Capítulo 2, tras la descripción del Credit Distribution Model. De forma detallada, a continuación se desarrolla un paso a paso sobre el algoritmo con la utilización de pseudocódigos para una mejor comprensión del mismo.

Inicialmente, se escanea el log de acciones L y se mantiene toda la información necesaria para seleccionar las “k” semillas. En particular, se almacena el crédito total asignado a cada nodo “v” por influenciar a cualquier otro nodo “u” para todas las acciones “a”, en una estructura denominada UC (del inglés, User Credits). Cada entrada en esta estructura es de la forma UC[v][u][a] y corresponde a Γv,uV­S(a) que, como se enunció con anterioridad, es el crédito total asignado a “v” por activar “u” en el grafo inducido por V­S donde S es el conjunto de semillas actual. Por otro lado, se mantiene una estructura SC (del inglés, Set Credits) donde cada entrada tiene la estructura SC[x][a] que refiere al crédito total asignado al conjunto de semillas actual por un nodo “x” para la acción “a”. Esto también es denotado como ΓS,x(a). Cabe destacar, que en la primera iteración esta estructura no se utiliza ya que S es vacío.

El pseudocódigo mostrado en la Figura 3.21 describe la primera etapa del método que escanea L, donde L se mantiene ordenado (primero por acción y luego por tiempo). Este se encarga de procesar una acción tras otra en orden cronológico y mantienen una lista de los usuarios que realizaron la acción actual bajo la estructura current_table (tabla actual). Además Au como se indicó en la tabla de notaciones en la sección 2.3.5, es el número de acciones realizadas por el usuario “u” en L. En particular, Parents(u) se utiliza para representar la lista de padres de cada nodo “u” respecto de la acción actual, que es Nin(u,a). Cabe destacar que se utiliza el umbral de truncamiento λ con el objetivo de reducir requerimientos de memoria y descartar los créditos que se encuentren bajo el mismo.

53

Figura 3.21. Pseudocódigo que describe la primera etapa del

método que escanea el Log de Acciones. Una vez que la primera fase se completa, se utiliza el algoritmo greedy

estándar pero con la optimización CELF para seleccionar las semillas. El algoritmo mantiene una cola Q donde una entrada para un usuario “x” es almacenada de la forma <x, mg, it>, donde “mg” representa la ganancia marginal del usuario “x” respecto al conjunto de semillas de la iteración “it”. Q siempre se encuentra ordenada en orden decreciente por ganancia marginal (mg). A continuación se ilustra un pseudocódigo en la Figura 3.22.

Figura 3.22. Pseudocódigo del algoritmo Greedy estándar con

la optimización CELF para seleccionar semillas.

54

Es importante analizar las funciones computeMG y update que se utilizan en el pseudocódigo provisto en la Figura 3.22. En el caso de la primera, se encarga de determinar la ganancia marginal de un nodo “x” respecto al conjunto de semillas actual S. Finalmente, siempre que un usuario “x” es añadido al conjunto de semillas, la subrutinaupdate es invocada, y se encarga de actualizar las estructuras UC y SC. Ambas funciones son ilustradas en los pseudocódigos de la Figura 3.23.

Figura 3.23. Pseudocódigos correspondientes a las funciones computeMG y

update usadas en el algoritmo Greedy con optimización de CELF. Una vez comprendido el algoritmo, y con los archivos de entrada ya

generados como se explicó en la subsección anterior se procede a ejecutar el Influence Models. Luego de su ejecución, genera como salida un conjunto de semillas que maximizan la influencia en el Grafo Social, estableciendo el valor de ganancia marginal de cada usuario perteneciente a dicho conjunto.

3.5. Interpretación de Resultados En esta etapa se describe la correcta interpretación de los resultados

obtenidos por el Influence Models. Manteniendo el ejemplo conductor proveniente de las etapas anteriores, a continuación se ilustra (ver Figura 3.24) la salida del Influence Models configurado para que el conjunto de semillas contenga 3 usuarios.

55

Figura 3.24. Salida del Influence Models tras ejecutarlo

en modo de Selección de Semillas. En la primera columna se indica el ID del usuario, en la segunda la ganancia

acumulada del conjunto propuesto y en la tercera la ganancia marginal aportada por el usuario en cuestión. Al ser breve el ejemplo, puede previamente de manera intuitiva predecirse el mismo resultado que se obtiene de la ejecución del Influence Models. Es decir, que la cuenta @bocaoficial (ID=2) con un tweet realizado y dos retweets sobre el mismo iba a ser influyente. De manera similar se hubiera incluido a la cuenta @deportes102 (ID=1) que con dos tweets realizados y un retweet sobre uno de ellos podría ser previamente considerado dentro de los influyentes. Por último, se indica la cuenta @90minutos (ID=6) que como puede verse la ganancia marginal que aporta al grafo equivale a 1. Esto ocurre ya que no tuvo interacciones con otros nodos y entonces la cantidad de créditos que aporta es su total propio, es decir, 1. Cabe destacar la no aparición en el conjunto de la cuenta @laura301 (ID=3) que realizó un retweet y fue retweeteada en una oportunidad.

Es trascendental comprender que la ganancia marginal se modifica a medida que se selecciona un usuario para ingresarlo al conjunto de semillas. Es decir, se genera un ranking interno de las ganancias cada vez que uno de los usuarios es seleccionado. Es por ello, que en múltiples casos usuarios relacionados por las interacciones no siempre son incluidos de manera conjunta. Esto sucede ya que incluir a uno de ellos, puede derivar en que el aporte o nueva ganancia marginal del otro usuario al conjunto restante sea menor a la calculada en un principio.

3.6. Visualización de los Resultados

Hasta la etapa anterior se resume el proceso que ocurre cada cierta ventana de tiempo (normalmente un minuto). Sin embargo, para esta quinta etapa la visualización de los resultados en forma de gráficos sobre los usuarios que fueron o son semillas cobran mayor sentido cuanto mayor tiempo transcurre. Esto se debe a que así permite analizar la dinámica de la influencia del usuario. De todas maneras para indicar un cierre sobre el ejemplo conductor, en la Figura 3.25 se ilustra el gráfico que se generaría para el usuario @bocaoficial con las interacciones procesadas en las etapas anteriores.

56

Figura 3.25. Gráfico de evolución de influencia del usuario

@bocaoficial siguiendo ejemplo conductor. Nótese que la posición en el Seed Set está invertida para analizar

visualmente de manera sencilla las crecidas o los descensos posibles de la influenciabilidad de los usuarios. Es decir, dicha cuenta era la primera en el Seed Set y, por ello, en el gráfico puede apreciarse que se ubica en la posición 3 (lo que permite visualizar un valor de influencia alto).

Al mostrar resultados de una sola ejecución del Influence Models (a las 22:50:00hs), el gráfico no aporta información de interés. Es por ello, que a continuación se muestran diversos casos posibles con el paso del tiempo, con la cuenta @deportes102. El primer caso planteado es, en el transcurso horario de las 10.00hs y las 19.00hs el usuario @deportes102 fue incluido en el Seed Set como lo indica la Tabla 3.6.

Tabla 3.6. Inclusiones en el Seed Set de @deportes102 entre las 10hs y las 19hs.

En base a la misma, el gráfico que se generaría sería el que se ilustra en la

Figura 3.26.

Figura 3.26. Gráfico de evolución de influencia del usuario @deportes102 entre las 10hs y las 19hs.

57

Si en cambio la ventana temporal analizada, hubiese sido desde las 22.00hs hasta las 22.50hs, la tabla de Inclusiones en el Seed Set sería la ilustrada en la Tabla 3.7.

Tabla 3.7. Inclusiones en el Seed Set de @deportes102

entre las 22.00hs y las 22.50hs.

El gráfico que se obtendría utilizando los datos de la Tabla 3.7, sería el ilustrado en la Figura 3.27.

Figura 3.27. Gráfico de evolución de influencia del usuario

@deportes102 entre las 22.00hs y las 22.50hs.

58

En base a la observación de gráficos como los mostrados previamente, se pueden estudiar diversos aspectos de la influencia de los usuarios. Entre otros, puede analizarse la continuidad en el tiempo de su aparición en el Seed Set o determinar las brechas horarias o días en los que logra los picos más altos. Además al examinar sus acciones en dichos momentos también pueden visualizarse ciertos campos donde su influencia es mayor. Es decir, si bien la búsqueda es categorizada y, por ejemplo, todas las acciones tratarán o contendrán la palabra “fútbol”, dentro del mismo puede distinguirse entre opiniones, noticias, resultados, entre otros. También permite en cierto punto determinar cuáles son las temáticas dentro de la categoría en cuestión, sobre la que más información se propaga.

De esta forma, atravesando las cinco etapas descritas en las secciones anteriores y en la presente, se busca cumplir con el objetivo del enfoque. Como se ha enunciado con anterioridad, dicho objetivo se centra principalmente en resolver el problema de la maximización de la influencia, dada una temática y una red social, y además busca poder analizar la dinámica o evolución de la influencia de los usuarios en el tiempo.

59

4. Implementación de TSeedS

En este capítulo se describe la implementación de la herramienta TSeedS desde un punto de vista técnico, analizando su diseño y desarrollo. En la primera sección de este capítulo se muestra un diagrama UML (del inglés, Unified Modeling Language) que representa la vista demódulos del sistema. Se eligió la utilización de dicha vista con el objetivo de presentar la funcionalidad del sistema mediante unidades estáticas que proveen conjuntos de servicios y responsabilidades. Además en las secciones siguientes se descomponen dichos módulos utilizando diagramas de clases. Estos permiten realizar un análisis de mayor profundidad sobre la implementación y el diseño.

Por otra parte, se explica la utilización de la herramienta Influence Models [4]. La misma se usa para obtener el conjunto de semillas.

En la última sección del presente capítulo se muestran capturas de la visualización de la aplicación bajo las distintas ventanas que pueden encontrarse. Entre ellas, se muestran la ventana principal, la contenedora de información de las semillas y la contenedora del Grafo Social.

Por otro lado, cabe destacar que el desarrollo de TSeedS se realizó en Java, utilizando el entorno de desarrollo Eclipse. El motivo de la utilización de Java corresponde a la familiarización y experiencia con dicha tecnología. También es importante mencionar que existe una gran cantidad de bibliotecas que facilitan el trabajo básico necesario, permitiendo enfocarse en el objetivo real del proyecto.

4.1. Diseño del Sistema En la Figura 4.1 se ilustra un diagrama de módulos UML, que indica cómo se

organiza la herramienta TSeedS en diferentes unidades de implementación. El módulo Aplicación es el más importante ya que es el encargado de activar las distintas etapas del enfoque. Primero, se encarga de cargar las configuraciones iniciales del sistema. Luego inicia la secuencia de las etapas propuestas en el enfoque.

La primera etapa que corresponde a la Obtención de la Información, en el diagrama se mapea al módulo de Monitoreo de Redes Sociales. Este además utiliza el módulo Filtros para realizar los distintos filtrados sobre las interacciones. También usa la Interfaz de Twitter con el fin de obtener información adicional de la red.

La etapa de Generación de Estructuras, se mapea al módulo de Procesamiento de Información. El cual usa los módulos del Grafo Social y el Registro de Propagaciones. También utiliza la Interfaz de Twitter para lo que corresponde a la búsqueda de caminos críticos entre usuarios. Lógicamente se

60

relaciona con el stream provisto por el Monitoreo de Redes Sociales ya que de allí obtiene las interacciones para generar las estructuras.

La etapa 3 se mapea con el Volcado de Información y el módulo de Ejecución del Influence Models. El Volcado se relaciona con el Registro de Propagaciones y el Grafo Social ya que de ellos proviene la información que se debe volcar.

La etapa de Interpretación de Resultados se mapea con el módulo del mismo nombre. Dicho módulo se relaciona con el Histórico de Semillas que es mapeado con la última etapa del enfoque que corresponde a la Visualización de los Resultados.

Además el Grafo Social, el Registro de Propagaciones y el Histórico de Semillas se relacionan con el módulo Usuario ya que este contiene los servicios de interés de los usuarios del sistema. El Usuario al igual que el Registro de Propagaciones contienen y utilizan acciones. Es por ello, que en el diagrama se establece la relación de dichos módulos con el módulo Acción.

Figura 4.1. Diagrama de paquetes UML del sistema.

61

4.2. Monitoreo de Redes Sociales La red social utilizada en la implementación, como se presentó en el enfoque,

es Twitter. Para poder realizar el monitoreo de dicha red se creó la clase TwitterMonitor.java como se ilustra en el diagrama de clase de la Figura 4.2.

Figura 4.2. Diagrama de clase de la etapa

de Monitoreo de Redes Sociales. En el método startListen() se da inicio a la escucha de interacciones

provenientes de Twitter. Para llevar a cabo dicho streaming sobre la red social se utilizan clases de la librería Twitter4J . La clase principal que provee el servicio es 14

denominada TwitterStream y a través de una subscripción permite escuchar las interacciones de Twitter. En este método además se aplican los distintos filtros de idioma, tiempo y categoría que deben cumplirse para tomar como válida una interacción. Dichos filtros se analizan en la sección siguiente (4.3). Cada interacción válida que es escuchada se agrega al vector de interactions que muestra la Figura 4.2. Es importante distinguir que las interacciones son de tipo Status (que también es una clase provista por la librería Twitter4J) pero esto se analiza en mayor profundidad en la sección 4.4.

Para poder realizar el chequeo temporal de las interacciones denominadas replies se usa el módulo Interfaz de Twitter ya que este provee el servicio de búsqueda de información adicional.

Por último, cabe destacar que el hilo t_date permite actualizar cada cierta ventana de tiempo el filtro temporal que debe aplicarse sobre las interacciones en cuestión.

14 Twitter4J: Librería Java no oficial de la Twitter API. Para más información: http://twitter4j.org/en/index.html

62

4.3. Filtros En esta sección, se detallan los distintos filtros que pueden aplicarse sobre

las interacciones escuchadas en la etapa de monitoreo. El filtrado de categorías se realiza de manera directa sobre el streaming planteado en la sección anterior. Para ello, se utiliza la clase FilterQuery de la librería Twitter4J, la cual permite añadir palabras o keywords a una lista y luego filtrar por la misma. Es decir, las interacciones pasan este filtro sólo si contienen al menos una de las palabras de dicha lista.

El filtro temporal como se enunció en la sección anterior, se aplica dentro de la clase TwitterMonitor.java y se actualiza cada cierta ventana de tiempo.

En la Figura 4.3 se ilustra una jerarquía de filtros que permite la fácil incorporación de nuevos filtros. El único implementado es el filtro de idioma o lenguaje que . Además se permiten las operaciones AND y OR entre distintos filtros, habilitando la concatenación de diversos tipos de filtrado.

Figura 4.3. Diagrama de clases de filtros complementarios

al filtro temporal y al de categoría.

4.4. Interacción

La implementación de este módulo se materializa en la clase Status de la librería Twitter4J. En la Figura 4.4 pueden visualizarse los métodos utilizados de dicha clase.

63

Figura 4.4. Lista de métodos utilizados de la clase Status de la librería Twitter4j.

Los distintos métodos permiten obtener una mayor cantidad de información

acerca de la interacción en cuestión. Para el monitoreo de redes sociales, su utilización refiere a datos como el idioma, el tiempo de creación de la interacción y su contenido textual. En otras palabras, la información que provee esta clase permite comprobar los filtros a aplicar sobre la interacción.

Además es utilizada para la obtención de identificadores, tanto de usuarios relacionados con la interacción, como de la interacción en sí misma. Además, al igual que en la etapa del monitoreo de redes sociales, permite obtener información sobre tiempos de creación de la acción original y sus interacciones, y sus respectivos contenidos.

4.5. Interfaz de Twitter Este módulo hace referencia a la interacción con la red social Twitter y la

posibilidad de realizar consultas sobre usuarios e interacciones. Es utilizada en la etapa de monitoreo y en la de procesamiento con el objetivo de completar la información obtenida. En el caso del monitoreo se le debe consultar a Twitter por el tiempo original de la interacciónreply, cuya información no está incluida dentro de la interacción escuchada.

En el caso del procesamiento de información, es además utilizada para solicitar datos sobre las relaciones entre usuarios. Es fundamental su uso para el establecimiento de enlaces entre usuarios de manera directa o a través de nodos intermedios. En particular las solicitudes que se realizan sonshowStatus(id­status) y showFriendship(id­user1,id­user2). La primera permite recuperar una interacción indicando su valor de identificador (id­status). La segunda permite determinar el tipo de relación existente entre dos usuarios.

Sin embargo, en la versión gratuita de Twitter, la cantidad de solicitudes que se pueden realizar por unidad de tiempo son limitadas. Es por ello, que con el caudal de consultas que el sistema realiza y las limitaciones propias que establece

64

la Twitter API, se derivó en la creación de una pileta de instancias de Twitter. Esta pileta o pool se diseñó entonces con el objetivo de poder abastecer una mayor cantidad de solicitudes. Twitter a través de cuatro valores identificatorios (credenciales) permite registrar una instancia. Por ende, lo que se hizo fue registrar distintas credenciales en Twitter con el objetivo de permitir la creación de múltiples instancias. En la Figura 4.5, se puede visualizar que en la claseTwitterPool.java se implementa dicho pool. Cabe destacar que sólo se indican tres credenciales registradas por un tema de prolijidad en el diagrama, sin embargo, se utilizan más de quince.

Para saber si una instancia puede o no continuar recibiendo solicitudes se suscribe un CustomRateLimitStatusListener que informa al pool sobre el estado de de la misma. Este listener implementa la interfaz RateLimitStatusListener contenida en la librería Twitter4j, cuyos métodos de interés son onRateLimitStatus y onRateLimitReached. A través de dichos métodos, el listener se comunica con el pool para indicar si una instancia de Twitter aún responde solicitudes o si alcanzó su límite y debe esperarse para volver a utilizarla. Por su parte el pool contiene una tabla de hash que contiene las distintas instancias y un valor lógico por cada una de ellas, que indica si la instancia se encuentra disponible o no.

Figura 4.5. Diagrama de clases del sistema de

administración de instancias de Twitter.

65

4.6. Procesamiento de Información

El procesamiento de la información se encuentra relacionado con la segunda etapa del enfoque propuesto, la Generación de Estructuras. Sin embargo, cabe destacar que en esta este módulo también se completa información de la interacción escuchada, por ende, abarca una parte de la primera etapa del enfoque, la Obtención de Información.

En el caso de la etapa de Obtención de Información, se solicita datos sobre las relaciones entre usuarios y las acciones originales tras los replies. Es además fundamental completar la información para el establecimiento correcto de los enlaces entre usuarios y los tiempos en que las interacciones son realizadas.

En el caso de la etapa de Generación de Estructuras, este módulo es el encargado de: indicar cuándo y con qué datos debe agregarse un usuario al Grafo Social; y cuándo y con qué datos debe agregarse una acción al Registro de Propagaciones.

Para establecer el vínculo entre los distintos usuarios se diseñó una solución que busca mejorar el concepto de enlace directo. Es decir, bajo el enfoque del Credit Distribution Model explicado con anterioridad en el presente trabajo, resulta interesante distinguir cuando los usuarios re­publican o hacenretweetde un usuario con el que no están relacionados de manera directa. En otras palabras, cuando un usuario realiza un retweet de una publicación de una persona que no sigue.

Motivados por esto, bajo el método lookForRetweetsChain implementado en la clase InfoProcessor.java (ilustrada en la Figura 4.6), se intenta encontrar el/los usuario/s intermedio/s entre el usuario que realizó originalmente eltweet y aquel que sin seguirlo hizo un retweet del mismo. Para lograrlo, se solicita a Twitter la lista de retweets existentes sobre eltweet en cuestión y se busca en ella un usuario que sea seguido por el usuario que realizó elretweet. En base a ello, de manera recursiva se establecen los enlaces entre nodos de manera que el enlace directo sea lo más real posible. Sin embargo, puede que un usuario haya accedido a una cuenta que no sigue y realizado el retweet sin intermediarios. De esta manera o en caso de no encontrar un usuario seguido en la lista de retweets el enlace se establece directo.

En la Figura 4.6, se ilustra un diagrama de la clase en cuestión. Además cabe destacar que se relaciona con el módulo de Monitoreo de Redes Sociales visto en la sección 4.2, al cual le solicita (de a una) las interacciones a procesar.

La clase InfoProcessor.java extiende de la claseThread y en su métodorun() realiza la solicitud de interacciones antes mencionada.

66

Figura 4.6. Diagrama de clase del procesamiento de información.

4.7. Grafo Social

La estructura Grafo Social está contenida en la clase SocialGraph.java y se compone de aristas (vínculos) y nodos (usuarios). Dicha clase implementa los métodos necesarios para la agregación de aristas y nodos; para la normalización de identificadores de usuarios; y para la búsqueda de usuarios en base a distintos criterios (nombre de pantalla, identificador, identificador normalizado). Está implementada usando el patrón Singleton de manera que sólo existe una instancia de esta estructura en toda la herramienta. Esto fue necesario, ya que la misma es utilizada desde diversas clases.

Por otro lado, para el manejo de la visualización gráfica del Grafo Social se implementó la clase GraphVisualization.java. Esta permite ver los nodos de manera distintiva (diferente color) entre los que realizaron una acción original (tweet), o una interacción (retweet ó reply), o fueron intermediarios en una interacción, o los que pertenecen al último conjunto de semillas seleccionado. Dicha visualización se actualiza de manera automática a medida que surgen nuevos nodos o enlaces en el Grafo Social. Es importante destacar que los usuarios que sólo realizaron tweets pero no se relacionan con ninguna interacción, no son tenidos en cuenta a la hora de mostrar el Grafo. Esto se debe a que, estéticamente, una superpoblación de nodos solitarios (sin vincular) no permite apreciar las diversas relaciones existentes entre nodos conectados.

Para llevar a cabo la funcionalidad antes mencionada, se utilizan clases de la librería JUNG (del inglés, Java Universal Network Graph). La clase de mayor trascendencia es la que contiene el grafo y se denomina DirectedSparseGraph.

Para la utilización de colores distintivos se implementó la clase VertexColorTransformer.java que permite determinar el color de un nodo en base a un criterio.

67

En la Figura 4.7, se ilustra un diagrama de clase del módulo previamente explicado.

Figura 4.7. Diagrama de clase de la unidad de implementación del Grafo Social.

4.8. Usuario En la Figura 4.8 se ilustra la clase User.java la cual representa el módulo de

esta sección. Por razones de prolijidad los métodosgettersde los atributosnro_xno fueron incluidos en el diagrama.

68

Figura 4.8. Diagrama de clase del Usuario.

Como se puede apreciar, el usuario almacena las distintas acciones que ha

realizado, la cantidad de cada una de las interacciones que ha hecho, la cantidad de interacciones en las que otros usuarios los han referenciado, la información sobre las veces que perteneció al conjunto de semillas, y campos específicos e identificatorios como su nombre de pantalla o sus números de ID (original y normalizado). Junto con estos atributos, esta clase provee los getters y métodos de agregación add para mantener actualizada la información del usuario.

Es importante destacar que clases como SeedInfo.java y Action.java son referenciadas por el usuario pero serán analizadas en las unidades de implementación correspondientes.

69

4.9. Registro de Propagaciones y Acción

La estructura Registro de Propagaciones se genera y actualiza en la segunda etapa del enfoque propuesto al igual que el Grafo Social. Y análogamente a este último son utilizadas en etapas posteriores por diversos módulos. En la Figura 4.9 se ilustra el diagrama de clase de la unidad Registro de Propagaciones.

70

Figura 4.9. Diagrama de clases de la unidad Registro de Propagaciones.

Cabe destacar que por razones de prolijidad no se incluyen los getters y

setters de las clases Action.java y LogEntry.java. Como se puede apreciar en el diagrama de la Figura 4.9, el Log de Acciones

(o Registro de Propagaciones) contiene entradas y cada una de ellas contiene una acción y un tiempo. Dichas entradas se implementan en la clase LogEntry.java y además de lo mencionado anteriormente, permiten diferenciar cuándo una interacción tuvo un usuario intermedio y cuándo se realizó de manera directa. Esta

71

información se utiliza luego para la Generación de Entradas del Influence Models, perteneciente a la etapa 3 del enfoque propuesto.

Respecto a la clase Action.java es un contenedor que indica, el identificador normalizado de una acción o interacción, el tipo (tweet, retweet, reply) y el texto que contiene. Cabe recordar que el usuario contiene un listado de las acciones realizadas. Esta clase es la que representa el módulo Acción visto en el diagrama de la sección 4.1.

Por último y siendo la clase más importante, se ilustra ActionLog.java. Esta clase contiene la estructura del denominado Registro de Propagaciones y permite la agregación de nuevas interacciones. Es importante destacar que el registro de interacciones se mantiene de manera ordenada primero por ID de acción y luego por tiempo de realización. Esto es así para facilitar la creación de las entradas del Influence Models, que será analizada en la sección siguiente.

4.10. Volcado de Información

Este módulo pertenece a la primera parte de la etapa tres del enfoque propuesto, la Obtención del Conjunto de Semillas. Para llevar a cabo esta última se utiliza la herramienta denominada Influence Models [4]. Esta herramienta como se explicó en el capítulo anterior permite cinco maneras de funcionamiento:

­ Selección de Semillas para la Maximización de la Influencia bajo el CD. ­ Determinar la Verdadera Propagación de Influencia de un conjunto de semillas bajo el CD. ­ Experimentos de Predicción de Propagación. ­ Maximización de Influencia bajo los modelos LT e IC. ­ Generación de Archivos de Entrada. El modo de trabajo a elegir se debe indicar en el archivo de configuración de

la herramienta, bajo el parámetro phase. Cada uno de los modos anteriores se identifica con un número entero y dependiendo del funcionamiento que se desee utilizar el resto de los parámetros que son necesitados puede variar. En el caso particular del enfoque propuesto, laphase a utilizar es la primera del listado anterior, identificada con el número 12 (doce). Para ello, se deben indicar ocho parámetros además del ya mencionado modo. A continuación son listados junto con una breve descripción de los mismos:

1. Phase: 12 ­ Selección de Semillas para la Maximización de la Influencia bajo el CD. 2. graphFile: ruta al archivo que contiene la información sobre el Grafo Social. Cada línea debe contener 5 (cinco) columnas, separadas por un espacio en blanco. Este archivo puede ser generado utilizando el quinto modo enunciado

72

en la lista (Generación de Archivos de Entrada). A continuación se enumeran las columnas y su contenido.

Columna 1: ID del usuario 1. Debe ser un entero positivo. Columna 2: ID del usuario 2. Debe ser un entero positivo. El

usuario 1 y el 2 son amigos. En esta etapa el grafo ya no es dirigido. En cambio, si se utilizara el modo de Generación de Archivos para producirlo, sí se debería establecer la dirección de la arista.

Columna 3: Tiempo promedio tomado en propagarse las acciones del usuario 1 hacia el usuario 2. La unidad temporal es segundos.

Columna 4: Tiempo promedio tomado en propagarse las acciones del usuario 2 hacia el usuario 1. La unidad temporal es segundos.

Columna 5: Tiempo en segundos, en que el usuario 1 y el usuario 2 se hacen amigos. Indicar 0 si el grafo es estático. Como dicha información no es provista por Twitter, se indica el valor cero en este campo para todas las filas.

3. actionsFile: ruta al archivo que contiene la información sobre las trazas de propagación. Cada línea debe contener 3 (tres) columnas, separadas por un espacio en blanco. Las mismas se enumeran a continuación

Columna 1: ID del usuario. Debe ser un entero positivo. Columna 2: ID de la acción. Debe ser un entero positivo. Columna 3: Tiempo en segundos en que el usuario realizó la

acción. 4. trainingActionsFile: ruta al archivo que contiene los IDs de las acciones que están en el conjunto de entrenamiento. En este caso, el conjunto son todas las interacciones que sobrepasan a los filtros. Cada línea debe contener una única columna con el ID de la acción. 5. userInflFile: ruta al archivo que contiene la información sobre la influenciabilidad del usuario. Cada línea debe contener 3 (tres) columnas, separadas por un espacio en blanco. Las mismas indican:

Columna 1: ID del usuario. Debe ser un entero positivo. Columna 2: Número de acciones que el usuario realizó del

conjunto de entrenamiento. Columna 3: Número de acciones que el usuario realizó del

conjunto de entrenamiento, en las cuales no fue el iniciador. Columna 4: Es la división de la columna 3 sobre la 2 e indica la

influenciabilidad del usuario. 6. outdir: ruta al directorio donde se creará el archivo de salida.

73

7. maxTuples: número máximo de tuplas en el log de acciones a ser consideradas. Se debe indicar el valor numérico 0 si se desean considerar todas. 8. truncation_threshold: Umbral de Truncamiento. Valores por debajo de este umbral son descartados del cómputo del crédito otorgado a nodos influyentes. En los experimentos de [38] se determina que el valor 0.001 obtiene muy buenos resultados, aunque este valor puede ser modificado. 9. budget: número de semillas que se desean determinar. Como se puede apreciar algunos parámetros son básicos de la configuración

como la cantidad de semillas, el umbral de truncamiento, la cantidad de interacciones a considerar, o el directorio donde crear el archivo de salida. Sin embargo, los que resultan de interés para destacar son los relacionados con el Grafo Social y el Log de Acciones. En la Figura 4.10 se ilustra la clase FilesBuilder.java, en la cual el método makeFiles() implementa la generación de los archivos necesarios. Estos incluyen graphFile, actionsFile, trainingActionsFile y userInflFile. Para el último archivo se utiliza la estructura del Grafo Social, mientras que para el primero de ellos, solo el Registro de Propagaciones. Para la generación del actionsFile se utilizan ambas estructuras.

Cabe destacar que se debe indicar un directorio en el cual guardar dichos archivos que luego debe coincidir con el directorio que selecciona las entradas para la ejecución del Influence Models (módulo que se analiza en la sección siguiente).

Figura 4.10. Diagrama de clase que genera

las entradas del Influence Models.

También puede apreciarse la existencia del método getOlderTime(), el cual se encarga de retornar el tiempo más antiguo registrado en el Log de Acciones. Este tiempo se utiliza para normalizar los valores de los demás tiempos. Es decir, el tiempo más antiguo se utiliza como valor 1, y en base a él se normalizan los demás. Esto es así, ya que la representación de los tiempos se encuentra en milisegundos desde el 1ro de Junio de 1970 y el Influence Models no permite valores extremadamente altos.

74

4.11. Ejecución del Influence Models

Una vez generados los archivos de entrada, se procede a la Ejecución del Influence Models. Lo que se hace en el método execute() de la clase ilustrada en la Figura 11, es invocar al Influence Models indicando que el archivo de configuración se llama “config_maxinf_CD.txt”. Como fueron enumerados en la sección anterior, nueve son los parámetros que deben indicarse en dicho archivo.

Es sumamente importante incluir el ejecutable del Influence Models y sus respectivas dll (del inglés, dynamic­link library) en el mismo directorio que el ejecutable de la herramienta TSeedS. Las tres dll necesarias son: cyggcc_s­1, cygstdc++­6, y cygwin1.

Figura 4.11. Diagrama de clase de la unidad

de Ejecución del Influence Models.

En la Figura 4.12, se ilustra un ejemplo del contenido del archivo de configuración config_maxinf_CD.txt. En este caso, bajo el directorio training se encuentran los archivos de entrada generados y bajo el directorio maxinf_CD se encontrará el archivo de salida del Influence Models. Laphase es 12 como se indicó anteriormente, el maxTuples equivale a cero con el objetivo de considerar todas las acciones y el umbral de truncamiento es 0.001 (valor tomado de [4]). Por último, el tamaño del conjunto de semillas deseado es 10.

Figura 4.12. Archivo de configuración de Ejecución del Influence Models.

75

4.12. Interpretación de Resultados

En base a la salida generada por el Influence Models se procede a la Interpretación de Resultados. Dicha salida se basa en filas donde la primera columna indica el ID del usuario, la segunda la ganancia acumulada del conjunto propuesto y la tercera la ganancia marginal aportada por el usuario en cuestión. La lectura del archivo de salida, con dichas filas y la interpretación de las mismas se implementa en la clase ResultsInterpreter.java ilustrada en la Figura 4.13.

Figura 4.13. Diagrama de clase de la

Interpretación de Resultados. Esta clase permite obtener los resultados en dos formatos distintos, como

texto o como un conjunto de celdas para una tabla. Por la actual visualización de la aplicación, el método que se utiliza es el que retorna las celdas, getResultsAsCells(). Lo que se hace es leer el archivo de salida línea por línea y tras ello, agregar dicha información a los usuarios seleccionados (presencia en el conjunto de semillas) y notificar a la visualización gráfica del Grafo Social cuáles son dichos usuarios. Además los usuarios se agregan al histórico de semillas, unidad que se analiza en la sección siguiente.

4.13. Histórico de Semillas

Como se vio en la sección 4.8, el usuario almacena información de las oportunidades en las que fue seleccionado en el conjunto de semillas. Dicha información está contenida en la clase SeedInfo.java ilustrada en la Figura 14. Los atributos que se guardan son la posición lograda en el conjunto de semillas o seed set, la ganancia marginal alcanzada y la fecha exacta de dicha ocurrencia. Además se implementan los getters y setters de los mismos.

76

Figura 4.14. Diagrama de clase de unidad contenedora de información de semilla.

Por otro lado, como se indicó en la sección anterior los usuarios se agregan a

un histórico de semillas. El administrador de dicho histórico como se ilustra en la Figura 4.15, es la claseHistoricManager.java. Este administrador mantiene una lista actualizada de los usuarios que pertenecen o pertenecieron al menos una vez al conjunto de semillas. Dicha lista es solicitada con regularidad por la ventana principal de la aplicación.

Figura 4.15. Diagrama de clase del administrador

del histórico de semillas.

La ventana principal no solo muestra la lista que provee dicho histórico sino que además permite la visualización personalizada de los integrantes de la misma. Al realizar un doble click sobre el usuario, se abre una ventana que muestra todo tipo de información del mismo. Por un lado, una tabla muestra las acciones e interacciones realizadas por el usuario junto con su identificador y fecha exacta de realización. Por otro lado, se muestra una tabla con los datos personales del usuario, como nombre e identificador, y también con datos estadísticos, como cantidad de tweets, retweets y replies realizados, o cantidad de veces que ha recibido un reply o un retweet, o cantidad de veces que estuvo presente en el

77

conjunto de semillas. Por último, también se provee la visualización de un gráfico que muestra las distintas posiciones que el usuario obtuvo en el Seed Set en función del tiempo. Esto permite el análisis de la dinámica de la influencia de los usuarios y la ampliación de los ámbitos de comparación entre distintas semillas. La clase que implementa la funcionalidad antes descrita es ilustrada en la Figura 4.16 y se denomina SeedProfile.java.

Figura 4.16. Diagrama de clase de la visual de la información de un usuario semilla.

Cabe destacar que para la realización de los gráficos se utiliza la librería

JFreeChart. En particular, se crea un dataset del tipoTimeSeries con la información de las distintas oportunidades en las que el usuario fue semilla. Luego se crea el gráfico de tipo TimeSeriesChart indicando el dataset en cuestión y los rangos y unidades mínimas para el dominio y el eje de ordenadas. La unidad mínima en el eje de abscisas es de un minuto, es por ello que transcurridas algunas horas puede resultar ilegible ver dichos valores. De todas formas, la aplicación permite realizar distintos tipos de zoom sobre el gráfico. El rango que se establece para este eje es desde la fecha de la primera acción o interacción detectada por el sistema para este usuario hasta la fecha en la que se abrió la ventana de dicho usuario.

En el caso del eje de ordenadas, los valores son enteros y se encuentran entre 0 y k, donde k representa el número de semillas presentes en elSeed Set. El valor cero indica la no pertenencia al conjunto de semillas. La escala de 1 akindica la posición en el Seed Set invertida. Es decir, si el usuario se encontraba en la décima posición en el conjunto dado k=10, en el gráfico aparecerá con el valor 1 y viceversa. Esto se decidió así con el objetivo de visualizar fácilmente el crecimiento o decrecimiento de la influenciabilidad del usuario en el tiempo.

4.14. Visualización de la Aplicación

La visualización de TSeeds se compone de tres ventanas distintas. Por un lado la ventana principal, que mantiene actualizada una lista con el histórico de

78

semillas del sistema, muestra otra lista con el conjunto de semillas actual (fecha exacta indicada en la parte superior de dicha lista) y un botón que permite la visualización del Grafo Social. Además al realizar un doble click sobre los usuarios del histórico se abre una ventana que posee la información del mismo. En la Figura 4.17 se ilustra la ventana principal de la herramienta al inicio de la ejecución, es decir, previo a la obtención del primer conjunto de semillas.

Figura 4.17. Captura de la ventana principal de la herramienta

previo a la selección del primer conjunto de semillas.

En la Figura 4.18 se ilustra la ventana principal de la herramienta transcurridos unos minutos. Es decir, luego de haber seleccionado distintos conjuntos de semillas. Allí puede verse la información perteneciente alSeed Set y la aparición de los usuarios en el histórico de semillas.

Figura 4.18. Captura de la ventana principal de la herramienta

luego de varias selecciones del conjunto de semillas.

79

En la Figura 4.19, se ilustra la ventana correspondiente al Grafo Social previo a la obtención del primer conjunto de semillas. Es decir, correspondiente con presionar el botón SHOW SOCIAL GRAPH en la ventana principal de la Figura 4.17.

Figura 4.19. Captura de la ventana de visualización del Grafo Social

previo a la selección del primer conjunto de semillas. Análogamente en la Figura 4.20, se ilustra la ventana correspondiente al

Grafo Social tras la obtención de reiterados conjunto de semillas. Es decir, correspondiente con presionar el botón SHOW SOCIAL GRAPH en la ventana principal de la Figura 4.18.

Figura 4.20. Captura de la ventana de visualización del Grafo Social

luego de la selección de varios conjuntos de semillas.

80

En la Figura 4.20, puede apreciarse la distinción de usuarios por sus diversos

colores. En azul los nodos que pertenecen al conjunto actual de semillas. En celeste los usuarios que son sólo realizadores de acciones y no han hecho ni retweet ni reply sobre publicaciones de otros usuarios. En rojo se indican aquellos usuarios que han realizado al menos un retweet o un reply. Finalmente, en verde se identifican aquellos nodos que fueron añadidos a la red por la búsqueda de usuarios intermedios.

En las Figuras 4.21 y 4.22 se ilustran dos perfiles de usuarios diferentes. Uno es aún semilla (Figura 4.21) y el otro (Figura 4.22) ha pertenecido alguna vez al Seed Set pero no se encuentra en el conjunto actual. En ambas puede apreciarse que se listan las acciones realizadas por los usuarios así como información adicional en el panel superior izquierdo. En el panel inferior, se visualizan los gráficos que indican la posición en el Seed Set en función del tiempo.

Figura 4.21. Captura de la ventana de visualización del Perfil

de un usuario que es semilla en la actualidad.

81

Figura 4.22. Captura de la ventana de visualización del Perfil de un usuario que ha pertenecido al conjunto de semillas.

En resumen, en el presente capítulo se describieron en forma detallada los

distintos módulos contenidos en la herramienta TSeedS. Además se evidencian y justifican decisiones de diseño tomadas. También se indican las librerías externas incluidas (Twitter4J, JFreeChart, JUNG) y se indica en qué módulos y para qué son utilizadas. El análisis de los diagramas ilustrados en el capítulo también permite indicar en qué fragmentos de código se llevan a cabo las diferentes etapas del enfoque propuesto.

82

5. Resultados Experimentales En este capítulo se muestran los experimentos realizados sobre la

herramienta desarrollada en el presente trabajo. Para llevar a cabo los experimentos previamente se definieron dos casos de estudio de interés. El primer caso de estudio se relaciona con la temática “Fútbol” y el segundo con la temática “Política”. Ambos casos tienen como objetivo mostrar el funcionamiento de las distintas etapas del enfoque propuesto. Por un lado, las primeras dos etapas se agrupan bajo las secciones de Análisis de Información de los casos. Estas etapas refieren a la Obtención de Información y a la Generación de Estructuras. Para ello, se ilustran y analizan los resultados obtenidos respecto a distintos aspectos de las etapas en cuestión, como el streaming y los filtros aplicados, las solicitudes de información adicionales realizadas, la cantidad de usuarios y enlaces en el Grafo Social, y la cantidad de nodos intermedios creados a partir de la búsqueda de caminos críticos entre usuarios.

Por otro lado, para mostrar el funcionamiento de las dos últimas etapas del enfoque, se agrupan las mismas bajo las secciones de Análisis de Resultados. Estas etapas refieren a la Interpretación y Visualización de Resultados. Para ello, se ilustran los resultados obtenidos tras la utilización de la herramienta y se analizan diferentes temas de las etapas en cuestión, como la variabilidad en el Seed Set, el contenido de las interacciones de las semillas, la cantidad de acciones e interacciones realizadas por dichas semillas, la evolución de la influencia del usuario en el tiempo y posibles justificaciones de sus apariciones en el conjunto seleccionado.

El capítulo se encuentra organizado por secciones. En particular, la sección 5.1 describe la estructura de los experimentos realizados y las configuraciones iniciales indicadas. Luego en las secciones 5.2 y 5.3 se tratan los casos de estudio planteados. Cabe destacar que ambas secciones poseen subsecciones para diferenciar el Análisis de Información del Análisis de Resultados, tópicos mencionados anteriormente. Por último en la sección 5.4 se analizan de manera comparativa los resultados obtenidos en los casos de estudio.

5.1. Estructura de los Experimentos Se realizaron dos experimentos basados en el funcionamiento en tiempo real

de la herramienta desarrollada, TSeedS. En ambos experimentos la aplicación estuvo activa durante 4 horas capturando interacciones de la red social Twitter y generando los distintos Seed Set con el transcurso del tiempo. Cabe destacar que se realizaron modificaciones sobre la herramienta para poder extraer información adicional de su comportamiento. Básicamente las modificaciones radicaron en el

83

volcado de la información en archivos con el objetivo de realizar un análisis más profundo en los casos de estudio.

La configuración inicial de los experimentos es la misma para ambos, exceptuando las keywords contenidas en el filtro de categoría. Estas últimas se modifican para los distintos casos de estudio según la temática de interés. En la Figura 1 se ilustran las configuraciones iniciales para llevar a cabo los experimentos. Las mismas son indicadas en el archivo initconfig.txt.

Figura 5.1. Contenido del archivo initconfig.txt.

En la Figura 5.1, puede apreciarse que el tiempo seleccionado como

entrenamiento de la herramienta equivale a diez minutos. Este tiempo se especifica en el campo TrainingWindow e indica cuánto se espera para la obtención del primer conjunto de semillas. Dicho valor fue seleccionado con el objetivo de que el Seed Set seleccionado surja tras un Grafo Social y un Registro de Propagaciones ya enriquecidos y no con escasa información. Luego puede verse que el valor del tiempo seleccionado como ventana de actualización equivale a un minuto. Este tiempo se especifica en el campo UpdateWindow e indica cada cuánto se recalcula el Seed Set. Para el presente caso de 4 horas, se recalcula 230 veces el Seed Set.

También se muestra el valor del filtro temporal que equivale a una hora (60 minutos). Este tiempo se especifica en el campo OlderTime y se utiliza para establecer una ventana de antigüedad sobre la interacción. Es decir, se usa para chequear que el tiempo de origen de una interacción no sobrepase cierto tiempo límite. Esto tiene como objetivo acotar el dominio de interacciones que son escuchadas tras el streaming, limitando el mismo a acciones consideradas recientes.

Por otro lado, en dicha configuración se indican los directorios donde se encuentran los filtros de idioma y categoría. Como se indicó previamente las keywords de categoría se modifican en los distintos casos de estudio y es por ello que no serán ilustradas en este sección. Sin embargo, el filtro de idioma a aplicar es igual para ambos casos de estudio y se ilustra en la Figura 5.2.

Figura 5.2. Contenido del archivo lang­filter.txt.

84

Como puede verse los idiomas seleccionados son español (es) e indeterminado (und). Este último es agregado ya que múltiples cuentas de Twitter no indican su idioma y no se desea perder dicha información.

Además deben indicarse las configuraciones para la ejecución de la herramienta Influence Models. En la Figura 5.3 se muestra el contenido del archivo de configuración que contiene los parámetros necesarios.

Figura 5.3. Contenido del archivo config_maxinf_CD.txt.

Como se explicó en el capítulo anterior, el parámetrophase permite indicar el

modo de funcionamiento de la herramienta. En este caso, el valor es 12 ya que el mismo identifica a la función de Selección de Semillas para la Maximización de la Influencia bajo el CD que provee la herramienta. En base a dicha manera de funcionamiento se deben añadir ocho parámetros al archivo de configuración como ilustra la Figura 5.3. Las rutas a las entradas generadas por la herramienta TSeedS para la ejecución del Influence Models se generan en la carpeta training y se almacenan con los nombres mostrados en la Figura 5.3. El directorio en el que almacenará la salida es maxinf_CD aunque cabe destacar que este puede ser modificado sin problemas.

Respecto al parámetro maxTuples que equivale a cero, se indicó con anterioridad que dicho valor permite que se consideren todas las tuplas del Log de Acciones. El umbral de truncamiento (truncation_threshold) indica que los valores por debajo del mismo son descartados del cómputo del crédito otorgado a nodos influyentes. En los experimentos de [4] se determina que el valor 0.001 obtiene muy buenos resultados y es por ello que fue seleccionado. Finalmente, el parámetro budget que indica cuántas semillas se desean determinar. Para los experimentos realizados se indicó el valor diez para dicho parámetro con el objetivo de analizar los diez usuarios que maximizan la influencia en la red.

Bajo las configuraciones iniciales de la herramienta TSeedS antes explicadas y las configuraciones de ejecución del Influence Models se llevaron a cabo los

85

experimentos y sus resultados se analizan en las secciones siguientes en los dos casos de estudio planteados.

5.2. Caso de Estudio 1: Fútbol El presente Caso de Estudio tiene como objetivo ilustrar el funcionamiento de

las diversas etapas del enfoque propuesto bajo la temática “Fútbol”. Para ello, la keyword utilizada para el filtro de categoría fue “futbol” como se muestra en la Figura 5.4.

Figura 5.4. Contenido del archivo cat­filter.txt

en el caso de estudio 1. En las secciones siguientes se presentan los resultados obtenidos tras el

experimento realizado. Estos se dividen según las distintas etapas del enfoque en el Análisis de Información y el Análisis de Resultados. Como se explicó anteriormente el primero refiere a las primeras dos etapas (Obtención de Información y Generación de Estructuras) y el segundo refiere a las últimas dos etapas (Interpretación y Visualización de Resultados). En otras palabras, en las secciones siguientes se ilustran los resultados obtenidos tras el experimento realizado según los distintos puntos de interés de análisis del presente caso de estudio.

5.2.1. Análisis de Información Como se indicó previamente, en esta sección se analizan los resultados

obtenidos correspondientes a la primera y a la segunda etapa del enfoque propuesto. En el caso de la Obtención de Información (etapa 1) se muestran resultados relacionados con el filtrado de interacciones en la sección 5.2.1.1. En el caso de la Generación de Estructuras (etapa 2) se muestran resultados referidos a la generación del Grafo Social en la sección 5.2.1.3. En la sección 5.2.1.2 se muestran resultados que involucran parte de ambas etapas en lo que refiere a la información adicional que se solicita a Twitter.

5.2.1.1. Filtrado de Interacciones Esta sección tiene como objetivo ilustrar los resultados obtenidos respecto a

la aplicación de filtros sobre la información provista por Twitter en tiempo real. Previamente se aclara que la aplicación de filtros en la herramienta respeta el siguiente orden: primero el filtro por categoría (directo sobre el streaming), luego el filtro de idioma o lenguaje y finalmente el filtro de antigüedad de interacciones.

86

Para poder realizar comparaciones sobre el primer filtro se deberían conocer la cantidad de interacciones generadas por toda la red Twitter en el intervalo de tiempo que se llevó a cabo el experimento. Esto resulta impracticable ya que la API de Twitter solo aporta un porcentaje de interacciones de las generadas realmente por toda la red en cada instante de tiempo. Es por ello que se procede al análisis de los siguientes filtros en cuestión.

A través del streaming de Twitter (con el filtro de categoría aplicado) se escucharon 9977 interacciones en un intervalo de tiempo de 4 horas. De dichas interacciones, 7921 pasaron el filtro de idioma propuesto en el experimento. Por ende aproximadamente un 79% de las interacciones interceptadas por el streaming pasan el filtro de idioma. De estas 7921 interacciones que pasaron el filtro de idioma, 3601 eran tweets, 3917 eran retweets y 403 eran replies. En la tabla ilustrada en la Figura 5.5 se resume la información antes explicada mostrando algunos valores porcentuales tras la aplicación del filtro de idioma.

Figura 5.5. Información del Filtro de Idioma para el caso de estudio 1.

Además tras los resultados obtenidos surgió el interés de mostrar un análisis

de las interacciones denominadasreplies. En la Figura 5.6 se ilustran losreplies que fueron aceptados y rechazados por la herramienta en el momento posterior al filtro de idioma y previo a la aplicación del filtro temporal.

87

Figura 5.6. Información sobre replies entre el Filtro de Idioma

y el Filtro Temporal para el caso de estudio 1.

En la Figura 5.6 se puede apreciar el alto porcentaje de replies rechazados por la herramienta por diversas razones. Una de ellas, es el denominadoautoreply. Este tipo de interacción indica que un usuario se respondió a sí mismo otra interacción. Lógicamente no debería permitirse que la influencia del usuario en cuestión aumente por decisión propia y es por ello que la interacción es rechazada. Por otro lado puede observarse que se rechazaron 6 replies porque la API de Twitter no permitió la visualización de la interacción original. Esto se relaciona con la privacidad de las cuentas de usuarios en cuestión. Por último, se refleja que 122 replies fueron rechazados por no tener alguna interfaz de Twitter disponible para realizar las consultas necesarias.

Luego sobre las 7921 interacciones que pasaron el anterior filtro, se aplica el filtro temporal. En la Figura 5.7 puede observarse una tabla similar a la ilustrada para el filtro de idioma, que muestra la cantidad de interacciones que pasan dicho filtro y el tipo de las mismas. Análogamente, se añaden los valores porcentuales correspondientes.

Figura 5.7. Información del Filtro de Temporal para el caso de estudio 1.

Por ende, aproximadamente un 83% de las interacciones que pasaron el filtro

de idioma también pasaron el filtro temporal. A modo de conclusión del análisis realizado, se indica que aproximadamente el 66% de las interacciones que son interceptadas por el streaming originalmente, se consideran como válidas para llevar a cabo la siguiente etapa del enfoque.

88

5.2.1.2. Información Adicional Como se explicó con anterioridad en el presente trabajo, en diversas

situaciones es necesario completar determinada información de las interacciones provenientes del streaming. Ya sea para la identificación de origen de los replies o para la búsqueda de un camino crítico entre usuarios, se realizan consultas a Twitter a través de una interfaz. Esta interfaz posee limitaciones de solicitudes por intervalo de tiempo dependiendo el tipo de consulta y es por ello que esta sección resulta de interés para el caso de estudio en cuestión. Dichas limitaciones (sobre las solicitudes realizadas desde la herramienta) se ilustran en la Figura 5.8 y fueron extraídas de la página oficial de la API de Twitter . 15

Figura 5.8. Limitaciones de la API de Twitter.

Tras el experimento, se identificó que la herramienta realizó en total 4991

solicitudes en el transcurso de 4 horas. Esto indica un promedio de 20,8 solicitudes por minuto, que llevado a la ventana temporal que establece la API de Twitter, equivale a un promedio de 312 solicitudes por cada 15 minutos. Estos resultados se ilustran en la Figura 5.9.

Figura 5.9. Resumen de solicitudes por unidad

de tiempo del caso de estudio 1.

De las solicitudes antes mencionadas, 256 fueron realizadas para permitir el chequeo temporal de los replies y 4735 fueron realizadas con el objetivo de completar la información adicional necesaria para la búsqueda de caminos críticos entre usuarios. Por otro lado, también cabe destacar que las solicitudes que no se

15 Twitter API Limits: https://dev.twitter.com/rest/public .

89

pudieron realizar por falta de disponibilidad de la interfaz de Twitter fueron 1077, de las cuales 122 fueron rechazadas para el chequeo temporal de los replies. En la Figura 5.10, se muestra un resumen de la información recién enunciada.

Figura 5.10. Resumen de solicitudes por interés

de su realización del caso de estudio 1.

Más allá del análisis de los promedios que se pueda realizar, la cantidad de solicitudes a procesar (tanto realizadas como rechazadas) no admiten patrones temporales ni permiten obtener justificaciones a corto plazo de por qué se pudieron o no llevar a cabo. De hecho, dependen estrictamente de los usuarios y las interacciones en cuestión en tiempo real. Este último factor es el que impide realizar el análisis en distintas situaciones ya que los datasets son diferentes cada vez que se ejecuta la herramienta.

5.2.1.3. Generación del Grafo Social En esta sección se muestran la cantidad de usuarios que se ingresaron al

sistema tras el experimento realizado y junto con ellos la cantidad de vínculos creados. Cabe destacar que en la visualización del grafo los nodos que no tienen enlaces no son mostrados y en esta sección también se indican cuántos de estos casos se encontraron. En la Figura 5.11, se puede apreciar el crecimiento de la cantidad de usuarios en función del tiempo, indicando además qué cantidad de usuarios se encuentran relacionados en la red y qué cantidad de ellos son nodos aislados. El gráfico se realiza sobre intervalos de 15 minutos.

90

Figura 5.11. Gráfico de cantidad de usuarios del caso de estudio 1.

En base al gráfico ilustrado en la Figura 5.11, se puede observar que por más

que transcurre el tiempo la cantidad de nodos aislados continúa siendo grande. Cabe destacar que la existencia de los mismos no aporta información para la determinación de los nodos más influyentes ya que para convencerlos de la realización de una acción habría que seleccionarlos en el Seed Set. Respecto a los nodos relacionados, en la Figura 5.12 se ilustra un gráfico que compara la cantidad de aristas creadas con lo que refiere a la cantidad de usuarios conectados. Al igual que el gráfico mostrado previamente se seleccionan intervalos de 15 minutos.

Figura 5.12. Gráfico de comparativa de aristas creadas vs. nodos relacionados del caso de estudio 1.

91

La Figura 5.12 permite ilustrar que la cantidad de aristas creadas permite la conexión de un alto porcentaje de nodos. Esto es fundamental para lograr buenos resultados a la hora de la selección de semillas, ya que no hay gran dispersión de vínculos entre usuarios.

También resulta interesante destacar que se alcanzó un total de 179 nodos intermedios creados tras la búsqueda de caminos críticos entre usuarios. Estos realizan grandes aportes de información ya que hacen más real la vinculación entre usuarios y permiten analizar de mejor forma la propagación de las acciones.

Sin embargo, también es importante notar aquellos enlaces que se crearon de manera directa a pesar de que el usuario que interactúa no siga al usuario que realizó la acción original. Esta cantidad alcanzó un total de 134 enlaces directos creados que en realidad no lo eran. Como se explicó anteriormente, este valor no implica que el establecimiento de la relación directa sea incorrecto, ya que puede que el usuario que interactúa acceda a la cuenta de otro usuario sin nodos en común y realice unretweet. También hay que aclarar que este número puede crecer en momentos en los que no hay disponibilidad de solicitudes a realizar sobre la interfaz de Twitter.

5.2.2. Análisis de Resultados Como se indicó previamente, en esta sección se analizan los resultados

obtenidos referidos a la cuarta y a la quinta etapa del enfoque propuesto. En el caso de la Interpretación de Resultados (etapa 4) se muestran resultados relacionados con la variabilidad de los Seed Set en la sección 5.2.2.1. En el caso de la Visualización de Resultados (etapa 5) se muestran resultados referidos a la evolución de las semillas seleccionadas y posibles justificaciones de sus apariciones en los Seed Set en la sección 5.2.2.2.

5.2.2.1. Variabilidad del Seed Set En esta sección se analizan los distintos Seed Set seleccionados por la

herramienta tras la etapa de Obtención del Conjunto de Semillas y su variación en el tiempo. En primer lugar se ilustra en la Figura 5.13, el Seed Set obtenido tras los diez primeros minutos del experimento, tomado como tiempo de entrenamiento, tal como se explicó con anterioridad en el presente capítulo.

92

Figura 5.13. Primer Seed Set obtenido en el caso de estudio 1.

Con el transcurso del tiempo dicho conjunto inicial se modifica ya sea por la

selección de una semilla distinta o por el cambio de posicionamiento de un mismo usuario. Tras el análisis de los resultados obtenidos se encontraron 47 usuarios distintos sobre un total de 230 Seed Set calculados (el primero tras 10 minutos y luego cada un minuto). Dicha cantidad de conjuntos equivale a un máximo teórico de 2300 usuarios distintos. Es decir, que la variabilidad respecto del valor máximo equivale a 0,0204 (usuarios distintos obtenidos sobre máximo teórico).

Los usuarios pertenecientes al Seed Set seleccionado por primera vez (ver Figura 12), en el transcurso del tiempo logran alcanzar las 780 apariciones sobre el máximo posible de 2300. Lo que indica que este primer Seed Set representa el 34% de los 230 conjuntos calculados.

Por otro lado, cabe destacar que el promedio de apariciones en el Seed Set equivale aproximadamente a 49 presencias. Dicho valor analizado desde el punto de vista de minutos, es alto para un experimento de 4 horas (240 minutos).

Por otra parte, se observó tras los resultados obtenidos que con sólo 7 usuarios se logra obtener más del 50% de apariciones totales en losSeed Set y con 12 usuarios más del 75%.

Por los datos estadísticos explicados anteriormente se deduce que la variabilidad de los Seed Set seleccionados del presente caso de estudio es baja. En la Figura 5.14 se ilustra un resumen de la cantidad de apariciones en los Seed Set de los distintos usuarios. Aquellos resaltados en color rojo son los usuarios que fueron elegidos en el primer Seed Set calculado.

93

Figura 5.14. Resumen de apariciones de usuarios en los

Seed Set calculados en el caso de estudio 1.

5.2.2.2. Semillas Seleccionadas En esta sección se analizan los diferentes usuarios que pertenecieron a los

conjuntos de semillas seleccionados. La función de este análisis es mostrar que la herramienta TSeedS permite cumplir con uno de los objetivos centrales del enfoque propuesto, el cual radica en mostrar la evolución de la influenciabilidad de los usuarios. Para tratar este tema se observaron los gráficos de posición en el Seed Set en función del tiempo provistos por la herramienta. Esto se realizó para los distintos usuarios que pertenecieron a los diferentes conjuntos de semillas seleccionados. A modo de resumen, se seleccionaron seis usuarios para realizar distintas comparaciones con los gráficos obtenidos. De manera complementaria, se tiene en cuenta la información relacionada con la cantidad de interacciones en las que se involucraron los usuarios.

Con los gráficos que evidencian la evolución y la información complementaria considerada, se analizan posibles justificaciones de las apariciones de los usuarios en los conjuntos seleccionados. Los usuarios en cuestión son @memedeportes,

94

@orioldomenech, @hoyextremadura, @Tigre_VAVEL, @RConfidencial y @CARiverPlate. Tanto @memedeportes como @RConfidencial aparecen en el 100% de los Seed Set calculados. Por su parte, @orioldomenech y @CARiverPlate se encuentran entre el 15% y 20% de los conjunto calculados. Finalmente, los usuarios @hoyextremadura y @Tigre_VAVEL aparecen entre el 1,5% y el 4% de los Seed Set obtenidos.

En primer lugar, se analizan los casos de los usuarios @hoyextremadura y @Tigre_VAVEL cuya permanencia en los Seed Set seleccionados no fue muy duradera. En la Figura 5.15 se ilustra el gráfico de evolución de influencia para el primero de ellos.

Figura 5.15.Gráfico de Evolución de Influencia del usuario @hoyextremadura en el caso de estudio 1.

El gráfico de la Figura 5.15 permite apreciar la ínfima permanencia del

usuario en los conjuntos de influyentes. Además también se puede visualizar que cuando se seleccionó el mismo la influencia alcanzada no era significativa. En la Figura 5.16, se ilustra la información complementaria al gráfico extraída de los resultados obtenidos.

95

Figura 5.16. Información complementaria del usuario

@hoyextremadura en el caso de estudio 1. Tal cual refleja el gráfico ilustrado en la Figura 5.15, la cantidad de presencias

en los Seed Set es muy pequeña. También puede verse las pocas interacciones que tuvo como usuario influyente. Dichas interacciones se analizan tras los valores de los campos Nro de Replied y Nro de Retweeted.

En la Figura 5.17 se muestra el gráfico de evolución de influencia para el segundo de los usuarios en cuestión.

Figura 5.17.Gráfico de Evolución de Influencia del usuario @Tigre_VAVEL en el caso de estudio 1.

De manera similar a lo observado con el usuario anterior, el gráfico de la

Figura 5.17 permite apreciar la ínfima permanencia del usuario en los conjuntos de influyentes. Sin embargo, se puede apreciar en el caso del presente gráfico, que previo a la desaparición del mismo de los Seed Set seleccionados, se puede ver un pequeño decrecimiento. A diferencia del usuario @hoyextremadura, en este caso se

96

logra alcanzar la séptima posición en el Seed Set. En la Figura 5.18, se ilustra la información, complementaria al gráfico, extraída de los resultados obtenidos para el usuario en cuestión.

Figura 5.18. Información complementaria del usuario

@Tigre_VAVEL en el caso de estudio 1.

La información complementaria permite apreciar que con el mismo valor de influencia marginal alcanzado por el presente usuario y aún con menor cantidad de interacciones en las que fue referenciado se logró un mejor posicionamiento en los Seed Set y una mayor permanencia en la selección de los mismos. Esto puede ocurrir por diversas razones como por ejemplo los tiempos de propagación de las interacciones, vínculos establecidos con otros nodos, el resto del conjunto de usuarios seleccionados, etc.

En segundo lugar, se analizan los casos de los usuarios @CARiverPlate y @orioldomenech cuya permanencia en los Seed Set seleccionados rondó entre el 15% y el 20%, respectivamente. En la Figura 5.19, se muestra el gráfico de evolución de influencia para el primero de ellos.

97

Figura 5.19.Gráfico de Evolución de Influencia del usuario @CARiverPlate en el caso de estudio 1.

El gráfico de la Figura 5.19 permite apreciar que la permanencia del usuario

en cuestión es notoriamente mayor al de los analizados con anterioridad. De manera similar al caso anterior, se puede indicar que previo a la desaparición de los Seed Set se nota un decrecimiento en la influencia del usuario. Aunque en el presente caso, la presencia del usuario es más prolongada y su desaparición se extiende, estando varios minutos en la última posición del Seed Set seleccionado. En la Figura 5.20, se ilustra la información complementaria al gráfico extraída de los resultados obtenidos.

Figura 5.20. Información complementaria del usuario

@CARiverPlate en el caso de estudio 1.

La Figura 5.20 muestra una mayor cantidad de interacciones como influyente aunque también se indica la realización de múltiples acciones. Por ende, puede que la propagación haya sido más distribuida (por ejemplo, 2 retweets a cada tweet) o

98

puede que la propagación haya sido más centralizada (por ejemplo, 10 retweets a un solo tweet). También cabe aclarar que aunque el valor máximo de ganancia marginal alcanzado es el indicado en la Figura 5.20, la mejor posición la logró alcanzar con un valor de ganancia menor. Esto permite deducir que aunque el valor de ganancia era menor, era significativo en el Seed Set seleccionado y por ello se obtenía un mejor posicionamiento. Por otro lado, en el momento en que obtuvo el valor más alto de ganancia, dicho valor no era tan significativo en el Seed Set seleccionado. De esta forma, se explica que su posicionamiento sea peor aunque su ganancia sea mayor que en otras oportunidades.

En la Figura 5.21 se ilustra el gráfico de evolución de influencia para el segundo de los usuarios en cuestión, la cuenta @orioldomenech.

Figura 5.21. Gráfico de Evolución de Influencia del usuario @orioldomenech en el caso de estudio 1.

La Figura 5.21 permite apreciar una gran variabilidad en la influenciabilidad

del usuario a pesar de sus breves presencias en el Seed Set. Primero es importante resaltar que cuando la línea es diagonal indica la no presencia en los Seed Set durante dichos minutos. Por ende, se puede deducir que el usuario logra crecimientos y decrecimientos fugaces (en cantidad de minutos) de influenciabilidad aunque nunca alcanza una de las primeras cinco posiciones en elSeed Set. Al igual que en varios casos anteriores, previo a la desaparición de los conjuntos se ilustra un decrecimiento en la influenciabilidad del usuario.

En la Figura 5.22, se muestra la información complementaria al gráfico extraída de los resultados obtenidos del presente caso de estudio para el usuario @orioldomenech.

99

Figura 5.22. Información complementaria del usuario

@orioldomenech en el caso de estudio 1.

Análogamente a los resultados obtenidos sobre los dos primeros usuarios de la presente sección, la información complementaria permite apreciar que con un valor inferior de influencia marginal alcanzado por el presente usuario y aún con menor cantidad de interacciones en las que fue referenciado se logró un mejor posicionamiento en los Seed Set y una mayor permanencia en la selección de los mismos que el usuario @CARiverPlate. Como se indicó previamente, esto puede ocurrir por diversas razones, como tiempos de propagación de las interacciones, vínculos establecidos con otros nodos, el resto del conjunto de usuarios seleccionados, etc.

En tercer lugar, se analizan los casos de los usuarios @memedeportes y

@RConfidencial que estuvieron presentes en la totalidad de los Seed Set seleccionados. En las Figura 5.23 y 5.24 respectivamente, se ilustran los gráficos de evolución de influencia para los usuarios en cuestión.

100

Figura 5.23. Gráfico de Evolución de Influencia del usuario @memedeportes en el caso de estudio 1.

Figura 5.24. Gráfico de Evolución de Influencia del usuario @RConfidencial en el caso de estudio 1.

Si bien ambos usuarios permanecen en la totalidad de los Seed Set

seleccionados puede notarse una interesante diferencia en la influenciabilidad de los mismos. En el caso del usuario @memedeportes, se evidencia que desde el primer momento se posiciona como usuario influyente y además como se visualizó en secciones anteriores obtuvo gran cantidad de interacciones previo a la selección del primer Seed Set. En el caso del usuario @RConfidencial, si bien permanece casi en la cúspide (segunda posición en elSet) durante más de la mitad del tiempo que duró

101

el experimento, se puede apreciar el decrecimiento lento y marcado en la otra mitad del tiempo analizado.

En las Figuras 5.25 y 5.26 respectivamente, se ilustran los datos obtenidos como información complementaria para los usuarios en cuestión.

Figura 5.25. Información complementaria del usuario

@memedeportes en el caso de estudio 1.

Figura 5.26. Información complementaria del usuario

@RConfidencial en el caso de estudio 1.

Notoriamente pueden distinguirse los valores alcanzados de ganancia marginal y la cantidad de veces que fueron referenciadas sus interacciones (Nro de Retweeted y Nro de Replied). El usuario @memedeportes muestra su permanencia en los Seed Set siendo referenciado continuamente con el correr de los minutos indicando el perfil de un usuario realmente influyente. Por otro lado, el usuario @RConfidencial, con un número mucho menor de referencias sobre sus acciones realizadas, logra mantenerse en el Seed Set con el mismo valor de ganancia marginal que obtuvo casi desde un principio. Por ende podría decirse que el usuario @RConfidencial tuvo un buen comienzo en el que fue fuertemente referenciado y con esto se mantuvo por un largo tiempo en el conjunto seleccionado. Sin embargo, con el correr del tiempo dichas interacciones fueron perdiendo peso y su

102

desaparición del conjunto seleccionado parecía ser casi un hecho si se hubiese corrido el experimento durante una brecha horaria mayor a la establecida.

Tras el caso de estudio 1 y el análisis de los resultados obtenidos se concluye que la herramienta TSeedS permite lograr con el objetivo central del enfoque propuesto en el presente trabajo referido al análisis de la evolución de la influencia de los usuarios. Esto abarca la sección actual referida a las etapas 4 y 5 del enfoque. Complementariamente, resultó de gran importancia el análisis realizado sobre las primeras dos etapas ya que permitió extraer interesantes conclusiones sobre los filtrados, la información adicional y la generación del Grafo Social. Respecto al caso de estudio 1 en particular, se puede deducir que previo a la desaparición del conjunto seleccionado todos los usuarios indicaron un decrecimiento leve o trascendente de su influenciabilidad. Esto parece lógico pero podría haberse dado que tras los cálculos de los nuevos Set los usuarios perdieran drásticamente el aporte de ganancia marginal que alcanzaban previamente.

5.3. Caso de Estudio 2: Política El presente Caso de Estudio tiene como objetivo ilustrar el funcionamiento de

las diversas etapas del enfoque propuesto bajo la temática “Política”. Para ello, la keyword utilizada para el filtro de categoría fue “politica” como se muestra en la Figura 5.27.

Figura 5.27. Contenido del archivo cat­filter.txt

en el caso de estudio 2. De forma análoga a lo hecho en el caso de estudio previo, en las secciones

siguientes se presentan los resultados obtenidos tras el experimento realizado. Estos se dividen según las distintas etapas del enfoque en el Análisis de Información y el Análisis de Resultados que como se explicó anteriormente el primero refiere a las primeras dos etapas (Obtención de Información y Generación de Estructuras) y el segundo refiere a las últimas dos etapas (Interpretación y Visualización de Resultados). En otras palabras, en las secciones siguientes se ilustran los resultados obtenidos tras el experimento realizado según los distintos puntos de interés de análisis del presente caso de estudio.

103

5.3.1. Análisis de Información En esta sección se analizan los resultados obtenidos referidos a la primera y

a la segunda etapa del enfoque propuesto. En el caso de la Obtención de Información (etapa 1) se muestran resultados relacionados con el filtrado de interacciones en la sección 5.3.1.1. En la sección 5.3.1.2 se muestran resultados que involucran parte de ambas etapas en lo que refiere a la información adicional que se solicita a Twitter. Por último, en el caso de la Generación de Estructuras (etapa 2) se muestran resultados referidos a la generación del Grafo Social en la sección 5.3.1.3.

5.3.1.1. Filtrado de Interacciones Esta sección tiene como objetivo ilustrar los resultados obtenidos respecto a

la aplicación de filtros sobre la información provista por Twitter en tiempo real. Al igual que en el caso de estudio 1 se aclara que la aplicación de filtros en la herramienta respeta el siguiente orden: primero el filtro por categoría (directo sobre el streaming), luego el filtro de idioma o lenguaje y finalmente el filtro de antigüedad de interacciones.

Por razones explicadas en el caso de estudio previo no se realizan comparativas respecto del filtro de categoría y la totalidad de interacciones de la red Twitter. Por ende se procede al análisis de los siguientes filtros en cuestión.

A través del streaming de Twitter (con el filtro de categoría aplicado) se escucharon 11475 interacciones en un intervalo de tiempo de 4 horas. De dichas interacciones, 8948 pasaron el filtro de idioma propuesto en el experimento. Por ende aproximadamente un 78% de las interacciones interceptadas por el streaming pasan el filtro de idioma. De estas 8948 interacciones que pasaron el filtro de idioma, 2601 eran tweets, 6157 eran retweets y 190 eran replies. En la Figura 5.28 se resume la información antes explicada mostrando algunos valores porcentuales tras la aplicación del filtro de idioma.

104

Figura 5.28. Información del Filtro de Idioma para el caso de estudio 2.

Tras lo descubierto en el caso de estudio 1 de pérdida dereplies entre el filtro

de idioma y el filtro temporal. En la Figura 5.29 se ilustran los replies que fueron aceptados y rechazados por la herramienta en dicho momento.

Figura 5.29. Información sobre replies entre el Filtro de Idioma

y el Filtro Temporal para el caso de estudio 2. En la Figura 5.29 se puede apreciar el alto porcentaje de replies rechazados

por la herramienta que como se analizó anteriormente se debe a diversas razones. Dichas razones son, el denominadoautoreply, aquellosreplies que la API de Twitter no permitió la visualización de la interacción original, y replies que fueron rechazadas por no tener alguna interfaz de Twitter disponible para realizar las consultas necesarias.

Luego sobre las 8948 interacciones que pasaron el anterior filtro, se aplica el filtro temporal. Es importante resaltar la gran disminución de los retweets válidos tras la aplicación de este filtro. En particular, de 6157retweetsque pasan el filtro de idioma, sólo 2741 (el 44%) logran pasar el filtro temporal. Esto permite inducir que

105

en la presente temática, la propagación de las acciones se realice con un retardo mayor que en otras como la estudiada en el caso 1.

En la Figura 5.30 puede observarse una tabla similar a la ilustrada para el filtro de idioma, que muestra la cantidad de interacciones que pasan dicho filtro y el tipo de las mismas. Análogamente, se añaden los valores porcentuales correspondientes.

Figura 5.30. Información del Filtro de Temporal para el caso de estudio 2.

Por ende, aproximadamente un 60% de las interacciones que pasaron el filtro

de idioma también pasaron el filtro temporal. A modo de conclusión del análisis realizado, se indica que aproximadamente el 47% de las interacciones que son interceptadas por el streaming originalmente, se consideran como válidas para llevar a cabo la siguiente etapa del enfoque.

5.3.1.2. Información Adicional Como se explicó con anterioridad en el caso de estudio 1, en diversas

situaciones es necesario completar determinada información de las interacciones provenientes del streaming. Ya sea para la identificación de origen de los replies o para la búsqueda de un camino crítico entre usuarios, se realizan consultas a Twitter a través de una interfaz. A modo de recordatorio las limitaciones (sobre las solicitudes realizadas desde la herramienta) se ilustran en la Figura 5.31 y fueron extraídas de la página oficial de la API de Twitter . 16

Figura 5.31. Limitaciones de la API de Twitter.

16 Twitter API Limits: https://dev.twitter.com/rest/public .

106

Tras el experimento se identificó que la herramienta realizó en total 3733 solicitudes en el transcurso de 4 horas. Esto indica un promedio de 15,55 solicitudes por minuto, que llevado a la ventana temporal que establece la API de Twitter, equivale a un promedio de 233 solicitudes por cada 15 minutos. Los promedios de solicitudes realizadas y rechazadas por unidad de tiempo se ilustran en la Figura 5.32.

Figura 5.32. Resumen de solicitudes por unidad

de tiempo del caso de estudio 2.

De las solicitudes antes mencionadas, 105 fueron realizadas para permitir el chequeo temporal de los replies y 3628 fueron realizadas con el objetivo de completar la información adicional necesaria para la búsqueda de caminos críticos entre usuarios. Por otro lado, también caben destacar las solicitudes que no se pudieron realizar por falta de disponibilidad de la interfaz de Twitter. Estas alcanzaron las 1475 solicitudes sin resolver, de las cuales 69 intentaron obtener información para realizar el chequeo temporal de los replies. En la Figura 5.33, se ilustra un resumen de la información recién enunciada.

Figura 5.33. Resumen de solicitudes por interés

de su realización del caso de estudio 2.

Como se mencionó en el caso de estudio 1, más allá del análisis de los promedios que se pueda realizar, la cantidad de solicitudes a procesar (tanto realizadas como rechazadas) no admiten patrones temporales ni permiten obtener justificaciones a corto plazo de por qué se pudieron o no llevar a cabo. De hecho,

107

dependen estrictamente de los usuarios y las interacciones en cuestión en tiempo real. Este último factor es el que impide realizar el análisis en distintas situaciones ya que los datasets son diferentes cada vez que se ejecuta la herramienta.

5.3.1.3. Generación del Grafo Social En esta sección se muestran la cantidad de usuarios que se ingresaron al

sistema tras el experimento realizado y junto con ellos la cantidad de vínculos creados. En la Figura 5.34, se puede apreciar el crecimiento de la cantidad de usuarios en función del tiempo indicando además qué cantidad de usuarios se encuentran relacionados en la red y qué cantidad de ellos son nodos aislados. El gráfico se realiza sobre intervalos de 15 minutos.

Figura 5.34. Gráfico de cantidad de usuarios del caso de estudio 2.

En base al gráfico ilustrado en la Figura 5.34, se puede observar que,

mientras transcurre el tiempo, la cantidad de nodos aislados tiende a disminuir su crecimiento, aunque no se observa una pendiente negativa en ningún momento. Como se enunció anteriormente, la existencia de estos nodos aislados no aporta información para la determinación de los nodos más influyentes ya que para convencerlos de la realización de una acción habría que seleccionarlos en el Seed Set.

Respecto a los nodos relacionados, en la Figura 5.35 se ilustra un gráfico que compara la cantidad de aristas creadas con lo que refiere a la cantidad de usuarios conectados. Al igual que el gráfico mostrado previamente se seleccionan intervalos de 15 minutos.

108

Figura 5.35. Gráfico de comparativa de aristas creadas vs. nodos relacionados del caso de estudio 2.

La Figura 5.35 permite ilustrar que la cantidad de aristas creadas permite la

conexión de un altísimo porcentaje de nodos. Esto indica la fuerte conexión entre los nodos del Grafo Social. Además es fundamental para lograr buenos resultados a la hora de la selección de semillas, ya que no hay gran dispersión de vínculos entre usuarios.

También resulta interesante destacar que se alcanzó un total de 270 nodos intermedios creados tras la búsqueda de caminos críticos entre usuarios. Estos realizan grandes aportes de información ya que hacen más real la vinculación entre usuarios y permiten analizar de mejor forma la propagación de las acciones.

Sin embargo, también cabe notar aquellos enlaces que se crearon de manera directa a pesar de que el usuario que interactúa no siga al usuario que realizó la acción original. Esta cantidad alcanzó un total de 108 enlaces directos creados que en realidad no lo eran. Como se explicó con anterioridad, este valor no implica que el establecimiento de la relación directa sea incorrecto. También hay que aclarar que este número puede crecer en momentos en los que no hay disponibilidad de solicitudes a realizar sobre la interfaz de Twitter.

5.3.2. Análisis de Resultados Como se indicó previamente, en esta sección se analizan los resultados

obtenidos referidos a la cuarta y a la quinta etapa del enfoque propuesto. En el caso de la Interpretación de Resultados (etapa 4) se muestran resultados relacionados con la variabilidad de los Seed Set en la sección 5.3.2.1. En el caso de la Visualización de Resultados (etapa 5) se muestran resultados referidos a la evolución de las semillas seleccionadas y posibles justificaciones de sus apariciones en los Seed Set en la sección 5.3.2.2.

109

5.3.2.1. Variabilidad del Seed Set En esta sección se analizan los distintos Seed Set seleccionados por la

herramienta tras la etapa de Obtención del Conjunto de Semillas y su variación en el tiempo. En primer lugar se ilustra en la Figura 5.36, el Seed Set obtenido tras los diez primeros minutos del experimento, tomado como tiempo de entrenamiento.

Figura 5.36. Primer Seed Set obtenido en el caso de estudio 2.

Con el transcurso del tiempo dicho conjunto inicial se modifica ya sea por la

selección de semillas distintas o mismo por el posicionamiento de un mismo usuario. Tras el análisis de los resultados obtenidos se encontraron 31 usuarios distintos sobre un total de 230 Seed Set calculados (el primero tras 10 minutos y luego cada un minuto). Por ende la variabilidad respecto del valor máximo (2300) equivale a 0,0134 (usuarios distintos obtenidos sobre máximo teórico).

Los usuarios pertenecientes al Seed Set seleccionado por primera vez (ver Figura 35), en el transcurso del tiempo logran alcanzar las 630 apariciones sobre el máximo posible de 2300. Lo que indica que este primerSeed Set representa el 27% de los 230 conjuntos calculados.

Por otro lado, el promedio de apariciones en el Seed Set equivale aproximadamente a 74 presencias. Dicho valor analizado desde el punto de vista de minutos, es extremadamente alto para un experimento de 4 horas (240 minutos). Indica que en promedio un usuario permanece más de una hora en el conjunto de usuarios más influyentes.

Por otra parte, se observó tras los resultados obtenidos que con sólo 8 usuarios se logra obtener más del 50% de apariciones totales en losSeed Set y con 11 usuarios más del 75%.

Por los datos estadísticos explicados anteriormente se deduce que la variabilidad de los Seed Set seleccionados del presente caso de estudio es extremadamente baja. En la Figura 5.37 se ilustra un resumen de la cantidad de

110

apariciones en los Seed Set de los distintos usuarios. Aquellos resaltados en color rojo son los usuarios que fueron elegidos en el primer Seed Set calculado.

Figura 5.37. Resumen de apariciones de usuarios en los

Seed Set calculados en el caso de estudio 2.

5.3.2.2. Semillas Seleccionadas En esta sección se analizan los diferentes usuarios que pertenecieron a los

conjuntos de semillas seleccionados. La función de este análisis es mostrar que la herramienta TSeedS permite cumplir con uno de los objetivos centrales del enfoque propuesto, el cual radica en mostrar la evolución de la influenciabilidad de los usuarios. Para ello, se observaron los gráficos de posición en elSeed Set en función del tiempo provistos por la herramienta. Esto fue llevado a cabo para los distintos usuarios que pertenecieron a los diferentes conjuntos de semillas seleccionados y a modo de resumen se seleccionaron seis usuarios para realizar distintas comparaciones con los gráficos obtenidos. De manera complementaria, se tiene en cuenta la información relacionada con la cantidad de interacciones en las que se involucraron los usuarios. De esta forma, con los gráficos que evidencian la evolución y la información complementaria considerada, se analizan posibles justificaciones de las apariciones de los usuarios en los conjuntos seleccionados.

Los usuarios seleccionados son @yosoynaranjito_, @radiocable, @quetemuevas, @jcvelezuribe, @JuanyGar63 y @publico_es. Tanto @radiocable, como @quetemuevas como @jcvelezuribe aparecen en más del 85% de los Seed Set calculados. Por su parte, @yosoynaranjito_ y @publico_es se encuentran entre el 45% y 65% de los conjuntos calculados. Finalmente, el usuario @JuanyGar63 aparece aproximadamente en el 20% de los Seed Set obtenidos.

111

En primer lugar, se analiza el caso del usuario @JuanyGar63 cuya permanencia en los Seed Set seleccionados no fue muy extendida. En la Figura 5.38 se ilustra el gráfico de evolución de influencia para el usuario en cuestión.

Figura 5.38.Gráfico de Evolución de Influencia del usuario @JuanyGar63 en el caso de estudio 2.

El gráfico de la Figura 5.38 permite apreciar la breve permanencia del usuario

en los conjuntos de influyentes. Por otro lado también se puede visualizar que cuando se seleccionó el mismo la influencia alcanzada fue muy alta alcanzando un segundo puesto en el Seed Set durante unos minutos. Luego su influenciabilidad decrece hasta ubicarse en el medio del conjunto. Se puede apreciar que luego de dicha ocurrencia el usuario no vuelve a aparecer en los conjuntos seleccionados. Esto resulta interesante que sea destacado ya que normalmente los usuarios desaparecen de losSeed Set tras encontrarse en algunas de las últimas posiciones. En la Figura 5.39, se ilustra la información complementaria al gráfico, extraída de los resultados obtenidos.

112

Figura 5.39. Información complementaria del usuario

@JuanyGar63 en el caso de estudio 2. El gráfico ilustrado se condice con la información complementaria indicando

las pocas interacciones que tuvo @JuanyGar63 como usuario influyente. En segundo lugar, se analizan los usuarios @yosoynaranjito_ y @publico_es

que como se mencionó anteriormente se encuentran entre el 45% y 65% de los conjuntos calculados. La Figura 5.40 ilustra el gráfico de evolución de influencia para el primero de los usuarios en cuestión.

Figura 5.40.Gráfico de Evolución de Influencia del usuario @yosoynaranjito_ en el caso de estudio 2.

De manera similar a lo observado con el usuario anterior, el gráfico de la Figura 5.40 permite apreciar el alcance rápido de la cúspide de los Seed Set calculados por unos minutos. A diferencia del caso anterior la durabilidad en la selección de los mismos del presente usuarios es mucho mayor. Lo que sí se identifica de manera clara es el decrecimiento de la influenciabilidad del usuario

113

respecto del tiempo de forma escalonada. En la Figura 5.41, se ilustra la información complementaria al gráfico extraída de los resultados obtenidos para el usuario en cuestión.

Figura 5.41. Información complementaria del usuario

@yosoynaranjito_ en el caso de estudio 2.

La información complementaria permite apreciar que a pesar de ser mayor la cantidad de interacciones en las que fue referenciado, @yosoynaranjito_ alcanzó un valor de influencia marginal menor con respecto al usuario anterior. Sin embargo, logró un mejor posicionamiento en los Seed Set y una mayor permanencia en la selección de los mismos.

A continuación, se procede al análisis del siguiente usuario (@publico_es). En la Figura 5.42 se muestra el gráfico de evolución de influencia de dicho usuario.

Figura 5.42.Gráfico de Evolución de Influencia del usuario @publico_es en el caso de estudio 2.

114

El gráfico de la Figura 5.42 permite apreciar que la permanencia del usuario @publico_es es mayor que la de los analizados con anterioridad. De manera similar al caso anterior, se puede indicar que previo a la desaparición de los Seed Set se nota un decrecimiento en la influencia del usuario. Aunque en el presente caso, la presencia del usuario es más prolongada y su desaparición se extiende. En la Figura 5.43, se ilustra la información complementaria al gráfico extraída de los resultados obtenidos.

Figura 5.43. Información complementaria del usuario

@publico_es en el caso de estudio 2.

La Figura 5.43 muestra una leve mejoría en la cantidad de interacciones como influyente. Incluso, el valor máximo alcanzado de influencia marginal es muy similar al caso anterior. Por ende, al ser similar la información complementaria se explica su parecido en el gráfico de influenciabilidad.

En tercer lugar, se procede a analizar las tres cuentas restantes que superan el 85% de permanencia en los Seed Set calculados. En las Figuras 5.44 y 5.45 se ilustran los gráficos de los usuarios @radiocable y @quetemuevas respectivamente.

115

Figura 5.44. Gráfico de Evolución de Influencia del usuario @radiocable en el caso de estudio 2.

Figura 5.45. Gráfico de Evolución de Influencia del usuario @quetemuevas en el caso de estudio 2.

Ambos usuarios permanecen en la gran mayoría de los Seed Set

seleccionados y puede notarse una similitud en la influenciabilidad de los mismos. Ambos logran un pico alto y luego lo mantienen en el tiempo (más allá de que @quetemuevas este primero unos minutos en posiciones bajas de los Seed Set).

En las Figuras 5.46 y 5.47 respectivamente, se ilustran los datos obtenidos como información complementaria para los usuarios en cuestión.

116

Figura 5.46. Información complementaria del usuario

@radiocable en el caso de estudio 2.

Figura 5.47. Información complementaria del usuario

@quetemuevas en el caso de estudio 2.

Nuevamente pueden verse las similitudes antes supuestas en la información complementaria. Dicha información demuestra una cantidad de interacciones que los referencian muy similar y sólo diferencia en la cantidad de acciones realizadas. De hecho, este último factor es el causante de su leve menor influenciabilidad, ya que es altamente probable que los retweets del usuario @quetemuevas no estén distribuidos de igual forma para las ocho acciones realizadas.

Como dato extra a continuación se muestra el tweet publicado por @radiocable que logró tal cadena de retweets. Tweet de @radiocable: Así va el país… “Soria, recibido con abrazos y aplausos”https://t.co/tdhlRCRS9t vía @La_SER.

Como se puede apreciar la interacción apunta al descontento del usuario respecto del buen trato brindado al ex líder del PP de Canarias (en España) involucrado con una empresa offshore por los Panamá Papers. Además se puede

117

ver que hace referencia a una nota de la Cadena SER, en la que se trata dicho asunto.

Por último, se analiza el usuario @jcvelezuribe, cuyo gráfico de evolución de

influenciabilidad de ilustra en la Figura 5.48.

Figura 5.48. Gráfico de Evolución de Influencia del usuario @jcvelezuribe en el caso de estudio 2.

A diferencia de los dos usuarios anteriormente analizados, este usuario

describe un decrecimiento notorio escalonado, habiendo inicialmente logrado un pico alto de influenciabilidad de manera rápida. En la Figura 5.49 se muestra la información complementaria referida al usuario en cuestión.

Figura 5.49. Información complementaria del usuario

@jcvelezuribe en el caso de estudio 2.

118

En la Figura 5.49 se puede observar comparando con los usuarios anteriores que el usuario en cuestión es referenciado la mitad de las veces que los mismos. Esto puede indicar que tras el pico alto logrado rápidamente por @jcvelezuribe, la ganancia que dicho usuario aportaba a los Seed Set posteriores se estancó y que por ello se observa la disminución escalonada ilustrada en la Figura 5.48.

Tras el caso de estudio 2 y el análisis de los resultados obtenidos se

concluye que nuevamente la herramienta TSeedS permite lograr el objetivo central del enfoque propuesto en el presente trabajo referido al análisis de la evolución de la influencia de los usuarios.

5.4. Comparativa de Casos de Estudio

En esta sección se analizan de manera comparativa los resultados obtenidos en los casos de estudio antes desarrollados. En primer lugar se analiza la sección de Análisis de Información y luego la sección de Análisis de Resultados de dichos casos de estudio.

Bajo el Análisis de Información, se analizó el Filtrado de Interacciones que realizó la herramienta en los dos casos de estudio. En base a ello, en la Figura 5.50 se muestra un resumen de todos los resultados obtenidos, previamente analizados en las secciones 5.2.1.1 y 5.3.1.1.

Figura 5.50. Resumen del Filtrado de Interacciones para los casos de estudio 1 y 2.

En primer lugar, se observa que tras el streaming en el cual se aplica el filtro

de categoría se obtiene una mayor cantidad de interacciones en el caso de estudio 2. Esto puede deberse a la generalidad de cada categoría propuesta. Es decir, la categoría fútbol puede considerarse dentro de lo que sería la categoría deportes. Esta última puede considerarse al nivel de generalidad de la categoría política.

En segundo lugar, se observa la gran cantidad deretweets que pasan el filtro de idioma en el caso de estudio 2, en comparación con los filtrados en el caso de estudio 1. Sin embargo, tras la aplicación del filtro temporal los valores prácticamente se igualan. Esto indica que la propagación de acciones en el caso de estudio 2, se realiza con un margen temporal más amplio que el del caso de estudio 1.

119

En tercer lugar, se observa una notoria diferencia en los porcentajes totales de interacciones filtradas. En particular en el caso de estudio 2, se filtra un significativo porcentaje de interacciones. Como se explicó anteriormente, el filtrado temporal aplicado reduce drásticamente la cantidad de interacciones válidas.

Continuando el Análisis de Información, se observó la cantidad de solicitudes adicionales realizadas por la herramienta TSeedS en ambos casos de estudio. En la Figura 5.51 se muestra un resumen de los resultados obtenidos.

Figura 5.51. Resumen de las Solicitudes de Información Adicional para los casos de estudio 1 y 2.

Se observa que los valores se mantienen en brechas similares, aunque es

notorio que en el caso de estudio 1 se realizan aproximadamente mil solicitudes más que en el caso 2. Esto puede deberse a la cantidad de interacciones que pasan los filtros en los casos de estudio 1 y 2. En el caso 1, pasan los filtros aproximadamente mil interacciones más que en el caso 2.

Por último, se analiza la sección de Generación del Grafo Social de los casos de estudio desarrollados. En el caso de estudio 1 se observa que por más que transcurre el tiempo la cantidad de nodos aislados continúa siendo grande. Mientras que en el caso de estudio 2 la cantidad de nodos aislados tiende a disminuir notoriamente. Como se explicó anteriormente, la existencia de estos nodos aislados no aporta información para la determinación de los nodos más influyentes ya que para convencerlos de la realización de una acción habría que seleccionarlos en el Seed Set. Los resultados obtenidos en lo que corresponde a cantidad de aristas y nodos relacionados en ambos casos de estudios son similares.

Como se enunció previamente en la actual sección, en segundo lugar se realiza el Análisis de Resultados. Este involucra las etapas de Interpretación y Visualización de Resultados del enfoque propuesto.

Tras el análisis realizado en la sección de Variabilidad del Seed Set de los casos de estudio se observa que en ambos la cantidad de usuarios distintos seleccionados es baja. Esto indicaría que en ambos casos de estudio la variabilidad es pequeña. Además se obtienen resultados similares en lo que corresponde a cuántas semillas logran cubrir el 50% o el 75% de la totalidad de los Seed Set generados.

120

Finalmente, tras el análisis realizado en la sección de Semillas Seleccionadas se pueden apreciar los casos particulares de usuarios y la evolución de la influenciabilidad de los mismos. Es por ello, que no serán comparados estos resultados obtenidos en ambos casos de estudio.

121

6. Conclusiones En el presente trabajo se presentó un enfoque para determinar nodos

influyentes en redes sociales en tiempo real con el objetivo de analizar la evolución de la influenciabilidad de los usuarios de manera dinámica. Dicho enfoque se materializó en la herramienta TSeedS.

En la sección 6.1 se presentan las principales contribuciones aportadas por el enfoque propuesto. Por otro lado, en la sección 6.2 se enuncian ciertas limitaciones observadas a lo largo del desarrollo del enfoque en cuestión. Por último, en la sección 6.3 se presenta un conjunto de trabajos futuros para extender el enfoque propuesto y/o mejorarlo.

6.1 Contribuciones Como contribución principal, la herramienta TSeedS permite analizar de

forma dinámica la evolución de la influencia de los usuarios de la red social Twitter. Esto se logra mostrando gráficos de influenciabilidad de los usuarios influyentes en tiempo real. Cabe destacar que la herramienta actualiza la información representada en los gráficos tras una ventana temporal configurable.

Resulta importante resaltar de la investigación, que se toma como fuente de información Twitter en tiempo real. Ya que si bien hoy en día diversas aplicaciones utilizan Twitter como fuente de información no todas ofrecen resultados en tiempo real sobre lo que está ocurriendo al instante sobre dicha red.

Además, el presente enfoque permite resolver un problema de influencia que no es el que típicamente se observa en otra aplicaciones relacionadas. Es normal ver rankings o clasificación de usuarios en las redes sociales más utilizadas. Incluso existen múltiples herramientas que se dedican al análisis de usuarios influyentes estableciendo puntajes o clasificaciones en perfiles. Nótese que dichos análisis son estáticos. Mientras que la herramienta TSeedS puede, además de lo ya mencionado respecto al dinamismo de los análisis, ser utilizada con un fin relacionado al marketing viral. Usando la herramienta para determinar los usuarios más influyentes sobre una temática de interés y luego convenciendo a los mismos para maximizar la propagación de un rumor o la adquisición de un producto.

En base a los resultados obtenidos de la experimentación, se concluye que la herramienta permite realizar un análisis dinámico de la influenciabilidad de los usuarios mostrando correctamente los datos obtenidos en tiempo real. Permitiendo identificar diversos aspectos de la influenciabilidad de los usuarios influyentes. Ya que no sólo ilustra gráficos con crecimientos y decrecimientos de la influencia, sino que indica las interacciones realizadas y la ganancia marginal que aportan sobre la red minuto a minuto.

122

Los experimentos permitieron visualizar los momentos de pico de influencia de los usuarios y las interacciones relacionadas con ello. Además se pudo deducir que la mayoría de los usuarios, en los minutos previos a la desaparición del Seed Set seleccionado, describen un decrecimiento leve de su influenciabilidad. Sin embargo, también se apreciaron algunos casos en los que drásticamente los usuarios pasaban de ser muy influyentes a desaparecer del Seed Set sin indicar ningún leve decrecimiento previo de su influencia.

Por otro lado, los experimentos permitieron identificar que en algunas temáticas el margen temporal de propagación es más amplio. Esto se pudo identificar tras notar que más de la mitad de los retweet escuchados sobre política, no pasaron el filtro temporal.

6.2 Limitaciones La primera desventaja que se identificó en la herramienta desarrollada son

las limitaciones que establece la versión gratuita de la API de Twitter. Ésta limita la cantidad de interacciones escuchadas por el streaming trabajando sólo con un porcentaje de la realidad de la red en cada instante. Esto puede traer problemas en los resultados ya que puede suceder que gran cantidad de interacciones relacionadas con un usuario no sean escuchadas y por ello no se lo denomine influyente. O el caso contrario, en el que justo se escuchen todas las interacciones de un usuario y éste termine marcando significativas diferencias sobre los demás cuando en realidad no es así. Además de los límites que establece la API en cuanto a la captura de información también posee límites sobre las cantidad de peticiones que se le pueden realizar. Esto último, muchas veces no nos permite completar la información deseada y por ende, el análisis que realiza la herramienta puede que se encuentre desfasado de lo que ocurre realmente.

La segunda desventaja radica en la utilización de una herramienta externa para el cálculo los usuarios influyentes. Ya que esto conlleva a no poder analizar ciertos aspectos que pueden resultar de interés sobre el modelo de propagación que se utiliza (Credit Distribution Model).

Otra limitación encontrada corresponde a que al no poseer persistencia la herramienta (una base de datos por ejemplo), si se deseara realizar una comparación sobre una brecha demasiado extensa de tiempo (semanas, meses) se podría hacer costoso el mantenimiento de las estructuras internas y el volcado de la información en archivos.

123

6.3 Trabajos a Futuro El proceso de desarrollo del presente trabajo, tanto la descripción del enfoque

como la implementación de la herramienta, evidenció posibles investigaciones futuras y mejoras sobre TSeedS. A continuación se explican algunas de ellas. Archivos Incrementales

Respecto a las mejoras que se le pueden realizar a la herramienta a nivel interno, se pensó en que el volcado de información se realice de manera incremental evitando así muchas operaciones de entrada/salida que pueden resultar costosas. Persistencia

Se analizó la utilización de persistencia de manera que en caso de querer realizar comparaciones con extensas brechas temporales no resulte costoso el mantenimiento de estructuras internas. Además la persistencia permitiría contar con mayor cantidad de información sobre los usuarios influyentes, de forma que se podrían comparar los resultados obtenidos en distintos momentos y no sólo en tiempo real. Una versión inicial se hizo para la etapa de la experimentación aunque esta podría ser extendida y mejorada. Vistas conjuntas de los resultados

Sería interesante poder ver los resultados obtenidos de diversos usuarios bajo un mismo gráfico. De esta forma, los resultados podrían ser comparados más fácilmente. Visualización de estadísticas complementarias

Si bien el enfoque se centra en la influenciabilidad de los usuarios también sería importante, al igual que se realizó en los experimentos( donde se explicó que se modificó la herramienta para obtener mayor cantidad de información acerca del comportamiento de la misma) poder ver estadísticas relacionadas con la red que se genera. Es decir, poder visualizar gráficos que muestren la evolución del grafo social en el tiempo. Lo mismo podría realizarse sobre las interacciones filtradas y la justificación de su rechazo.

También sería interesante obtener estadísticas relacionadas con la variabilidad de los Seed Set seleccionados o la calidad de los mismos en el tiempo. Exportación de información

Para poder realizar un análisis más profundos sobre los usuarios, tener la posibilidad de exportar la información resultaría de gran utilidad. De manera que, por ejemplo, se pudiera ver el resultado obtenido por los usuarios (influyentes o no) para

124

todos los Seed Set recalculados. También sería muy útil cuando se usa durante un tiempo muy extenso la herramienta. Determinación automática de idioma

La determinación automática del idioma permitiría eliminar los filtros de lenguaje que se realizan actualmente en la herramienta. Con esto se permite analizar tweets escritos en español, aunque en la cuenta del usuario figure idioma inglés. Además si se clasificara por idioma, se podría analizar la influenciabilidad del usuario tanto en su idioma (que normalmente acusa una determinada geolocalización) como a nivel mundial. Clasificación de Texto

A modo de investigaciones futuras, se propone el agregado de clasificadores de texto para analizar en mayor profundidad las temáticas y la relación de los usuarios con las mismas. Es decir, poder analizar qué contenido (textual, palabras) se encuentra en las interacciones más propagadas y determinar si hay palabras que ayudan a influenciar a los usuarios. Por otro lado, poder determinar con qué contenido un usuario es más referenciado.

También se podría identificar temáticas dentro de las temáticas, de modo de establecer por ejemplo si las publicaciones relacionadas con el fútbol español se propagan en mayor medida que las relacionadas con el fútbol alemán. Múltiples Fuentes de Información

Otra de las investigaciones que se propone es una ampliación de la herramienta, de modo que permita la conexión de múltiples tipos de redes sociales. Es decir, que la fuente de información de la herramienta no se limite a Twitter sino que sea como una plantilla en la que pueda asociarse diversas redes sociales. En este punto es necesario determinar qué se determinan acciones en la red para analizar su propagación. Por ejemplo, si la red en cuestión fuese Facebook, las acciones podrían ser compartir una publicación o contestar un comentario.

125

Referencias [1] Francesco Bonchi, “Influence Propagation in Social Networks: A Data Mining

Perspective”, Barcelona, Spain, Dec 2011.

[2] N. E. Friedkin, “A Structural Theory of Social Influence”, Cambridge University

Press, 1998.

[3] David Kempe, Jon Kleinberg, and Éva Tardos, “Maximizing the Spread of

Influence through a Social Network”, Dept. of Computer Science Cornell University,

Ithaca NY.

[4] Amit Goyal, Francesco Bonchi, and Laks V. S. Lakshmanan, “A Data­Based

Approach to Social Influence Maximization”, University of British Columbia,

Vancouver, Canada, 2011.

[5] Benjamin Doerr, Mahmoud Fouz, and Tobias Friedrich, “Why Rumors Spread

Fast in Social Networks”, Max­Planck­Institut für Informatik and Universität des

Saarlandes, Saarbrücken, Germany, 2012.

[6] P. Beaumont, “The truth about twitter, facebook and the uprisings in the arab

world”, Feb 2011.

[7] Isabel Ponce, “Redes Sociales”, Abril 2012. Link:

http://recursostic.educacion.es/observatorio/web/es/internet/web­20/1043­redes­soci

ales

[8] Twitter ­ https://twitter.com/

[9] S. Johnson, “How Twitter will change the way we live”, Time Magazine, 2009.

[10] BigBangNews ­ http://www.bigbangnews.com/

[11] E. Veiszadeh, “Twitter freedom’s only link in Iran”, The Australian, Junio 2009.

Link:

http://www.theaustralian.com.au/news/twitter­freedoms­only­link­in­iran/story­e6frg6n

6­1225736033533

126

[12] A. Acar, Y. Muraki, “Twitter for crisis communication: lessons learned from

Japan’s tsunami disaster”, International Journal Web Based Communities, 2011.

Link: http://www.inderscienceonline.com/doi/pdf/10.1504/IJWBC.2011.041206

[13] Robert Mackey, “China’s Great Firewall Blocks Twitter”, Junio 2009. Link:

http://thelede.blogs.nytimes.com/2009/06/02/chinas­great­firewall­blocks­twitter

[14] Real Academia Española. Link: http://dle.rae.es/?id=LXZPs0x

[15] J. Weng, E.P. Lim, J. Jiang, and Q. He, “Twitterrank: finding topic sensitive

influential twitterers” in Proc. of the Third Int. Conf. on Web Search and Web Data

Mining, 2010.

[16] E. Bakshy, J. M. Hofman, W. A. Mason and D. J. Watts, “Everyone’s an

influencer: quantifying influence on twitter” in Proc. of the Forth Int. Conf. on Web

Search and Web Data Mining, 2011.

[17] C. Castillo, M. Mendoza and B. Poblete, “Information credibility on twitter” in

Proc. of the 20th Int. Conf. on World Wide Web, 2011.

[18] D. M. Romero, B. Meeder and J. M. Kleinberg,“Differences in the mechanics of

information diffusion across topics: idioms, political hashtags, and complex contagion

on twitter” in Proc. of the 20th Int. Conf. on World Wide Web, 2011.

[19] J. Wortman, “Viral marketing and the diffusion of trends on social networks”,

University of Pennsylvania, Technical Report MS­IS­08­19, May 2008. Link:

http://repository.upenn.edu/cgi/viewcontent.cgi?article=1924&context=cis_reports

[20] S. Morris, “Contagion”, Review of Economic Studies 67, 2000.

[21] J. Goldenberg, B. Libai and E. Muller,“Talk of the Network: A Complex Systems

Look at the Underlying Process of Word­of­Mouth”, Marketing Letters, 2001.

[22] J. Goldenberg, B. Libai and E. Muller, “Using Complex Systems Analysis to

Advance Marketing Theory Development”, Academy of Marketing Science Review,

2001.

[23] M. Richardson and P. Domingos, “Mining knowledge­sharing sites for viral

marketing” in Proc. of the Eighth ACM SIGKDD Int. Conf. on Knowledge Discovery

and Data Mining (KDD’02), 2002.

127

[24] P. Domingos and M. Richardson, “Mining the network value of customers” in

Proc. of the Seventh ACM SIGKDD Int. Conf. on Knowledge Discovery and Data

Mining (KDD’01), 2001.

[25] D. Easley and J. Kleinberg, “Networks, Crowds, and Markets: Reasoning About

a Highly Connected World”, Chapter 19, Cambridge University Press, 2010. Link:

https://www.cs.cornell.edu/home/kleinber/networks­book/networks­book.pdf

[26] X. Song, Y. Chi, K. Hino and B. L. Tseng, “Information flow modeling based on

diffusion rate for prediction and ranking,” in Proc. of the 16th Int. Conf. on World

Wide Web, 2007. Link: http://www2007.wwwconference.org/papers/paper664.pdf

[27] D. Ienco, F. Bonchi, and C. Castillo, “The meme ranking problem: Maximizing

microblogging virality” in Proc. of the SIASP workshop at ICDM’10, 2010.

[28] A. Anagnostopoulos, R. Kumar and M. Mahdian, “Influence and correlation in

social networks”, in Proc. of the 14th ACM SIGKDD Int. Conf. on Knowledge

Discovery and Data Mining (KDD), 2008.

[29] D. J. Crandall, D. Cosley, D. P. Huttenlocher, J. M. Kleinberg, and S. Suri,

“Feedback effects between similarity and social influence in online communities”, in

Proc. of the 14th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining

(KDD), 2008.

[30] S. Aral, L. Muchnik and A. Sundararajan, “Distinguishing influence­based

contagion from homophily­driven diffusion in dynamic networks”, Proc. of the

National Academy of Sciences, vol. 106, no. 51, pp. 21 544–21 549, 2009.

[31] T. L. Fond and J. Neville, “Randomization tests for distinguishing social

influence and homophily effects”, in Proc. of the 19th Int. Conf. on World Wide Web,

2010.

[32] N. A. Christakis and J. H. Fowler, “The spread of obesity in a large social

network over 32 years”, The New England Journal of Medicine, vol. 357(4), pp.

370–379, 2007.

[33] R. Lyons, “The spread of evidence­poor medicine via flawed social network

analysis”, Statistics, Politics, and Policy, vol. 2, no. 1, 2011.

128

[34] Chellapa and Jain, “Markov Random Fields: Theory and Application”, Academic

Press, 1993.

[35] E. Berger, “Dynamic Monopolies of Constant Size”, Journal of Combinatorial

Theory Series B 83, 2001.

[36] S. Morris. Contagion, “Review of Economic Studies”, 2000.

[37] D. Peleg, “Local Majority Voting, Small Coalitions, and Controlling Monopolies in

Graphs: A Review”, 3rd Colloq. on Structural Information and Communication, 1996.

[38] S. Wasserman and K. Faust, "Social Network Analysis", Cambridge University

Press, 1994.

[39] R. Durrett, “Lecture Notes on Particle Systems and Percolation”, Wadsworth

Publishing, 1988.

[40] T .M. Liggett, “Interacting Particle Systems”, Springer, 1985.

[41] W. Chen, C. Wang, and Y. Wang, “Scalable Influence Maximization for

Prevalent Viral Marketing in Large­Scale Social Networks”, in KDD’10, 2010.

[42] K. Jung, W. Heo, and W. Chen, “IRIE: Scalable and robust influence

maximization in social networks” in arXiv, 2012.

[43] M. Jamali and M. Ester, “A matrix factorization technique with trust propagation

for recommendation in social networks”, pp 135–142. In RecSys, 2010.

[44] A. Goyal, F. Bonchi, and L. V. S. Lakshmanan, “Learning influence probabilities

in social networks”, pp. 241–250, In WSDM, 2010.

[45] J. Leskovec, “Cost­effective outbreak detection in networks”, pp 420–429, In

KDD’07, 2007.

[46] Klout ­ https://klout.com/home

[47] Audiense https://www.audiense.com/

[48] Kred ­ http://home.kred/

[49] Kred, estudio realizado en 2011, Sección Influence en: http://home.kred/rules/

[50] LinkedIn Pulse integrada en LinkedIn ­ https://www.linkedin.com/

[51] CircleCount ­ http://www.circlecount.com/

129

[52] CircleScope ­ http://circloscope.com/

[53] Booshaka ­ https://www.booshaka.com/

[54] Quantico ­ http://www.quanticotrends.com/

[55] FollowerWonk ­ https://moz.com/followerwonk/

[56] Klear ­ http://klear.com/

[57] Topsy ­ http://topsy.com/

130