Sistema multiagente para el análisis de interacciones entre usuarios en medios sociales

TESIS DE M ´ ASTER Sistema multiagente para el an´ alisis de interacciones entre usuarios en medios sociales Author: Carla Mart´ ınez Poveda Directores: Dr. Vicent Botti Navarro y Dra. Elena del Val Noguera Departamento de Sistemas Inform´ aticos y Computaci´ on, Universidad Polit´ ecnica de Valencia, Camino de Vera, s/n 46022 Valencia, Spain Diciembre de 2016 ´ Indice 1 Introducci´ on 1 1.1 Motivaci´ on .................................... 1 1.2 Objetivos ..................................... 2 1.3 Organizaci´ ondeldocumento ........................... 3 2 Estado del arte 5 2.1 Introducci´ on.................................... 5 2.2 Agentes Inteligentes y Sistemas Multiagente . . . . . . . . . . . . . . . . . . . 5 2.3 Redescomplejas ................................. 8 2.3.1 Tiposderedes .............................. 9 2.3.2 Modelosdered.............................. 11 2.4 Redessocialesonline............................... 15 2.5 An´ alisis de Redes Sociales Online . . . . . . . . . . . . . . . . . . . . . . . . 17 2.6 Conclusiones ................................... 19 3 Dise˜ no del SMA 21 3.1 Introducci´ on.................................... 21 3.2 Modelo de Organizaci´ onVirtual ......................... 22 3.3 Dimensi´ onestructural............................... 22 3.4 Dimensi´ onfuncional ............................... 24 3.5 Dimensi´ on din´ amica ............................... 25 3.6 Conclusiones ................................... 26 4 Framework 27 4.1 Visi´ onglobal ................................... 27 4.2 Plataformayagentes ............................... 29 4.2.1 Rol Monitor: agentes AgentTweet yNeo4jAgent ............. 29 4.2.2 Rol Analyzer: agentes QueryNeo4jAgent yGraphAnalyzerAgent . . . . 32 4.2.3 Rol User: agente VisualAgent ...................... 34 4.3 Protocolos de interacci´ on............................. 34 4.4 Conclusiones ................................... 38 I 5 Caso de Estudio 39 5.1 Introducci´ on.................................... 39 5.2 Medidasaniveldered .............................. 40 5.3 Medidasaniveldenodo ............................. 42 5.4 An´ alisisdeeventos ................................ 45 5.4.1 Evento #MuereBarber´ aARV....................... 45 5.4.2 Evento #ChampionsLeague . . . . . . . . . . . . . . . . . . . . . . . 48 5.4.3 Evento #pesadillazamora . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.5 Conclusiones ................................... 54 6 Conclusiones y trabajo futuro 57 6.1 Conclusiones ................................... 57 6.2 TrabajoFuturo .................................. 58 6.3 Publicaciones ................................... 59 Bibliography 61 II Lista de Figuras 2.1 Ejemplos de tipos de redes seg´ un el tipo de informaci´ on considerada. Red social: citas entre alumnos de un instituto [36]. Red biol´ ogica: relaciones entre enfermedades a partir de los genes que tienen en com´ un [12]. Red tecnol´ ogica: trayectos entre aeropuertos [21]. Red de informaci´ on: citaci´ on de art´ ıculos [3]. 11 2.2 Proceso aleatorio de redirecci´ on de enlaces n=20, k=4 siguiendo el modelo propuestoporWatts[50].............................. 12 2.3 Estructura de Kleinberg. La estructura inicial es una cuadr´ ıcula regular. Las conexiones aleatorias entre dos nodos distantes se establecen con una probabilidad inversamente proporcional al cuadrado de la distancia entre ellos. . . . . 13 2.4 ´ Arbol de distancias sociales jer´ arquicas presentado por Watts [49] y Kleinberg [28]. Los individuos se agrupan considerando caracter´ ısticas sociales: trabajo, ubicaci´ on geogr´ afica o intereses. En el ejemplo, lindica el n´ umero de niveles de la jerarqu´ ıa (l= 4), bes el factor de ramificaci´ on (b= 2) y xindica la separaci´ on entre dos individuos. . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.1 Dimensi´ on Estructural del SMA propuesto. Esta dimensi´ on proporciona una descripci´ on de los elementos que componen el sistema, es decir, qu´ e roles y qu´ e agentes forman parte de la organizaci´ on virtual. . . . . . . . . . . . . . . 23 3.2 Dimensi´ on Funcional del SMA propuesto. Esta dimensi´ on proporciona informaci´ on sobre los servicios proporcionados por los agentes que forman parte delsistema. .................................... 24 3.3 Dimensi´ on din´ amica del SMA propuesto. Muestra las interacciones entre las entidades que forman parte del sistema para realizar la recogida y almacenamiento de informaci´ on asociada a un evento en una red social online (FollowEvent)...................................... 25 3.4 Dimensi´ on din´ amica del SMA propuesto. Muestra las interacciones entre las entidades que forman parte del sistema para realizar el an´ alisis de la red de interacciones generada a partir de la informaci´ on recogida de un evento en una red social online ( RequestAnalysis) ....................... 26 4.1 Estructura general del sistema. Indica la direcci´ on de los flujos de interacci´ on y/o conversaci´ on entre los diferentes agentes del sistema. . . . . . . . . . . . . 29 III 4.2 Ejemplo de c´ omo se almacenar´ ıan los distintos tipos de mensajes de interacci´ on asociados a un evento utilizando el modelo propuesto para almacenar la informaci´ on en Neo4j. Los nodos del grafo representan las entidades del modelo. Las entidades consideradas en el modelo son: eventos (rojo), interacciones (verde), usuarios (azul). Los enlaces del grafo representan los tipos de relaciones que hay en el modelo de datos (i.e., creates, mention, has hashtag, y creates). Las relaciones que se muestran en el grafo son las generadas al insertar un tweet donde no se menciona a ning´ un usuario (rosa), un tweet que contiene una menci´ on (morado), un tweet que es un reply-to (amarillo), y una menci´ on a varios usuarios (mention). En la parte inferior se muestran los cuatro mensajes (tweets) insertados en la base de datos. . . . . . . . . . . . . . . . . 31 4.3 Red de interacciones generada a partir de la actividad de los usuarios en Twitter asociadaaunevento. ............................... 33 4.4 Diagrama de secuencia para el escenario FollowEvent. Describe las interacciones entre los agentes VisualAgent,ManagerAgent,AgentTweet yNeo4jAgent. .......................................... 35 4.5 Diagrama de secuencia para el escenario RequestAnalysis. Describe las interacciones entre los agentes VisualAgent,ManagerAgent,QueryNeo4jAgent y GraphAnalyzerAgent. .............................. 36 5.1 Evoluci´ on de las propiedades estructurales a nivel de red: longitud del camino medio, grado medio de conexi´ on y di´ ametro de la red. Evento #MuereBarber´ aARV ..................................... 45 5.2 Evoluci´ on de las propiedades estructurales a nivel de red: modularidad. Evento #MuereBarber´ aARV ............................... 46 5.3 Evoluci´ on de las propiedades estructurales a nivel de red: densidad. Evento #MuereBarber´ aARV ............................... 46 5.4 Evoluci´ on de las propiedades estructurales a nivel de red: n´ umero de nodos, n´ umero de ejes y componente gigante. Evento #MuereBarber´ aARV . . . . . . 47 5.5 Evoluci´ on de las propiedades estructurales a nivel de red: longitud del camino medio, grado medio de conexi´ on y di´ ametro de la red. Evento #ChampionsLeague..................................... 49 5.6 Evoluci´ on de las propiedades estructurales a nivel de red: modularidad. Evento #ChampionsLeague................................ 49 5.7 Evoluci´ on de las propiedades estructurales a nivel de red: densidad. Evento #ChampionsLeague................................ 50 5.8 Evoluci´ on de las propiedades estructurales a nivel de red: n´ umero de nodos, n´ umero de ejes y componente gigante. Evento #ChampionsLeague . . . . . . . 50 5.9 Evoluci´ on de las propiedades estructurales a nivel de red: longitud del camino medio, grado medio de conexi´ on y di´ ametro de la red. Evento #pesadillazamora 52 5.10 Evoluci´ on de las propiedades estructurales a nivel de red: modularidad. Evento #pesadillazamora ................................. 53 5.11 Evoluci´ on de las propiedades estructurales a nivel de red: densidad. Evento #pesadillazamora ................................. 53 IV 5.12 Evoluci´ on de las propiedades estructurales a nivel de red: n´ umero de nodos, n´ umero de ejes y componente gigante. Evento #pesadillazamora . . . . . . . . 54 V Lista de Tablas 2.1 Comparativa de las caracter´ ısticas principales de trabajos relacionados con el an´ alisis de redes sociales online. Se han considerado las siguientes caracter´ ısticas: qu´ e fuentes de informaci´ on se han utilizado para generar la red, qu´ e tipo de informaci´ on extra´ ıda de las redes analizan, qu´ e tipo de relaciones han considerado para generar las redes, qu´ e medidas de an´ alisis se tienen en cuenta, cu´ ando se realiza el an´ alisis, y qu´ e tipo de framework ofrecen. . . . . . 20 4.1 Resumen de la implementaci´ on de los agentes que forman parte del framework propuesto. Se describe para cada agente del sistema: los roles que juega, los objetivos en los que participa, los servicios que ofrece, los agentes que crea, y los agentes con los que interact´ ua. ........................ 37 5.1 Evoluci´ on de las propiedades estructurales a nivel de nodo durante el evento #MuereBarber´ aARV. Indica los 5 perfiles que tienen valores de centralidad m´ as altos teniendo en cuenta distintos criterios de centralidad. . . . . . . . . . . . 48 5.2 Evoluci´ on de las propiedades estructurales a nivel de nodo: indica un top 5 de los principales roles que tienen lugar durante el evento #ChampionsLeague. . . 51 5.3 Evoluci´ on de las propiedades estructurales a nivel de nodo: indica un top 5 de los principales roles que tienen lugar durante el evento #pesadillazamora. . . . 54 VI CAP´ ITULO 1 Introducci´ on 1.1 Motivaci´ on........................... 1 1.2 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Organizaci´ on del documento . . . . . . . . . . . . . . 3 1.1 Motivaci´ on En los ´ ultimos a˜ nos, la forma en la que las personas se comunican est´ a cambiando. Las redes sociales online como Facebook, Linkedin o Twitter han supuesto una evoluci´ on significativa en la forma de generar y percibir la informaci´ on. Cada vez m´ as personas hacen uso de ellas y cualquiera puede compartir opiniones, difundir ideas, entablar amistades y mantenerse actualizado del mundo que nos rodea. Seg´ un una encuesta del portal Eurostat [18], durante el pasado a˜ no en 28 pa´ ıses de la UE, cerca del 50% de los usuarios de entre 16 y 74 a˜ nos usaban internet para conectarse a redes sociales, sugiriendo un aumento de uso en ´ estas en los pr´ oximos a˜ nos. Teniendo en cuenta estos datos, resulta relevante el an´ alisis de la gran cantidad de informaci´ on generada por estas redes sociales online para poder entender como se comportan sus usuarios en unas condiciones y circunstancias determinadas. Los mensajes y las interacciones entre usuarios en redes sociales online dejan una huella digital, siendo posible analizar la informaci´ on que contienen e incluso generar nueva informaci´ on. ´ Esta informaci´ on puede ser utilizada para analizar el comportamiento de los usuarios durante un evento y de qu´ e forma se propaga la informaci´ on dentro de las redes sociales online. Para facilitar la tarea, es necesario hacer uso de herramientas que recuperen, procesen y analicen dicha 1 82.3. Redes complejas tanto la perspectiva individual y organizacional asi como su adaptaci´ on a los cambios que suceden en el entorno. La propuesta de este trabajo intenta resolver el problema de la recogida, procesado y an´ alisis de informaci´ on mediante el dise˜ no y desarrollo de sistema multiagente donde cada uno de los agentes tiene un objetivo(s) individual(es) pero necesitan cooperar entre ellos para lograr el objetivo de la organizaci´ on. 2.3 Redes complejas El ´ area de Redes Complejas est´ a centrada en el estudio de la redes y que se basa en trabajos previos en el ´ area de la teor´ ıa de grafos. Sin embargo, el ´ area de Redes Complejas se diferencia de la visi´ on m´ as tradicional de la teor´ ıa de grafos en los siguientes aspectos [37]: 1. ´ Esta se centra en el estudio de las propiedades de redes, no s´ olo desde un punto de vista te´ orico, sino tambi´ en desde un punto de vista experimental. Las redes que se analizan emergen de una manera natural en el mundo real, evolucionando de una manera no supervisada y descentralizada (p. ej. World Wide Web, redes de transporte, redes de energ´ ıa, redes econ´ omicas, colaboraciones cient´ ıficas). 2. Las redes en el ´ area de Redes Complejas se entienden, no s´ olo como la topolog´ ıa de sistemas, sino tambi´ en como un marco donde las entidades que forman parte de esas topolog´ ıa interact´ uan [15]. 3. En la teor´ ıa de grafos, las redes se asum´ ıan est´ aticas, sin embargo, en trabajos recientes en el ´ area de Redes Complejas se ha tenido en cuenta la evoluci´ on de las redes respecto al tiempo de acuerdo a reglas din´ amicas. Una de las primeras aplicaciones conocidas al uso de las redes hace referencia a Euler y el problema de los puentes de K¨ onigsberg, cuyo planteamiento dio origen a la Teor´ ıa de Grafos tal y como la conocemos hoy en d´ ıa. Sin embargo, el concepto de Redes Complejas no se estableci´ o hasta finales de los a˜ nos 50 cuando dos matem´ aticos, Erd¨ os y R´ enyi, hicieron un gran avance en la teor´ ıa matem´ atica cl´ asica de grafos que revolucionar´ ıa la forma en que se pueden modelar estos problemas. Estos dos matem´ aticos describieron una red con una topolog´ ıa compleja por medio de un grafo aleatorio, estableciendo de esta manera los fundamentos de la teor´ ıa de redes aleatorias. Durante los ´ ultimos a˜ nos, el estudio de redes ha pasado del enfoque de an´ alisis de peque˜ nas redes simples, sus propiedades y las propiedades de sus nodos y enlaces 2. Estado del arte 9 a la consideraci´ on de propiedades estad´ ısticas de redes a gran escala. Este nuevo enfoque ha sido impulsado por la disponibilidad de computadoras y redes de comunicaci´ on que permiten analizar datos en una escala mucho mayor de lo que era posible. Ahora no es raro ver estudios donde se analizan redes con millones o incluso miles de millones de nodos. Una red es considerada una estructura compuesta por un conjunto de nodos yenlaces. Los nodos indican elementos que componen la red y los enlaces indican las conexiones que existen entre esos nodos. Los ejemplos de redes en contextos reales incluyen Internet, World Wide Web, redes sociales de conocidos u otras conexiones entre individuos, organizaciones, redes metab´ olicas, redes alimenticias, redes de citas entre art´ ıculos y muchas otras. La ubicuidad de las redes complejas (el hecho de encontrar caracter´ ısticas similares en muchas ´ areas de conocimiento) ha establecido un conjunto de problemas de investigaci´ on en diversos sectores. Es un hecho afirmar que las redes han sido utilizadas a lo largo de los a˜ nos para denotar relaciones entre elementos y de esta forma estudiar su comportamiento y evoluci´ on. ´ Esto ha supuesto que sean elementos muy estudiados en ´ ambitos como las Matem´ aticas y las Ciencias Sociales. 2.3.1 Tipos de redes Un conjunto de nodos unidos por enlaces es la versi´ on m´ as simple de red. Hay muchas maneras en que las redes pueden ser m´ as complejas que esto. Por ejemplo, puede haber m´ as de un tipo diferente de nodo en una red, o m´ as de un tipo diferente de enlace. Los nodos y/o los enlaces pueden tener una variedad de propiedades, num´ ericas o de otro tipo, asociadas con ellos. Tomando como ejemplo de una red social de personas, los v´ ertices pueden representar hombres o mujeres, personas de diferentes nacionalidades, lugares, edades, ingresos, o muchas otras cosas. Los enlaces pueden representar la amistad, pero tambi´ en pueden representar similaridad, o conocimiento o proximidad geogr´ afica. Tambi´ en pueden llevar asociados pesos indicando el nivel de conocimiento que tiene una persona con la otra. Teniendo en cuenta el tipo de sistema y los datos a representar, las redes se pueden clasificar en varios grupos: redes sociales, redes de informaci´ on, redes tecnol´ ogicas, y redes biol´ ogicas [38] (ver Figura 2.1). A continuaci´ on describimos cada uno de estos grupos de redes. Redes sociales. Una red social es un conjunto de personas o grupos de personas con alg´ un patr´ on de conexi´ on o interacci´ on entre ellos. Los patrones de amistad entre individuos, las relaciones comerciales entre empresas, son todo ejemplos de redes que se han estudiado en el 10 2.3. Redes complejas pasado. Uno de los experimentos m´ as conocidos es el de los “mundos peque˜ nos” realizado por Milgram [47]. El experimento ten´ ıa como objetivo determinar la distribuci´ on de longitudes de trayecto en una red de conocidos. Para ello pidi´ o a los individuos de la red pasar una carta a cada uno de sus conocidos hasta que alcanzara al destinatario. La mayor´ ıa de las cartas del experimento se perdieron, pero una cuarta parte de las cartas alcanz´ o el objetivo y pas´ o en promedio por las manos de aproximadamente seis personas. Este experimento fue el origen del concepto popular de “Seis grados de separaci´ on”. Dentro de la categor´ ıa de redes sociales se encuentran las redes de afiliaci´ on en las que los grupos/individuos son los nodos y los enlaces son colaboraciones de un tipo u otro entre ellos. Un ejemplo cl´ asico de este tipo de red es la red de colaboraci´ on de actores cinematogr´ aficos. Otra fuente de datos fiables para la generaci´ on de redes de colaboraci´ on son los registros de comunicaci´ on. Por ejemplo, se podr´ ıa construir una red en el que cada enlace (dirigido) entre dos personas representaba una carta/email o paquete enviado por correo de uno a otro. Los autores Ebel, Mielsch y Bornholdt [16] reconstruyeron el patr´ on de comunicaciones por correo electr´ onico entre cinco mil estudiantes en la Universidad de Kiel a trav´ es de los registros almacenados por los servidores de correo electr´ onico. En esta red los nodos representan las direcciones de correo y los enlaces dirigidos representan un mensaje que pasa de una direcci´ on a otra. Redes de informaci´ on. Las redes de informaci´ on tambi´ en son denominadas en algunos contextos como “redes de conocimiento”. El cl´ asico ejemplo de una red de informaci´ on es la red de citas entre art´ ıculos acad´ emicos [17]. La mayor´ ıa de los art´ ıculos citan trabajos previos de otros sobre temas relacionados. Estas citas forman una red en la que los nodos son art´ ıculos y un enlaces dirigidos van de un art´ ıculo A al art´ ıculo B indicando que A cita a B. La estructura de la red refleja la estructura de la informaci´ on almacenada en sus nodos. Otro ejemplo muy importante de una red de informaci´ on es el World Wide Web, que es una red de p´ aginas Web que contienen informaci´ on, unidas entre s´ ı por hiperv´ ınculos de una p´ agina a otra [25]. Redes tecnol´ ogicas. Las redes tecnol´ ogicas son aquellas que han sido dise˜ nadas por el hombre para la distribuci´ on de recursos como pueden ser la electricidad o la informaci´ on. El caso de la red el´ ectrica es un buen ejemplo [40]. Otras redes de distribuci´ on que han sido estudiadas incluyen la red de rutas de l´ ıneas a´ ereas [51] y redes de carreteras, ferrocarriles [39] y tr´ afico peatonal [14]. La red telef´ onica y las redes de distribuci´ on tales como las utilizados por la oficina de correos o empresas de entrega de paqueter´ ıa tambi´ en entrar´ ıan en esta categor´ ıa general. Otra red tecnol´ ogica muy estudiada es Internet, es decir, la red de conexiones f´ ısicas 2. Estado del arte 11 Figura 2.1: Ejemplos de tipos de redes seg´ un el tipo de informaci´ on considerada. Red social: citas entre alumnos de un instituto [36]. Red biol´ ogica: relaciones entre enfermedades a partir de los genes que tienen en com´ un [12]. Red tecnol´ ogica: trayectos entre aeropuertos [21]. Red de informaci´ on: citaci´ on de art´ ıculos [3]. entre computadoras. Redes biol´ ogicas. Los sistemas biol´ ogicos tambi´ en pueden representarse en forma de redes. Las redes de reacciones metab´ olicas, las redes gen´ eticas, los ecosistemas y cadenas tr´ oficas, las redes neuronales o las vasculares son algunos de los ejemplos de redes biol´ ogicas analizadas desde la perspectiva de la teor´ ıa de redes. En el caso de las redes alimentarias, los nodos representan especies y los enlaces relacionan cada uno de esos nodos entre s´ ı. El an´ alisis del grado de salida y del grado de entrada de este tipo de redes posibilita la extracci´ on de la complejidad e interconexi´ on entre las distintas comunidades naturales [42]. 2.3.2 Modelos de red Se han propuesto varios modelos basados en funciones matem´ aticas para la generaci´ on de determinadas estructuras en redes reales. Estos modelos intentan reflejar c´ omo se establecen los v´ ınculos entre los individuos de la red. En esta secci´ on describimos dos de los modelos m´ as importantes: small-world omundo peque˜ no yscale-free. 12 2.3. Redes complejas Figura 2.2: Proceso aleatorio de redirecci´ on de enlaces n=20, k=4 siguiendo el modelo propuesto por Watts [50]. Las redes de small-world se caracterizan por tener un alto n´ umero de enlaces entre nodos cercanos y unos pocos enlaces que conectan nodos que se encuentran distantes. Esta estructura tiene dos caracter´ ısticas principales: coeficiente de agrupamiento alto y trayectos cortos. El alto coeficiente de agrupamiento refleja que los vecinos de un nodo son tambi´ en vecinos entre ellos (esto tambi´ en se conoce comunmente con la descripci´ on de los amigos de mis amigos son tambi´ en mis amigos). La longitud corta de trayectorias se obtiene a trav´ es de las conexiones entre nodos que se encuentran distantes. Esta propiedad est´ a relacionada con el di´ ametro de la red. El di´ ametro en las redes de mundo peque˜ no es exponencialmente menor que el tama˜ no de la red y puede ser limitado a log n, donde nes el n´ umero de nodos. Este hecho hace que entre dos nodos en la red, por lo general, exista un camino corto. Existen varios modelos que utilizan mecanismos aleatorios para la generaci´ on de propiedades de mundo peque˜ no. Podemos clasificar los modelos dependiendo de la estructura subyacente utilizada como base del modelo: •Modelos rejilla-anillo: tienen una estructura regular (anillo, celos´ ıa o rejilla) donde se modifica alterando al azar algunos de los enlaces existentes o a˜ nadiendo nuevos para obtener caracter´ ısticas del mundo peque˜ no [29, 50]. •Modelos jer´ arquicos: son m´ as realistas que los modelos regulares. En el proceso de generaci´ on, en lugar de utilizar una estructura regular (celos´ ıa o anillo), se utilizan estructuras jer´ arquicas que reflejan la estructura organizativa de un determinado dominio. •Grid y modelos jer´ arquicos: toma caracter´ ısticas de los modelos anteriores para construir la red. Watts y Strogatz [50] proponen un m´ etodo para construir una red de mundo peque˜ no que 2. Estado del arte 13 !"#$ %$ &'( )*#+,'- 5×5,'.."/* &0( 1,*"20*-#34 4.-+/.+-* 562'7"#'0,* 2*.86-94 8".: n=5;p=1'2< q=2 !"#$% &'(#) *+$ ,*$,(-& *. !"#$%&'(/ 0'()(.*)(1 &'( -)*232#4#&5 *. 3 )*+)(* $(#%'2*) 2(#$% ,'*"($ )3&'() &'3$ 3 ,-*$.(* *$( #" '#%'()1 &'#" 6#"&3$,( 2(#$% 3 %($()34 ,*$,(-&1 $*& 7!"& 3 8(&)#, ,)#&()#3/ 0+* 6#..()($& 3--)*3,'(" ,3$ 2( !"(69 +( ,3$ &)5 &* )(-4#,3&( &'( 3,&!34 "&)!,&!)( *. &'( $(&+*): 3$6 &* "#8!43&( '*+ -(*-4( "(3),' *$ &'( $(&+*):1 *) +( ,3$ .*),( 3$ 3)&#!,#34 $(&+*): "&)!,&!)( &'3& 8((&" &'( ;<= )(>!#)(8($&"/ ?4(#$2()% @AB -)*-*"(" 3 "*4!&#*$ &'3& 2(4*$%" &* &'( "(,*$6 %)*!-1 25 #8-*"#$% 3 6(&()8#$(6 $(&+*): "&)!,&!)(/ C( -)*D(" &'3& 366#$% )3$6*8 4#$:" &* 3 EF )(%!43) 43&&#,(1 &'( )("!4&#$% $(&+*): #" 3 ;<= G'#%' ,4!"&() 6(%)(( 3$6 "'*)& %(*6("#,H/ !"#" $%&'(%)*+ $+,-./01 0'( -)*24(8 *. )3$6*8 %)3-'" #" &'3& &'(5 ,3$$*& -)*-I ()45 )(-)("($& 3$ #8-*)&3$& )(34 +*)46 -)*-()&59 )(43&#*$"'#-" 38*$% -(*-4( 3)( $*& )3$6*8 3$6 +( &)($6 &* '3D( "&)*$%() )(43&#*$"'#-" +#&' ,4*"() -3)&$()" &'3$ +#&' 4*$%I6#"&3$,( *$("/ J!& #$ &'( ,3"( *. )3$6*845 %($()3&(6 %)3-'"1 344 -*""#24( 3)," 2(&+(($ 3$5 -3#) *. $*6(" '3D( &'( "38( -)*232#4#&5 *. 2(#$% %($()3&(61 +'#,' 8(3$" &'3& +( 3)( 7!"& 3" 4#:(45 &* 8((& 3 -()"*$ &'3& 4#D(" #$ *!) "&)((& &'3$ 8((& 3 -()"*$ &'3& 4#D(" *$ *&'() ,*$&#$($&/ K$ &'( *&'() '3$61 )(%!43) %)3-'" G"!,' 3" 43&&#,("H ,3$ 8*6(4 &'#" -)*-()&5 2(,3!"( (3,' $*6( #" 4#$:(6 +#&' #&" ,4*"("& $(#%'2*)"/ L$*&'() #$&()("&#$% -)*-()&5 #" &'3& *!) $(#%'2*)" 3)( )(43&(6 (3,' *&'() &**1 .*)8#$% '(3D#45 ,*$$(,&(6 ,4!"&()"1 3%3#$ 3" #$ &'( )(34 +*)46 G!"!3445 3 .)#($6 *. 85 .)#($6 #" 34"* 85 .)#($6H/ 0'#" -)*-()&5 #" $*& -)("($&(6 #$ )3$6*8 %)3-'"/ C*+(D()1 )(%!43) $(&+*):" ,3$$*& 2( ,*$"#6()(6 "8344I+*)46 $(&+*):" 2(,3!"( &'( 6#"&3$,( 2(&+(($ 3$5 -3#) *. $*6(" #" &** 43)%( G#& 2(4*$%" &* O(n)H/ 0'( $(&+*): -)*-*"(6 25 ?4(#$2()%@AB #" 3 ,*82#$3&#*$ *. 2*&' &5-("/ M& "&3)&" +#&' 3 )(%!43)1 EI6#8($"#*$34 43&&#,( G3 n×n%)#6H1 +'()( (3,' $*6( #" )(43&(6 +#&' #&" .*!) $(#%'2*)" G"'*)& )3$%( )(43&#*$"'#-H/ 0'($1 *D() &'#" "&)!,&!)(1 .*) (3,' $*6( v#& 366" 3 $(+ 3), G4*$% )3$%( )(43&#*$"'#-H +#&' 3 -)*232#4#&5 -)*-*)&#*$34 &* ρ(v,w)−α1 +'()( ρ(v,w)#" &'( %)#6 6#"&3$,( 2(&+(($ v3$6 w1 (N-)(""(6 3" &'( $!82() *. (6%(" 2(&+(($ 2*&' $*6(" GO3$'3&&3$ 6#"&3$,(H1 3$6 α#" 3 -3)38(&() &* 367!"& &'( P)3$6*8#Q#&5P *. &'( %)#6/ ?4(#$2()% 6(8*$"&)3&(" &'3& #. α=2&'($ &'()( (N#"&" 3 6(4#D()5 34%*)#&'8 +#&' ,*"& O((log n)2)/ 0'#" )("!4& 6(8*$"&)3&(" &'3& #" -*""#24( &* ,*$"&)!,& 3 $3D#%324( $(&+*): +#&' &'( "&)!,&!)( *. 3 "8344I+*)461 #$ +'#,' 3$ 34%*)#&'8 .*) "(3),'#$% G3$6 !$6#$%H $*6(" #$ 4*%3)#&'8#, ( ,3$ 2( 6("#%$(6/ 0'#" "*4!&#*$ 344*+" 3 "(& *. ,*8-*$($&" &* 2( 6#"&)#2!&(6 #$ "!,' 3 $(&+*): *2&3#$#$% 3 ",34324(1 )(,*$!%!)324( 3$6 )*2!"&G.3#4!)( )("#"&3$&H "5"&(8/ 0'#" "&)!,&!)( #" D()5 3--)*-)#3&( .*) 6#"&)#2!&#$% &'( -43&.*)8 #$ 3 %)#6 *) (D($ #$ 3 8!4&#-)*,(""*) ,*8-!&()/ 2" 3(+4, 5+('1,/%,'.4 '4 67%**89./*:1 ;%,,'<+1 L48*"& 344 3%($& -43&.*)8" #$,4!6( &+* "()D#,(" +'#,' "&*)( #$.*)83&#*$ 32*!& &'( 3%($&" &'3& *-()3&( #$ &'(89 3 +'#&( -3%(" "()D#,( &'3& )(%#"&()" ,*$&3,& #$.*)83&#*$ G$38( 3$6 -'5"#,34 366)(""H 3$6 3 5(44*+ -3%(" "()D#,( &'3& )(%#"&()" &'( "()D#,(" &'3& &'( 3%($&" -)*D#6(/ 0'( +'#&( -3%(" "()D#,( #" -)*D#6(6 25 &'( L%($& O3$3%(8($& ;5"&(8 GLO;H 3$6 &'( 5(44*+ -3%(" "()D#,( 25 &'( F#)(,&*)5 R3,#4#&3&*) GFRH #$ &'( RMSL 32"&)3,& 3),'#&(,&!)(/ L$6 +#&' 6#..()($& $38(" &'("( "()D#,(" 3)( -)*D#6(6 #$ 344 3%($& -43&.*)8"/ C3D#$% *$( LO; 3$6 *$( FR ,3$ 2( ($*!%' .*) "8344 "5"&(8"1 2!& #&" -().*)83$,( 6(,35" >!#,:45 3" &'( $!82() *. 3%($&" #$,)(3"("/ 0)36#&#*$34 &(,'$#>!(" .*) 6#"&)#2!&(6 "5"&(8" '3D( 2(($ !"(6/ L$6 )(,($&45 "(D()34 3--)*3,'(" 23"(6 *$ -(()I&*I-(() ,*8-!&#$% 6(34 +#&' &'#" -)*24(8 +#&' "*8( "!,,("" #$ "*8( ($D#)*$8($&"/ F#..()($& 3%($& -43&.*)8"1 "!,' 3" TLFU@VB1 O36:#&@WB1 L%($&;,3-(@XYB *) O3%($&#N@XXB ,3$ 6#"&)#2!&( &'( 3%($&" *. 3$ ;OL #$ "(D()34 '*"&"/ J!& 344 *. &'(8 !"( &+* 3--)*3,'("9 83#$&3#$ 344 *. &'( #$.*)83&#*$ 3" 3 ,($&)34#Q(6 "()D#,( *) )(-4#,3&( 344 *. &'( #$.*)83&#*$ #$ (3,' '*"&1 !"#$% &(,'$#>!(" *. 6#"&)#2!&(6 "5"&(8" &* -)*-3%3&( &'( ,'3$%(" 3$6 &* :((- &'( 6#..()($& '*"&" !-63&(6/ ;!,' "*4!&#*$" '3D( &'( "38( -!)-*"(9 &* :((- &'( #$.*)83&#*$ 32*!& &'( ,*8-4(&( OL; #$ (3,' '*"& 3D3#4324(1 -)*-3%3&#$% &'( ,'3$%(" +'($ $((6(6/ 0'( "*4!&#*$ -)*-*"(6 #$ &'#" -3-() #" )36#,3445 6#..()($&/ M& 6*(" $*& 3&&(8-& &* !$6 *!& 344 *. &'( #$.*)83&#*$1 2!& 6(34 +#&' 4*,34 #$.*)83&#*$ 3$6 4!$,' 3 "(3),' -)*,("" +'($ !"#!"# Figura 2.3: Estructura de Kleinberg. La estructura inicial es una cuadr´ ıcula regular. Las conexiones aleatorias entre dos nodos distantes se establecen con una probabilidad inversamente proporcional al cuadrado de la distancia entre ellos. comienza con una red regular con nnodos situados en un anillo y kvecinos por cada nodo. Algunos enlaces (seleccionados al azar) se vuelven a reconectar con una probabilidad ρ, 0 ≤ρ≤ 1 (ve´ ase Figura 2.2). Los autores concluyen que con valores intermedios de ρse puede obtener una red con caracter´ ısticas de mundo peque˜ no (alto grado de agrupaci´ on y longitud de trayecto entre nodos peque˜ no). Otro m´ etodo para construir una red con propiedades de mundo peque˜ no fue propuesto por Kleinberg en [29]. La red se basa en un sistema de rejilla de n×ndimensiones donde todos los nodos de la red est´ an conectados a los vecinos m´ as cercanos (conexiones cortas). Entonces, las conexiones aleatorias largas son establecidas con una probabilidad pij que es inversamente proporcional al cuadrado de la distancia entre ellos: pij ∝r−γ ij donde res la distancia de Manhattan (n´ umero de enlaces entre nodos) en la red entre los nodos iyj(v´ ease la Figura 2.3). Kleinberg concluye que cuando γes igual a la dimensi´ on de la red, por medio de un algoritmo voraz se puede encontrar un nodo con caminos cuya distancia es inferior a log(n)2. Kleinberg presenta un modelo jer´ arquico para la generaci´ on de redes con propiedades de mundo peque˜ no [28]. Primero, la jerarqu´ ıa es modelada como un ´ arbol que tiene nhojas. La distancia entre dos hojas uyvse define como la menor distancia al predecesor com´ un h(u, v) en el ´ arbol. Basado en eso, Kleinberg define una red donde para un nodo vcon grado kla probabilidad de establecer un enlace con un nodo wes proporcional a bβh(v,w)(v´ ease Figura 2.4). 14 2.3. Redes complejas Identity and search in social networks Duncan J. Watts,1, 2, 3, †Peter Sheridan Dodds,2, ‡and M. E. J. Newman3, § 1Department of Sociology, Columbia University, New York, NY 10027. 2Columbia Earth Institute, Columbia University, New York, NY 10027. 3Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, NM 87501 (Dated: April 2, 2002) Social networks have the surprising property of being “searchable”: ordinary people are capable of directing messages through their network of acquaintances to reach a specific but distant target person in only a few steps. We present a model that offers an explanation of social network searchability in terms of recognizable personal identities defined along a number of social dimensions. Our model defines a class of searchable networks and a method for searching them that may be applicable to many network search problems including the location of data files in peer-to-peer networks, pages on the World Wide Web, and information in distributed databases. In the late 1960’s, Travers and Milgram [1] conducted an experiment in which randomly selected individuals in Boston, Massachusetts, and Omaha, Nebraska, were asked to direct letters to a target person in Boston, each forwarding his or her letter to a single acquaintance whom they judged to be closer than themselves to the target. Subsequent recipients did the same. The average length of the resulting acquaintance chains for the letters that eventually reached the target (roughly 20%) was approximately six. This reveals not only that short paths exist [2, 3] between individuals in a large social network but that ordinary people can find these short paths [4]. This is not a trivial statement, since people rarely have more than local knowledge about the network. People know who their friends are. They may also know who some of their friends’ friends are. But no one knows the identities of the entire chain of individuals between themselves and an arbitrary target. The property of being able to find a target quickly, which we call searchability, has been shown to exist in certain specific classes of networks that either possess a certain fraction of hubs (highly connected nodes which, once reached, can distribute messages to all parts of the network [5, 6, 7]) or are built upon an underlying geometric lattice which acts as a proxy for “social space” [4]. Neither of these network types, however, is a satisfactory model of society. In this paper, we present a model for a social network that is based upon plausible social structures and offers an explanation for the phenomenon of searchability. Our model follows naturally from six contentions about social networks. 1. Individuals in social networks are endowed not †Electronic address: [email protected] ‡Electronic address: [email protected] §Electronic address: [email protected] k i h=1 h=2 i, j j,k g=6 ij B l=4 ij x =3 A b=2 FIG. 1: (A) Individuals (dots) belong to groups (ellipses) which in turn belong to groups of groups and so on giving rise to a hierarchical categorization scheme. In this example, groups are composed of g= 6 individuals and the hierarchy has l= 4 levels with a branching ratio of b= 2. Individuals in the same group are considered to be a distance x= 1 apart and the maximum separation of two individuals is x=l. The example individuals iand jbelong to a category two levels above that of their respective groups and the distance between them is xij = 3. Individuals each have zfriends in the model and are more likely to be connected with each other the closer their groups are. (B) The complete model has many hierarchies indexed by h= 1 . . . H, and the combined social distance yij between nodes iand jis taken to be the minimum ultrametric distance over all hierarchies yij = minhxh ij. The simple example shown here for H= 2 demonstrates that social distance can violate the triangle inequality: yij = 1 since iand jbelong to the same group under the first hierarchy and similarly yjk = 1 but iand kremain distant in both hierarchies giving yik = 4 > yij +yjk = 2. only with network ties, but identities [8]: sets of charTypeset by REVT EX Figura 2.4: ´ Arbol de distancias sociales jer´ arquicas presentado por Watts [49] y Kleinberg [28]. Los individuos se agrupan considerando caracter´ ısticas sociales: trabajo, ubicaci´ on geogr´ afica o intereses. En el ejemplo, lindica el n´ umero de niveles de la jerarqu´ ıa (l= 4), bes el factor de ramificaci´ on (b= 2) y xindica la separaci´ on entre dos individuos. Otro modelo a considerar es la combinaci´ on de un modelo de grid basado en distancias y un modelo jer´ arquico. Esta idea es propuesta por Kleinberg en [27] donde define un nuevo modelo basado en una estructura de grupo. Kleinberg afirma que las personas que pertenecen al mismo grupo peque˜ no tienen m´ as probabilidades de estar conectados. Por ejemplo, en un modelo de cuadr´ ıcula se pueden encontrar grupos (sub-cuadr´ ıculas) donde los nodos est´ an m´ as cerca. En las jerarqu´ ıas, los grupos se pueden encontrar en sub´ arboles donde dos nodos est´ an dentro. El modelo se basa en la distancia entre dos nodos vywque se define como el tama˜ no del grupo m´ as peque˜ no que contiene ambos nodos. Un v´ ınculo entre dos nodos vywse establece con una probabilidad inversamente proporcional al tama˜ no del grupo m´ as peque˜ no donde ambos nodos (g(v, w)γ). El otro grupo de modelos existentes que vamos a comentar es el de Redes sin escala. Este tipo de redes se caracterizan por el grado de los nodos que componen la red. El grado de la mayor´ ıa de los nodos es bajo mientras que unos pocos nodos presentan un alto grado de conexi´ on. Esta caracter´ ıstica se refleja en varias funciones matem´ aticas. La m´ as conocida es la ley de potencias opower-law: pk∼k−α El par´ ametro αindica la tasa de decaimiento, un valor bajo de αsignifica un decaimiento m´ as lento y un valor mayor de αsignifica un decaimiento m´ as dr´ astico del grado de conexi´ on de los nodos. Barabasi y Albert [5] presentan un modelo matem´ atico para crear una red con caracter´ ısticas de power-law. El m´ etodo para crear la red realiza lo siguiente: cuando un nuevo nodo llega a la red, tiene m´ as probabilidad de establecer una conexi´ on con nodos que est´ an altamente conectados que con nodos que tienen pocas conexiones. La probabilidad de que un nodo que ya est´ a en la red reciba un nuevo enlace es p(ki) = c ki, donde ces una constante de normalizaci´ on 2. Estado del arte 15 ykies el grado de conexi´ on del nodo i. Una vez revisado los tipos de redes existentes y los principales modelos estructurales podemos afirmar que en este proyecto el uso de redes nos ayuda a modelar escenarios complejos donde el n´ umero de actores que intervienen es elevado. Concretamente, en este trabajo las redes que se utilizar´ an para modelar las interacciones entre los usuarios durante un evento determinado ser´ an redes de informaci´ on donde los nodos ser´ an las cuentas de los usuarios y los enlaces las comunicaciones entre ellos. A partir de estas redes, se analizar´ an propiedades como las que se han comentado en los modelos estructurales (longitud de caminos, grados de conexi´ on, etc.) para comprender qu´ e comportamientos comunicativos emergen. 2.4 Redes sociales online En t´ erminos esenciales, una red social online es considerada una estructura compuesta por un conjunto de usuarios (individuos u organizaciones) relacionados en base a un criterio, tales como parentesco, amistad, relaci´ on profesional, etc. y que estas relaciones se han establecido utilizando un medio online. En los ´ ultimos a˜ nos, en Internet han aflorado muchas comunidades locales en forma de redes sociales online y su n´ umero de usuarios activos se ha ido incrementando con el auge de las nuevas tecnolog´ ıas y el acceso a los nuevos canales de informaci´ on. Existen diferentes tipos de redes sociales online: de tipo profesional, relacionadas con la amistad, con aficiones, etc. Las redes sociales online como Facebook, Twitter, Linkedin o Flickr contienen millones de usuarios que comparten pensamientos, preferencias, creencias pol´ ıticas as´ ı como establecen enlaces entre los usuarios. Cada una de sus contribuciones deja una huella digital y para poder realizar cualquier tipo de an´ alisis es necesario procesar y gestionar ese volumen de datos. Actualmente, gracias a la tecnolog´ ıa disponible dentro del ´ area de Big Data, estos datos pueden ser almacenados y procesados de una manera eficiente [32]. Este hecho permite que se pueda analizar y extraer informaci´ on sobre el comportamiento de las personas y las interacciones entre usuarios. El an´ alisis de las redes sociales online tiene una aplicaci´ on directa en diversas ´ areas. Concretamente, el an´ alisis de redes sociales virtuales ha sido utilizado para campa˜ nas de marketing on-line y estrategias de persuasi´ on [31], dise˜ no de interfaces de usuario, sistemas de recomendaci´ on, para determinar consumidores potenciales [1] o para determinar la personalidad de los usuarios a trav´ es de sus interacciones [22]. El an´ alisis de las interacciones en las redes sociales facilita la comprensi´ on de los flujos de informaci´ on y la localizaci´ on de usuarios tienen una 16 2.4. Redes sociales online posici´ on influyente en la red [44, 45]. Otros ´ ambitos donde se ha aplicado el an´ alisis de la redes sociales son la personalizaci´ on de los resultados de b´ usquedas bas´ andose en los intereses de nodos vecinos en la red [10], as´ ı como para el terrorismo [43] o el cyberbullying [6]. En el trabajo presentado, nos centraremos principalmente en una red social online: Twitter. La raz´ on por la que nos decantamos por esta red social y no por otra es porque Twitter proporciona un API que facilita el acceso a la informaci´ on y los usuarios que utilizan esta red tienen un perfil p´ ublico en su mayor parte. Twitter [48] naci´ o en el a˜ no 2006 y es una red social catalogada como un servicio de microblogging. Su principal caracter´ ıstica es que permite al usuario publicar mensajes de texto plano de una longitud determinada, establecida en 140 caracteres. Dichos mensajes son denominados tweets.´ Estos se muestran en la p´ agina principal del usuario y pueden estar sometidos a ciertas acciones por parte del resto de los usuarios. Dichas acciones son las siguientes: •Cualquier usuario puede realizar comentarios en los tweets (que no sobrepase el m´ aximo establecido). A trav´ es de estos se puede citar directa o indirectamente a otro usuario. •De la misma forma, un tweet puede ser retweeteado (difundir sin cambiar el contenido por otro usuario) o citado (hacer referencia a ´ el, pero con un texto o usuario que lo acompa˜ ne). •Un usuario puede indicar afinidad por el contenido del tweet con la opci´ on de “Me gusta”. Sin embargo, con esta acci´ on no se establece ning´ un tipo de lazo en la red social, simplemente indica una preferencia. Los usuarios son los encargados de subir contenido a la red, abarcando innumerables temas y discusiones. Los usuarios que comienzan a seguir a un usuario, pasan a ser denominados followers de ese usuario. Un usuario puede conectarse con otro a trav´ es de mensajes p´ ublicos (los tweets) o por mensajes directos, que es un tipo de mensajer´ ıa privada disponible dentro de Twitter. Hay muchas maneras de asociar un tema en Twitter, pero la manera m´ as f´ acil es mediante los hashtags. Los hashtags son etiquetas de texto precedidas por un s´ ımbolo hash (#) que contiene el nombre, frase o descripci´ on del tema. Adem´ as, gracias a los hashtags es posible asociar tendencias o establecer trending topics, que son hashtags muy utilizados en Twitter por los usuarios en un momento determinado. Por ejemplo, para las Elecciones Generales del 20N, los 2. Estado del arte 17 hashtags utilizados para seguir el evento fueron #EleccionesGenerales2015 y#Elecciones20D, ambos trending topic del momento durante los meses previos al evento y despu´ es de ´ este. Twitter ha sido usado para gran variedad de prop´ ositos, en diferentes situaciones y lugares. Sin embargo, ha tenido gran relevancia a la hora de seguir determinados eventos considerados “de actualidad” o “candentes”. Un ejemplo de ello es que fue usado para organizar y reportar diferentes protestas como la de Egipto en 2011 [11] o la conocida Primavera Valenciana de 2012 [2]. 2.5 An´ alisis de Redes Sociales Online C´ omo se comportan los usuarios en las redes sociales online, cuan complejas son y c´ omo se establecen a trav´ es de la comunicaci´ on y la interacci´ on digital han sido y sigue siendo temas de inter´ es en distintas ´ areas de conocimiento. Hablar de complejidad es un hecho, ya que cuanto mayor sea el n´ umero de personas en una red social online, mayor es el n´ umero de conexiones y posibles relaciones entre individuos. A trav´ es de las redes sociales online, y concretamente en Twitter, se le brinda a los usuarios la posibilidad compartir experiencias, divulgar opiniones y establecer lazos de “amistad”. Sin embargo, desde el punto de vista del an´ alisis estas redes, Huberman et. al [26] consideraron que muchas de las relaciones de “amistad” son irrelevantes , ya que hay usuarios que pueden seguir o ser amigos de otros usuarios sin que hayan interactuado nunca y que por tanto no haya un v´ ınculo real entre ellos. Teniendo en cuenta este hecho, lo que relamente interesa es conocer la red social que emerge considerando las interacciones entre usuarios. Varios trabajos se han centrado en estudiar y medir las caracter´ ısticas de diferentes redes sociales online. Mislove et. al [35] realizaron un estudio de cuatro redes populares: Flickr, Youtube,LiveJournal yOrkut, con el objetivo de analizar la estructura de los grafos generados por las relaciones entre individuos. Se demostr´ o que cada red ten´ ıa una estructura social diferente, y sin embargo, a pesar de su crecimiento incremental, dicha estructura permanec´ ıa invariable. As´ ı mismo, tambi´ en se lleg´ o a la conclusi´ on de que la interacci´ on entre usuarios ten´ ıa un alto grado de reciprocidad: los usuarios participaban y respond´ ıan mensajes entre ellos. Otros trabajos est´ an relacionados con el an´ alisis de la red social online Twitter debido a su facilidad para recuperar informaci´ on. Estos trabajos estudian y analizan la estructura de su red. Smith et al. [46] estudiaron las redes creadas en conversaciones pol´ ıticas en Twitter y las 24 3.4. Dimensi´ on funcional Figura 3.2: Dimensi´ on Funcional del SMA propuesto. Esta dimensi´ on proporciona informaci´ on sobre los servicios proporcionados por los agentes que forman parte del sistema. 3.4 Dimensi´ on funcional Cada rol definido en la unidad organizacional SocialNetworkAnalyzer ofrece y/o consume un conjunto de servicios que define la funcionalidad del sistema. ´ Esta se describe de la siguiente manera (ver figura 3.2): •RequestAnalysis: Es un servicio ofrecido por los agentes User con el objetivo de obtener informaci´ on relacionada con el an´ alisis de la evoluci´ on de un evento. Esta informaci´ on es procesada y mostrada al usuario a trav´ es de una interfaz web. •FollowEvent: El agente User ofrece este servicio que consiste en comenzar a seguir el evento y recopilar tweets asociados con el mismo. Este mismo agente se engarga de enviar un mensaje al agente Manager para a˜ nadir los agentes Monitor necesarios. •RetrieveInteractions: Este servicio est´ a ofrecido por el agente Monitor y consiste en la recolecci´ on de los mensajes asociados con el evento en Twitter. •Analysis: Este servicio es el responsable del an´ alisis de las interacciones del usuario en un evento. Lo proporciona el agente Analyzer y dicho an´ alisis, una vez efectuado, se dirige al agente User. •Visualize: Lo proporciona el agente User y el servicio consiste en la visualizaci´ on de los resultados del analisis proporcionado por el agente Analyzer al usuario final. 3. Dise˜ no del SMA 25 Figura 3.3: Dimensi´ on din´ amica del SMA propuesto. Muestra las interacciones entre las entidades que forman parte del sistema para realizar la recogida y almacenamiento de informaci´ on asociada a un evento en una red social online (FollowEvent). 3.5 Dimensi´ on din´ amica En esta dimensi´ on se definen las interacciones y sus roles participantes. Se consideran dos entidades de interacci´ on: •FollowEvent: Aqu´ ı participan los roles Monitor,User yManager (ver figura 3.3). El agente User inicializa la interacci´ on y los agentes Monitor yManager colaboran iniciando las actividades CreateMonitorsyRetrieveInterations. Se considera que el evento existe en el sistema. El Manager crea un nuevo Monitor para monitorizar los mensajes que se disponen en el evento. •RequestAnalysis: Aqu´ ı participan los roles Monitor,User yAnalyzer (ver figura 3.4). En este caso, tanto el agente Monitor como el User pueden iniciar la unidad de interacci´ on RequestAnalysis, pero solo ´ este ´ ultimo agente puede iniciar la actividad ShowResults. El agente Analyzer puede iniciar NetworkAnalysis,NodeAnalysis yStatisticsAnalysis. 26 3.6. Conclusiones Monitor/User RequestAnalysis initiates initiates Network Analysis Analyzer initiates Node Analysis initiates Statistics Analysis Show Results initiates collaborates initiates initiates Figura 3.4: Dimensi´ on din´ amica del SMA propuesto. Muestra las interacciones entre las entidades que forman parte del sistema para realizar el an´ alisis de la red de interacciones generada a partir de la informaci´ on recogida de un evento en una red social online ( RequestAnalysis) 3.6 Conclusiones El dise˜ no del SMA propuesto para llevar a cabo la recogida y an´ alisis de la informaci´ on de Twitter se ha realizado utilizando la metodolog´ ıa GORMAS. Esta metodolog´ ıa nos ha permitido definir el sistema por medio de tres dimensiones: estructural (nos especifica qu´ e roles intervienen en el sistema), funcional (describe qu´ e funcionalidad/servicios ofrece cada uno de los roles) y finalmente la din´ amica (especifica qu´ e interacciones y escenarios de interacci´ on se van a dar entre las entidades del sistema en funci´ on del rol que desempe˜ nen). El uso de la metodolog´ ıa nos ha permitido definir con detalle el dise˜ no del sistema que se utilizar´ a como base para el desarrollo del framework multiagente. CAP´ ITULO 4 Framework 4.1 Visi´ on global . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2 Plataforma y agentes . . . . . . . . . . . . . . . . . . . . 29 4.3 Protocolos de interacci´ on................. 34 4.4 Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . 38 En este trabajo se propone un sistema multiagente para la automatizaci´ on y distribuci´ on del proceso de recolecci´ on de datos de la actividad de los usuarios en redes sociales online. Posteriormente, se analiza su evoluci´ on en diferentes niveles de granularidad basados en m´ etricas estructurales de redes complejas. El sistema multiagente propuesto est´ a organizado en organizaciones virtuales donde hay un conjunto de roles (i.e., Manager,Monitor,Analyzer yUser) que definen los servicios ofrecidos. El papel m´ as relevante es el analizador que se caracteriza por ofrecer servicios relacionados con un an´ alisis configurable de la informaci´ on recopilada que est´ a asociada a un evento. Estos servicios ofrecen un an´ alisis de lo que ocurre antes, durante y despu´ es de un evento a nivel global e individual. Toda la informaci´ on generada durante ´ este se le proporciona al usuario final a trav´ es de una interfaz. Los agentes que forman parte del MAS funcionan asincr´ ona y simult´ aneamente, lo que da como resultado una eficiencia computacional. Los nuevos requerimientos o funcionalidades pueden ser abordados agregando nuevos agentes o reconfigurando los existentes. 4.1 Visi´ on global En esta secci´ on presentamos la implementaci´ on de un framework para el an´ alisis de la actividad de los usuarios asociada a un evento en redes sociales online, concretamente Twitter. El 27 28 4.1. Visi´ on global sistema est´ a basado en el dise˜ no propuesto en el cap´ ıtulo anterior y cuenta con seis agentes encargados de realizar la extracci´ on, almacenamiento, procesamiento y an´ alisis de la informaci´ on procedente de Twitter. Concretamente el sistema lo componen los siguientes roles: Manager, Monitor,Analyzer yUser. Algunos agentes pueden tener varios roles y realizar sus funciones en base a ellos. En total los agentes que componen el sistema son los siguientes: el agente VisualAgent es el intermediario entre el MAS y el usuario final. El usuario interact´ ua con este agente para indicar el evento sobre el que est´ a interesado en recoger informaci´ on y/o analizar. El agente VisualAgent recibe esta informaci´ on y env´ ıa un mensaje al agente ManagerAgent para iniciar el seguimiento del evento. El ManagerAgent es responsable de gestionar los eventos seleccionados por los usuarios. El agente AgentTweet es responsable de recopilar los mensajes de generados durante un evento. Estos mensajes son enviados al agente Neo4jAgent para ser almacenados. El agente QueryNeo4jAgent se encarga de extraer la informaci´ on de la base de datos y crear la red que se enviar´ a al agente GraphAnalyzerAgent.´ Este agente realiza un an´ alisis bajo demanda del usuario y todos los datos se env´ ıan al agente VisualAgent que muestra los resultados del an´ alisis de actividad asociada al evento seleccionado por el usuario. En los siguientes p´ arrafos, describimos con detalle los principales agentes del framework. La idea principal y su proceso general se puede dividir en dos partes: 1. B´ usqueda de la actividad asociada a un evento. A partir de una interfaz gr´ afica, el usuario introduce el nombre del hashtag en Twitter y presiona el bot´ on de b´ usqueda. Los agentes que participan son ManagerAgent,VisualAgent,AgentTweet yNeo4jAgent, que se encargan recoger los datos del evento por parte del usuario, recopilar todos los tweets que pueden encontrar relacionado con ese evento y almacenarlos en una base de datos. 2. An´ alisis de los datos. A trav´ es de la misma interfaz, el usuario introduce el hashtag que quiere analizar y un intervalo de fechas inicial y final. Hay que tener en cuenta que deben de existir datos del evento en la base de datos para efectuar esta acci´ on. Despu´ es, cuando el usuario presiona el bot´ on de analizar, el sistema se encarga de extraer los mensajes correspondientes a ese intervalo de tiempo, crear la red y analizar sus caracter´ ısticas. Los agentes que participan son ManagerAgent,VisualAgent,QueryNeo4jAgent yGraphAnalyzerAgent. 4. Framework 29 Figura 4.1: Estructura general del sistema. Indica la direcci´ on de los flujos de interacci´ on y/o conversaci´ on entre los diferentes agentes del sistema. 4.2 Plataforma y agentes El sistema se basa en un conjunto de agentes desarrollados utilizando la plataforma Magentix2 [33]. Magentix2 es una plataforma para SMAs abiertos que soporta protocolos y conversaciones de interacci´ on flexibles, comunicaci´ on indirecta e interacciones entre las organizaciones de agentes. Adem´ as, la plataforma permite la definici´ on de un contexto normativo, que se puede adaptar f´ acilmente a los cambios en los requisitos del sistema. Hoy en d´ ıa, Magentix2 ofrece soporte a tres niveles: Nivel organizacional que consiste en tecnolog´ ıas y t´ ecnicas relacionadas con las sociedades de agentes; Nivel de interacci´ on que soporta protocolos y conversaciones de interacci´ on flexibles; y a nivel de Agente que ofrece diferentes clases de agentes como CAgent (i.e., un agente que permite la creaci´ on autom´ atica de conversaciones simult´ aneas) o JasonAgent (i.e., agentes BDI que pueden participar en conversaciones simult´ aneas). 4.2.1 Rol Monitor: agentes AgentTweet yNeo4jAgent El agente AgentTweet utiliza el API de Twitter4J1para la recuperaci´ on de los datos p´ ublicos generados por los usuarios durante un evento. Dichos datos, una vez recopilados, son almacenados en Neo4J2por el agente Neo4jAgent. Neo4j es una base de datos de c´ odigo abierto NoSQL implementada en Java y Scala, es altamente escalable y utiliza las relaciones como 1http://twitter4j.org/en/index.html 2https://neo4j.com/ 30 4.2. Plataforma y agentes aspecto central de su modelo de datos, por lo que es capaz de almacenar, procesar y consultar conexiones de manera eficiente. Los modelos de datos en Neo4J consideran tres componentes: nodos para poder definir las entidades, etiquetas que se utilizan para agrupar los nodos en conjuntos y relaciones que conectan nodos y los organizan en estructuras arbitrarias. En el modelo propuesto, hemos considerado los siguientes nodos: •hashtag: representa el evento en el que un usuario est´ a interesado. Identificamos un solo atributo asociado al hashtag: el nombre del evento. •tweet: representa el mensaje (i.e., mensaje de texto, foto, video, etc.) que un usuario crea en Twitter. Identificamos un conjunto de atributos asociados al mensaje como coordenadas geogr´ aficas, anotaciones temporales, referencias a otros usuarios, n´ umero de likes/favoritos, etc. •usuario: representa a un usuario de Twitter que ha participado a trav´ es de la publicaci´ on de un mensaje o que ha sido mencionado en el contenido del mismo. Identificamos un conjunto de atributos asociados al usuario que han sido extra´ ıdos del propio mensaje como: anotaciones temporales, amigos/seguidores, likes, etc. Las relaciones que conectan los nodos en el modelo de datos propuesto son (ver Figura 4.2): •has hashtag, que conecta un tweet con un evento. •mentions, que conecta un tweet (i.e., mensaje de texto, foto, video, etc.) con uno o varios usuarios a los que se menciona o hace referencia en el tweet. •creates, que conecta a un usuario con un tweet que ´ el mismo ha creado. Utilizando estas entidades y relaciones, hemos podido almacenar eficientemente toda la informaci´ on generada por los usuarios sobre un determinado evento. Como ejemplo, se muestra el uso de este modelo para el caso de almacenar la actividad de los usuarios durante un evento en Twitter, pero puede extrapolarse a otras redes sociales donde las interacciones podr´ ıan ser modeladas como mensajes entre los usuarios sobre un tema o evento. En Twitter, hemos considerado los siguientes tipos de mensajes: •Mensajes globales que se utilizan cuando la actualizaci´ on est´ a pensada para cualquier persona que se preocupe por leerla. Este el tipo m´ as habitual de mensaje en Twitter. Esta informaci´ on y sus relaciones se representan utilizando el modelo propuesto para Neo4j como sigue: 4. Framework 31 Tweet A Tweet-mention B Tweet-reply-to C Tweet-mentions B Figura 4.2: Ejemplo de c´ omo se almacenar´ ıan los distintos tipos de mensajes de interacci´ on asociados a un evento utilizando el modelo propuesto para almacenar la informaci´ on en Neo4j. Los nodos del grafo representan las entidades del modelo. Las entidades consideradas en el modelo son: eventos (rojo), interacciones (verde), usuarios (azul). Los enlaces del grafo representan los tipos de relaciones que hay en el modelo de datos (i.e., creates, mention, has hashtag, y creates). Las relaciones que se muestran en el grafo son las generadas al insertar un tweet donde no se menciona a ning´ un usuario (rosa), un tweet que contiene una menci´ on (morado), un tweet que es un reply-to (amarillo), y una menci´ on a varios usuarios (mention). En la parte inferior se muestran los cuatro mensajes (tweets) insertados en la base de datos. (u:USER)-[:CREATES]->(t:MESSAGE) (t:MESSAGE)-[:HAS_HASHTAG]->(e:EVENT) •Mensajes individuales que son los que involucran a otro usuario. Los mensajes individuales en Twitter pueden ser: retweets,menciones yrespuestas a los usuarios. –Los retweets son mensajes que previamente fueron publicados por otro usuario. –Las menciones son mensajes que se usan cuando un usuario pretende informar a trav´ es de un tweet a una persona espec´ ıfica. A menudo, dos o m´ as usuarios tendr´ an conversaciones mediante la publicaci´ on de menciones entre s´ ı. –Las respuestas a los usuarios son mensajes en los que un usuario menciona a otro usuario en un tweet anterior. La informaci´ on sobre los mensajes individuales y sus relaciones se representan usando el modelo propuesto en Neo4j como sigue: (t:MESSAGE)-[:MENTIONS]->(u:USER) 32 4.2. Plataforma y agentes 4.2.2 Rol Analyzer: agentes QueryNeo4jAgent yGraphAnalyzerAgent El agente QueryNeo4jAgent es responsable de extrer la informaci´ on asociada a un evento durante un intervalo de tiempo. Para ello hace uso del lenguaje Cypher3. Cypher es un lenguaje de consulta de grafos declarativo que permite la ejecuci´ on eficiente de consultas y la actualizaci´ on de la base de datos. Cypher toma prestada su estructura de SQLqueries. Las cl´ ausulas se encadenan juntas y alimentan conjuntos de resultados intermedios entre s´ ı. El agente QueryNeo4jAgent utiliza este lenguaje para obtener informaci´ on sobre las interacciones de los usuarios asociadas a un evento durante un per´ ıodo de tiempo. Como ejemplo, mostramos una instancia de una consulta en Cypher para la recuperaci´ on de informaci´ on en Twitter que se ha generado sobre un evento “myEvent” en un intervalo de tiempo determinado [time start, time end]: MATCH (u:USER)-[:CREATES]->(t:MESSAGE)-[:HAS_HASHTAG] ->(e:EVENT{Hashtag:"myEvent"}), OPTIONAL MATCH (u2:USER)<-[:MENTION]-(t:MESSAGE), WHERE t.tweet_created_at>="time_start" AND t.tweet_created_at<="time_end", RETURN u.User_screen_name, t.tweet_id, u2.User_screen_name) Bas´ andose en la informaci´ on obtenida de la base de datos Neo4j, el agente QueryNeo4jAgent crea una red de interacciones del evento anotada temporalmente. Un usuario A se convierte en un nodo de la red cuando participa escribiendo un mensaje global o individual con el hashtag asociado al evento o cuando otro usuario B le hace referencia en un mensaje individual dentro del intervalo temporal seleccionado. Cada nodo de la red (usuario) tiene una etiqueta asociada que representa el instante cuando se uni´ o a la red (i.e., en instante cuando particip´ o por primera vez en el evento). Los enlaces de la red se establecen cuando un usuario escribe un mensaje individual donde se menciona a un usuario que ya estaba presente en la red (i.e., un usuario que ya hab´ ıa participado anteriormente en el evento con un mensaje) o a un usuario que todav´ ıa no forma parte de la red. Por lo tanto, el tipo de red es dirigido (ver Figura 4.3). Es importante observar que trabajamos con datos acumulados (i.e., la red en el tiempo ttambi´ en incluye los nodos y enlaces de un momento anterior t0< t). El agente QueryNeo4jAgent crea la red utilizando GRAPHML, un lenguaje para describir estructuras de redes complejas y sus datos asociados. Una vez que el agente QueryNeo4jAgent ha construido la red de interacciones de usuarios asociada a un evento durante un intervalo temporal, el agente GraphAnalyzerAgent inicia el 3https://neo4j.com/developer/cypher-query-language/ 4. Framework 33 Figura 4.3: Red de interacciones generada a partir de la actividad de los usuarios en Twitter asociada a un evento. an´ alisis de las propiedades estructurales a nivel global y/o individual. Para llevar a cabo esta tarea, el agente utiliza JUNG4y Gephi Toolkit5. Jung, as´ ı como Gephi Toolkit, son una serie de librer´ ıas software que facilitan el modelado, an´ alisis y visualizaci´ on de datos que pueden ser representados como una red. El agente GraphAnalyzerAgent ofrece dos tipos de an´ alisis de las interacciones de los usuarios: •An´ alisis de nivel de red. A nivel de red, el agente GraphAnalyzerAgent estudia la evoluci´ on de las siguientes propiedades a lo largo del tiempo: 1. Nodos, es decir, la evoluci´ on de la participaci´ on de los usuarios durante un evento o eventos. 2. Enlaces, es decir, c´ omo fluye la informaci´ on en la red e influye en la formaci´ on del componente gigante. 3. Longitud y di´ ametro medio de la red para entender en qu´ e momento hay un cambio en la estructura de la red y, por lo tanto, en la comunicaci´ on. 4. Modularidad y grado medio, c´ omo de conectadas est´ an las comunidades. 5. Densidad, un indicador de la proporci´ on de enlaces que hay con respecto a todos los posibles. 6. N´ umero de nodos en la componente gigante, nivel de participaci´ on de usuarios dentro de la componente principal. •An´ alisis a nivel individual. El agente GraphAnalizerAgent estudia la evoluci´ on de las propiedades de centralidad de los usuarios (i.e., nodos de la red) en un evento. Las propiedades de centralidad determinan qu´ e usuarios son los m´ as importantes basados en 4http://jung.sourceforge.net/ 5https://gephi.org/toolkit/ 40 5.2. Medidas a nivel de red distintos tipos de eventos. 5.2 Medidas a nivel de red El primer conjunto de medidas estudia la red asociada al evento como un todo. Las medidas a nivel de red determinan principalmente las propiedades estructurales o topol´ ogicas, es decir, c´ omo se conectan unos nodos con otros. Una vez determinadas las propiedades, ´ estas nos ayudan a determinar si una red sigue un determinado patr´ on ya definido como puede ser una red de tipo small world, scale-free, o random y por lo tanto inferir propiedades propias del tipo de red. Antes de entrar en la definici´ on de algunas de las propiedades m´ as importantes que determinan la estructura de la red, vamos a presentar la siguiente notaci´ on. Grepresenta una red que consiste en un conjunto de nodos N, donde cada nodo i∈ {1, ..., n}representa a un usuario. Los nodos est´ an conectados a trav´ es de enlaces E∈N×N. Utilizamos la matriz de adyacencia Apara representar la red. Un enlace entre un nodo iy un nodo jse representa como Aij = 1. Si no existe un enlace entre iyjse representa como Aij = 0. Considerando esta definici´ on, presentamos las siguientes propiedades que se han tenido en cuenta en el an´ alisis. Nodos. Es un indicador del n´ umero de nodos (i.e., en el contexto del proyecto los nodos hacen referencia a cuentas de usuario) que han participado en un evento. La evoluci´ on de los nodos permite ver el ritmo al cual nuevos usuarios se incorporan al mismo con su primer mensaje que usa el hashtag asociado al evento. Es interesante tener en cuenta la evoluci´ on del n´ umero de nodos porque nos permite detectar en qu´ e momento se unen m´ as usuarios a la red (al evento). Enlaces. Los enlaces representan las interacciones entre usuarios (i.e., menciones, retweets y mensajes) y muestran c´ omo fluye la informaci´ on en el evento. La evoluci´ on del n´ umero de enlaces ayuda a ver en qu´ e momento los usuarios interact´ uan m´ as y como consecuencia se forma la componente gigante. La componente gigante es la componente conectada de la red que contiene una mayor parte de los nodos. Longitud media de los caminos y di´ ametro de la red. Se define como la media de las distancias entre todos los pares de nodos, es decir, la separaci´ on t´ ıpica entre pares de usuarios. 5. Caso de Estudio 41 Si consideramos la red Gcon un conjunto de v´ ertices N, siendo d(i, j)la distancia m´ as corta entre iyjy asumiendo que d= (i, j) = 0 si ino puede ser alcanzado por j. La longitud media del camino m´ as corto lgser´ a: lg=1 |N|·(|N|−1) ·X i6=j d(i, j) donde |N|es el n´ umero de nodos de la red G. La evoluci´ on del camino medio ayuda a ver en qu´ e momento hay un cambio estructural en la red. El di´ ametro es la distancia m´ axima de entre todas las distancias cortas entre dos usuarios de la red. Estas medidas nos indican cu´ antos retweets, menciones, o reply-to ser´ ıan necesarios para que un mensaje se propagara por toda la red (di´ ametro) o llegue a un usuario particular (camino medio). Densidad. La densidad determina la conectividad en la red entre pares, es decir, si un usuario est´ a conectado a otro usuario y ´ este a su vez al primero. Esto se calcula dividiendo el n´ umero de relaciones existentes entre las relaciones totales posibles. Esta medida resulta ´ util para conocer si entre usuarios existe reciprocidad entre los mensajes que se env´ ıan (si el usuario A escribe al usuario B y ´ este ´ ultimo responde de vuelta al usuario A). Si en un evento hay muchos usuarios que escriben pero no son respondidos, la densidad de la red disminuye. Modularidad. La modularidad es la fracci´ on de los enlaces que caen dentro de los grupos establecidos menos la fracci´ on esperada si los enlaces se distribuyeran al azar. El valor de la modularidad est´ a en el rango [-1/2,1]. Es positivo si, por casualidad, el n´ umero de enlaces dentro de los grupos excede el n´ umero esperado sobre la base. Para una divisi´ on determinada de los v´ ertices de la red, la modularidad refleja la concentraci´ on de los enlaces dentro de los m´ odulos en comparaci´ on con la distribuci´ on aleatoria de enlaces entre todos los nodos independientemente de los m´ odulos. Usuarios que son parte de la componente gigante de la red. El an´ alisis de esta propiedad nos facilita estimar en qu´ e momento durante un evento la componente gigante se forma, es decir, en qu´ e momento se forma un n´ ucleo de interacciones que contiene a la mayor parte de los usuarios que participan en el evento. Esta medida es importante porque a partir del momento en el que se forma la componente gigante se determina el mejor momento para difundir informaci´ on. 42 5.3. Medidas a nivel de nodo En las medidas no se tiene en cuenta el n´ umero de contactos de los usuarios. Es un medida sencilla de obtener y frecuentemente se emplea para dar una idea de los impactos que tiene un determinado tweet. Sin embargo, nosotros consideramos que las medidas a partir de las menciones directas a usuarios tienen una mayor visibilidad y, por lo tanto, un mayor impacto. 5.3 Medidas a nivel de nodo El segundo conjunto de medidas se centra en la relevancia de los usuarios dentro de la red, con el fin de identificar aquellos usuarios m´ as importantes para la formaci´ on de la red o para la transmisi´ on de informaci´ on. Habitualmente estas medidas se realizan sobre la red completa final, pero en nuestro caso, la evoluci´ on de la importancia de los usuarios a lo largo del evento es muy relevante y, como se muestra m´ as adelante, var´ ıa mucho, especialmente en cierto tipo de eventos. Existen muchas definiciones de importancia y por lo tanto muchas medidas de centralidad para redes. En el an´ alisis realizado en el proyecto hemos considerado las siguientes: Centralidad basada en grado (degree centrality). Una de las medidas m´ as simples es tener en cuenta el grado de un nodo de la red, el n´ umero de enlaces conectados al nodo. Aunque es una medida sencilla, puede ser relevante. Por ejemplo, en una red social parece razonable suponer que aquellos nodos que est´ an muy conectados puedan tener m´ as acceso a m´ as informaci´ on o m´ as prestigio que aquellos nodos que tienen menos. Un ejemplo claro donde se utiliza esta medida es en redes de citaciones de art´ ıculos, donde la importancia de un art´ ıculo (nodo) depende del grado de entrada de ese art´ ıculo (in-degree). La expresi´ on que calcula el valor de centralidad basada en grado es la siguiente: CDi=X j Aij En las redes dirigidas, cada nodo tiene dos grados. El grado de entrada es el n´ umero de enlaces entrantes y el grado de salida es el n´ umero de enlaces salientes. En el contexto de las redes sociales, para un nodo i, el grado de entrada representa el n´ umero de mensajes generados por otros usuarios donde se hace referencia a i. Esta m´ etrica indica si el usuario es significativo para otra gente, es decir, que ese usuario es una persona conocida dentro de la comunidad que podr´ ıamos definir como un referente dentro de la red. El grado de salida para un nodo ide la 5. Caso de Estudio 43 red representa el n´ umero de mensajes que un usuario crea haciendo referencia a otros usuarios. El grado de salida indica la actividad del usuario, es decir, que el grado de interacci´ on del usuario A con el resto de participantes en el evento. Cout Di= N X j=1 Aij Cin Di= N X j=1 Aji Centralidad basada en vector de valores propios (eigenvector centrality). Una extensi´ on natural de la centralidad basada en el grado es la centralidad basada en el vector de valores propios. En esta medida de centralidad los nodos vecinos no se consideran todos iguales. En muchas circunstancias, la importancia de un nodo de la red aumenta teniendo en cuenta a qu´ e nodos est´ a conectado y si estos son tambi´ en importantes. La centralidad basada en vectores propios del nodo vpuede ser definida como: CVi=1 λX j∈ki Cvj=1 λX j∈G AijCvj donde kies el conjunto de vecinos de iyλes una constante. En el contexto de las redes sociales, un usuario con un alto valor de eigenvector es una autoridad que se le sigue por los contenidos que emite. Dentro de esta misma categor´ ıa, tambi´ en se tiene en cuenta el PageRank, un tipo de medida que determina la relevancia de los nodos en la red en base al mayor valor del eigenvector en una matriz de adyacencia normalizada A0. Centralidad basada en cercan´ ıa (Closeness centrality). Una medida de centralidad diferente a las anteriores es la proporcionada por la centralidad basada en cercan´ ıa, que mide la distancia media de un nodo al resto de nodos. Formalmente, la cercan´ ıa de un nodo ise define como: CCLOi=|N| PjSij donde Ses la matriz de distancias de la red, es decir, aquella matriz cuyos elementos (i,j) 44 5.3. Medidas a nivel de nodo corresponden a la distancia m´ as corta desde el nodo ihasta el nodo j. Esta medida se puede interpretar como la rapidez que tomar´ a la propagaci´ on de la informaci´ on desde un nodo a todos los dem´ as o como la accesibilidad de un nodo en la red. Uno de los problemas de esta medida es que el rango de valores de centralidad entre el m´ aximo y el m´ ınimo es muy estrecho. La consecuencia de esto es que es dif´ ıcil distinguir entre valores m´ as o menos centrales utilizando esta medida. Los valores de centralidad tienen a acumularse en un peque˜ no intervalo y es necesario mirar los d´ ıgitos del final para determinar cu´ al es m´ as relevante. Centralidad basada en intermediaci´ on (Betweenness centrality). Un concepto de centralidad que es diferente a los anteriores es la centralidad basada en la intermediaci´ on. Esta medida de centralidad para un nodo amide cu´ antos caminos entre otros dos nodos de la red (i, j)pasan a trav´ es de ´ el. Los nodos con un alto valor de betweenness pueden ser considerados como influyentes en una red ya que controlan la informaci´ on que otros nodos se est´ an pasando. Los nodos que tienen el valor m´ as alto de betweenness en escenarios donde hay transmisi´ on de informaci´ on son aquellos nodos por los que m´ as mensajes pasan y en el caso de que obtuvieran un beneficio por hacer de “pasarela” de mensajes, podr´ ıan adquirir una gran relevancia en la red. Los v´ ertices que tienen un alto valor de betweenness son tambi´ en aquellos que al ser eliminados interrumpir´ an m´ as comunicaciones entre otros nodos de la red ya que a trav´ es de ellos pasan la mayor parte de los caminos que recorren los mensajes. La idea de centralidad basada en intermediaci´ on puede ser considerada como una aproximaci´ on a la influencia que tienen los nodos sobre el proceso de comunicaci´ on. Formalmente, la intermediaci´ on CBETide un nodo ien una red se define como: CBETi=X j,k bjik bjk donde bjk es el n´ umero de caminos m´ as cortos desde el nodo jhasta el nodo k, y bjik el n´ umero de caminos m´ as cortos desde jhasta kque pasan a trav´ es del nodo i. Un usuario con un valor alto de betweeness indica que es un punto de conexi´ on entre distintos grupos de usuarios y suele tener cierto control sobre los flujos de informaci´ on en la red. Un nodo con un betweenness alto no es necesario que tenga un grado de entrada o de salida alto. Si quisi´ eramos difundir un mensaje en una red social, ser´ ıa interesante que los usuarios con alto valor de intermediaci´ on reenviaran el mensaje. 5. Caso de Estudio 45 Figura 5.1: Evoluci´ on de las propiedades estructurales a nivel de red: longitud del camino medio, grado medio de conexi´ on y di´ ametro de la red. Evento #MuereBarber´ aARV 5.4 An´ alisis de eventos En esta secci´ on vamos a realizar el an´ alisis de las estructuras comunicativas que emergen a partir de las interacciones entre usuarios durante un evento en Twitter. Veremos las propiedades estructurales a nivel de red y a nivel de nodo que se comentaron en la secci´ on anterior y analizaremos su evoluci´ on. A partir de estas medidas podremos detectar patrones de comunicaci´ on que se siguen en funci´ on del tipo de evento. Los eventos que hemos considerado son los siguientes: #MuereBarber´ aARV (un evento de televisi´ on que trata temas de actualidad pol´ ıtica), #ChampionsLeague (un evento de tipo deportivo) y #pesadillazamora (un evento de televisi´ on de entretenimiento). 5.4.1 Evento #MuereBarber´ aARV Teniendo en cuenta la evoluci´ on de las propiedades estructurales, podemos observar c´ omo se comportan los usuarios en el evento. Su evoluci´ on se puede dividir en tres etapas: inicio, durante, y final del programa. Esta divisi´ on nos muestra que el comportamiento de los usuarios no es uniforme durante el programa “Al Rojo Vivo”, si no que los usuarios modifican su forma de interactuar a lo largo del programa. La figura 5.1 muestra la evoluci´ on del di´ ametro, el grado medio de conexi´ on y la longitud del camino medio. El di´ ametro de la red sigue una evoluci´ on parecida al camino medio de la red. Al principio del evento el diametro tiene un valor entorno a cinco, esto significa que la distancia mayor entre dos usuarios de la red es cinco. Esto es un indicador de que al principio del evento 46 5.4. An´ alisis de eventos Figura 5.2: Evoluci´ on de las propiedades estructurales a nivel de red: modularidad. Evento #MuereBarber´ aARV Figura 5.3: Evoluci´ on de las propiedades estructurales a nivel de red: densidad. Evento #MuereBarber´ aARV los usuarios que han participado mediante mensajes son pocos y entre ellos ha habido una comunicaci´ on rec´ ıproca. Respecto al camino medio,´ este va aumentando conforme crece la red, lo que significa que las comunicaciones entre los usuarios no se mantiene constante, sino que cambia. El momento m´ as relevante de este cambio es durante el transcurso del programa (entre los instantes de tiempo T+1 y T+3). Este cambio en la estructura se debe a la participaci´ on de nuevos usuarios (nuevos nodos que se incorporan a la red) y la generaci´ on de mensajes de interacci´ on (ver figura 5.4). El grado de conexi´ on de los nodos no evoluciona de una manera menos significativa que el camino medio. El valor del grado de conexi´ on est´ a alrededor de 1.5. Esto significa que de media un usuario participa en la red con uno o dos mensajes en la red. La figura 5.2 nos muestra la evoluci´ on de la modularidad. La evoluci´ on de la modularidad nos proporciona informaci´ on sobre las comunidades que se forman en la comunicaci´ on durante este 5. Caso de Estudio 47 Figura 5.4: Evoluci´ on de las propiedades estructurales a nivel de red: n´ umero de nodos, n´ umero de ejes y componente gigante. Evento #MuereBarber´ aARV evento. En general, durante todo el evento, se mantiene el n´ umero constante de comunidades, esto es un indicador de que los usuarios siguen interactuando con el mismo grupo de cuentas de Twitter durante la evoluci´ on del programa. La figura 5.3 nos muestrala densidad de la red. ´ Esta tiene un valor bajo que va decreciendo a lo largo del evento. Esto es debido a que hay una muy baja reciprocidad en la comunicaci´ on entre los usuarios (i.e., los mensajes generados por un usuario A hacen referencia a otro(s) usuario(s) pero ´ este (o ´ estos) no interaccionan con A). Finalmente, la figura 5.4 muestra la evoluci´ on del n´ umero de nodos y enlaces as´ ı como el tama˜ no de la componente gigante. Como hemos comentado anteriormente, es durante el evento cuando se produce un aumento significativo de la participaci´ on. Es en ese periodo cuando el n´ umero de usuarios, mensajes y el tama˜ no de la componente gigante aumentan. Cabe destacar que el n´ umero de mensajes es mayor que el n´ umero de nodos por lo que durante el evento los usuarios participan de una manera m´ as activa comentando lo que est´ a sucediendo con m´ as de un mensaje. Esto hace que el grado medio de conexi´ on aumente (ver figura 5.1). Es importante fijarse en el momento donde la componente gigante crece. Esto es interesante a la hora de decidir cu´ ando es relevante generar un mensaje cuyo objetivo sea lleguar a la mayor parte de usuarios que est´ an participando en el evento. El an´ alisis que ofrece el framework permite detectar qu´ e usuarios juegan un papel relevante en la comunicaci´ on teniendo en cuenta distintos criterios de centralidad. En la tabla 5.1, mostramos el perfil de los usuarios que son relevantes si consideramos las medidas de centralidad comentadas en la secci´ on anterior en distintos momentos del evento. Hemos considerado los siguientes tipos de perfiles: celebrities (i.e., actores, presentadores, participantes de un 48 5.4. An´ alisis de eventos T IN DEGREE OUT DEGREE PAGE RANK EIGENVECTOR CLOSENESS ECCENTRICITY BETWEENESS INICIO CUENTAS OFICIALES USUARIOS AN ´ ONIMOS CUENTAS OFICIALES CUENTAS OFICIALES CUENTAS OFICIALES CUENTAS OFICIALES USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS CELEBRITIES USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS CUENTAS OFICIALES USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS CELEBRITIES USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS CUENTAS OFICIALES USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS CUENTAS OFICIALES USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS MEDIO CUENTAS OFICIALES USUARIOS AN ´ ONIMOS CUENTAS OFICIALES CUENTAS OFICIALES CUENTAS OFICIALES CUENTAS OFICIALES USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS CELEBRITIES USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS CELEBRITIES USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS CELEBRITIES CUENTAS OFICIALES CUENTAS OFICIALES USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS CUENTAS OFICIALES CELEBRITIES USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS CUENTAS OFICIALES CELEBRITIES M. COMUNICACI ´ ON CELEBRITIES USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS FINAL USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS M. COMUNICACI ´ ON USUARIOS AN ´ ONIMOS CUENTAS OFICIALES CUENTAS OFICIALES USUARIOS AN ´ ONIMOS CUENTAS OFICIALES USUARIOS AN ´ ONIMOS CUENTAS OFICIALES CUENTAS OFICIALES USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS M. COMUNICACI ´ ON USUARIOS AN ´ ONIMOS M. COMUNICACI ´ ON M. COMUNICACI ´ ON CUENTAS OFICIALES CUENTAS OFICIALES USUARIOS AN ´ ONIMOS M. COMUNICACI ´ ON USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS M. COMUNICACI ´ ON USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS USUARIOS AN ´ ONIMOS CUENTAS OFICIALES CUENTAS OFICIALES USUARIOS AN ´ ONIMOS Tabla 5.1: Evoluci´ on de las propiedades estructurales a nivel de nodo durante el evento #MuereBarber´ aARV. Indica los 5 perfiles que tienen valores de centralidad m´ as altos teniendo en cuenta distintos criterios de centralidad. concurso, personajes pol´ ıticos, etc.), cuentas oficiales (i.e., cuentas asociadas a programas de TV, cuentas oficiales de un evento, etc.), cuentas de grupos (i.e., club de fans, asociaciones, partidos pol´ ıticos, etc.), medios de comunicaci´ on (i.e., blogs, bloggers, radios, televisiones, periodistas, etc), y usuarios an´ onimos. En el evento #MuereBarber´ aARV se observa que las cuentas oficiales asociadas al programa son las m´ as relevantes en cuanto a grado de entrada, page rank, eigenvector, excentricity. Esto refleja que las cuentas oficiales no son cuentas que generen conversaciones con otros usuarios, sino que son cuentas que reciben muchos mensajes de usuarios an´ onimos y s´ olo hacen referencia a otras cuentas de personajes o grupos relevantes. Las cuentas de personajes relevantes juegan un papel importante durante el evento si tenemos en cuenta los mensajes recibidos de otras cuentas (in-degree) porque est´ an relacionados con otras cuentas importantes (i.e., alto valor de page-rank e eigenvector). Los usuarios an´ onimos en este evento tambi´ en juegan un papel principal en la generaci´ on de mensajes (i.e., un alto valor en el grado de salida) y en la conexi´ on de comunidades diferentes (i.e., betweenness). 5.4.2 Evento #ChampionsLeague Este evento de la jornada de Liga de Campeones tuvo lugar el 23 de noviembre, donde se hicieron seis partidos de forma simult´ anea en el que intervinieron varios equipos de futbol. Bas´ andonos en la evoluci´ on de las propiedades estructurales, podemos observar que el comportamiento de los usuarios durante el evento #ChampionsLeague fue variable en el tiempo. La figura 5.5 muestra la evoluci´ on del di´ ametro, el grado medio de conexi´ on y la longitud del camino medio. Al principio del evento, el di´ ametro de la red es dos. Que la mayor distancia entre dos usuarios de la red sea tan baja indica que hay nodos que est´ an conectados a muchos otros nodos de la red, esto hace que disminuyan las distancias entre ´ estos. El camino medio de 5. Caso de Estudio 49 Figura 5.5: Evoluci´ on de las propiedades estructurales a nivel de red: longitud del camino medio, grado medio de conexi´ on y di´ ametro de la red. Evento #ChampionsLeague Figura 5.6: Evoluci´ on de las propiedades estructurales a nivel de red: modularidad. Evento #ChampionsLeague la red crece en la primera mitad del evento (a medida que crece la red) y se mantiene constante hasta finalizar. Esta evoluci´ on en la estructura indica que muchos usuarios se unieron al evento desde T a T+1. En el intervalo entre T+1 a T+2 el aumento m´ as significativo del n´ umero de mensajes (i.e., mensajes) que de usuarios hizo que el camino medio se mantuviera constante. Un valor tan bajo tiene relaci´ on con que la mayoria de los usuarios est´ an conectados a cuentas oficiales y medios de comunicaci´ on que hace de hub y acortan los caminos entre los usuarios. El grado de conexi´ on no evoluciona de forma significativa. Mantiene un valor medio alrededor de 1.4, lo que indica que un usuario participa en la red con uno o dos mensajes como mucho. La figura 5.6 nos muestra la evoluci´ on de la modularidad. Podemos ver que ´ esta es casi constante y al tener un valor alto indica que el nivel de cohesi´ on en las comunidades detectadas 56 6.2. Trabajo Futuro de red etiquetadas temporalmente. Finalmente, bas´ andonos en medidas proporcionadas en el ´ area de redes complejas hemos analizado varios eventos en la red social online Twitter. Este an´ alisis lo hemos llevado a cabo teniendo en cuenta la evoluci´ on de las propiedades a nivel de red y a nivel de nodo. Como resultado de este an´ alisis, hemos detectado patrones de evoluci´ on de la red y las caracter´ ısticas estructurales comunes, as´ ı como las diferencias entre los distintos eventos. Durante el desarrollo de este trabajo se han alcanzado los siguientes objetivos: •La propuesta de un dise˜ no de SMA para el an´ alisis de eventos en redes sociales. Se ha descrito la arquitectura propuesta desde su dimensi´ on funcional, estructural, y din´ amica. •Se ha desarrollado un framework basado en tecnolog´ ıas de agentes para el an´ alisis de la actividad de los usuarios en las redes sociales online durante un evento. El framework est´ a basado en una plataforma de SMA Magentix2. •Se ha establecido un tipo de red de informaci´ on etiquetada temporalmente que representa los flujos de informaci´ on durante un evento. •Se ha realizado un an´ alisis de varios casos de estudio de eventos donde se han extra´ ıdo elementos significativos que nos han permitido entender mejor lo que estaba sucediendo en la comunicaci´ on entre usuarios durante el evento. 6.2 Trabajo Futuro El trabajo presentado compone las bases para continuar en esta l´ ınea de investigaci´ on. Entre algunos de los trabajos futuros que se contemplan est´ an: (i) integrar m´ as redes sociales online como pueden ser Instagram o Facebook que permita hacer un an´ alisis de redes multicapa; (ii) mejorar la visualizaci´ on de las redes de interacci´ on que contienen un alto n´ umero de nodos y enlaces y que permita aplicar filtros para centrar la atenci´ on en determinadas partes de la red; (iii) incorporar nuevas medidas para el an´ alisis de las interacciones teniendo en cuenta el dominio; (iv) realizar una interfaz web que permita una mejor visualizaci´ on de los an´ alisis desde cualquier tipo de dispositivo. 6. Conclusiones y trabajo futuro 57 6.3 Publicaciones Como resultado del trabajo presentado se han realizado dos publicaciones cient´ ıficas. La primera se ha publicado en un track de Agentes Inteligentes dentro de la Conferencia Internacional de Modelos de Softcomputing en Entornos Industriales. El segundo trabajo ha sido publicado en una revista con un JCR de 1.630 (Q2). •E. del Val, C. Mart´ ınez, and V. Botti. Analyzing users’ activity in online social networks over time through a multi-agent framework. Soft Computing 20.11 (2016): 4331-4345. •E. del Val, C. Mart´ ınez and V. Botti. A Multi-agent Framework for the Analysis of Users Behavior over Time in On-Line Social Networks 10th International Conference on Soft Computing Models in Industrial and Environmental Applications pp. 191-201. (2015) Bibliography [1] AHN, Y.-Y., HAN, S., KWAK, H., MOON, S., AND JEONG, H. Analysis of topological characteristics of huge online social networking services. In Proceedings of the 16th international conference on World Wide Web (2007), ACM, pp. 835–844. [2] ALBERO-GABRIEL, J. Twitter,# primaveravalenciana y generaci´ on de noticias. Cuadernos de Informaci´ on y Comunicaci´ on 19 (2014), 253. [3] ALDHOUS, P. The stem cell wars: data, methods and results. https://www.newscientist.com/article/ dn18996-the-stem-cell-wars-data-methods-and-results/, 2016. [Online; accessed 22-Nov-2016]. [4] ARGENTE, E., BOTTI, V., AND JULIAN, V. Gormas: An organizational-oriented methodological guideline for open mas. In International Workshop on Agent-Oriented Software Engineering (2009), Springer, pp. 32–47. [5] BARABASI, A. L., AND ALBERT, R. Emergence of scaling in random networks. Science (New York, N.Y.) 286 (1999), 509–512. [6] BASTIAENSENS, S., VANDEBOSCH, H., POELS, K., VAN CLEEMPUT, K., DESMET, A., AND DEBOURDEAUDHUIJ, I. Cyberbullying on social network sites. an experimental study into bystanders’ behavioural intentions to help the victim or reinforce the bully. Computers in Human Behavior 31 (2014), 259–271. [7] BENEVENUTO, F., RODRIGUES, T., CHA, M., AND ALMEIDA, V. Characterizing user behavior in online social networks. In Proceedings of the 9th ACM SIGCOMM conference on Internet measurement conference (2009), ACM, pp. 49–62. 59 60 Bibliograf´ ıa [8] BORGE-HOLTHOEFER, J., RIVERO, A., GARC´ IA, I., CAUH ´ E, E., FERRER, A., FERRER, D., FRANCOS, D., I ˜ NIGUEZ, D., P´ EREZ, M. P., RUIZ, G., ET AL. Structural and dynamical patterns on online social networks: the spanish may 15th movement as a case study. PLoS One 6, 8 (2011). [9] BORONDO, J., MORALES, A., LOSADA, J. C., AND BENITO, R. M. Characterizing and modeling an electoral campaign in the context of twitter: 2011 spanish presidential election as a case study. Chaos: an interdisciplinary journal of nonlinear science 22, 2 (2012), 023138. [10] CARMEL, D., ZWERDLING, N., GUY, I., OFEK-KOIFMAN, S., HAR’EL, N., RONEN, I., UZIEL, E., YOGEV, S., AND CHERNOV, S. Personalized social search based on the user’s social network. In Proceedings of the 18th ACM conference on Information and knowledge management (2009), ACM, pp. 1227–1236. [11] CASTELLS, M., AND HERN ´ ANDEZ, M. Redes de indignaci´ on y esperanza: los movimientos sociales en la era de Internet. Alianza Editorial, 2012. [12] CUSICK, M. V. A.-L. B. M. Mapping the Human ‘Diseasome’. http: //www.nytimes.com/interactive/2008/05/05/science/20080506_ DISEASE.html, 2008. [Online; accessed 22-Nov-2016]. [13] DAFT, R. Organization theory and design. Cengage learning, 2006. [14] DEL VAL, E., PALANCA, J., AND REBOLLO, M. U-Tool: A Urban-Toolkit for enhancing city maps through citizens’ activity. In 14th International Conference on Practical Applications of Agents and Multi-Agent Systems (2016), pp. 243–246. [15] DEL VAL, E., REBOLLO, M., AND BOTTI, V. Does the type of event influence how user interactions evolve on Twitter? PLOS ONE 10(5) (2015), 1–32. [16] EBEL, H., MIELSCH, L.-I., AND BORNHOLDT, S. Scale-free topology of e-mail networks. Physical review E 66, 3 (2002), 035103. [17] EGGHE, L., AND ROUSSEAU, R. Introduction to informetrics: Quantitative methods in library, documentation and information science. [18] EUROSTAT. Information society statistics - households and individuals. http://ec.europa.eu/eurostat/statistics-explained/index. php/Information_society_statistics_-_households_and_ individuals, 2014. [Online; accessed 19-May-2016]. Bibliograf´ ıa 61 [19] FERBER, J., GUTKNECHT, O., AND MICHEL, F. From agents to organizations: an organizational view of multi-agent systems. In International Workshop on Agent-Oriented Software Engineering (2003), Springer, pp. 214–230. [20] FOSTER, I., KESSELMAN, C., AND TUECKE, S. The anatomy of the grid: Enabling scalable virtual organizations. International journal of high performance computing applications 15, 3 (2001), 200–222. [21] GLEAMVIZ. gleamviz: The Global Epidemic and Mobility Model. http://www. gleamviz.org/gleam-in-detail/, 2010. [Online; accessed 22-Nov-2016]. [22] GOLBECK, J., ROBLES, C., AND TURNER, K. Predicting personality with social media. In CHI’11 extended abstracts on human factors in computing systems (2011), ACM, pp. 253–262. [23] H´ IPOLA, P., AND VARGAS-QUESADA, B. Agentes inteligentes: definici´ on y tipolog´ ıa: los agentes de la informaci´ on. El profesional de la informaci´ on 8, 4 (1999), 13–21. [24] H´ IPOLA, P., VARGAS-QUESADA, B., AND MONTES, A. Descripci´ on y evaluaci´ on de agentes multibuscadores. El profesional de la informaci´ on 8, 11 (1999). [25] HUBERMAN, B. A. The laws of the Web: Patterns in the ecology of information. mit Press, 2001. [26] HUBERMAN, B. A., ROMERO, D. M., AND WU, F. Social networks that matter: Twitter under the microscope. Available at SSRN 1313405 (2008). [27] KLEINBERG, J. Small-world phenomena and the dynamics of information. In In Advances in Neural Information Processing Systems (NIPS) 14 (2001), MIT Press, p. 2001. [28] KLEINBERG, J. Complex networks and decentralized search algorithms. In In Proceedings of the International Congress of Mathematicians (ICM (2006). [29] KLEINBERG, J. M. Navigation in a small world. Nature 406 (2000). [30] KUMAR, R., NOVAK, J., AND TOMKINS, A. Structure and evolution of online social networks. In Link mining: models, algorithms, and applications. Springer, 2010, pp. 337– 357. [31] LESKOVEC, J., ADAMIC, L. A., AND HUBERMAN, B. A. The dynamics of viral marketing. ACM Transactions on the Web (TWEB) 1, 1 (2007), 5. 62 Bibliograf´ ıa [32] LOHR, S. The age of big data. New York Times 11 (2012). [33] L ´ OPEZ FOGU ´ ES, R. Magentix2: Una nueva plataforma para sistemas multiagente abiertos. [34] LOTAN, G., GRAEFF, E., ANANNY, M., GAFFNEY, D., PEARCE, I., ET AL. The arab spring— the revolutions were tweeted: Information flows during the 2011 tunisian and egyptian revolutions. International journal of communication 5 (2011), 31. [35] MISLOVE, A., MARCON, M., GUMMADI, K. P., DRUSCHEL, P., AND BHATTACHARJEE, B. Measurement and analysis of online social networks. In Proceedings of the 7th ACM SIGCOMM conference on Internet measurement (2007), ACM, pp. 29–42. [36] NEWMAN, M. High school dating. http://www-personal.umich.edu/ ˜mejn/networks/, 2004. [Online; accessed 22-Nov-2016]. [37] NEWMAN, M., BARABASI, A.-L., AND WATTS, D. J. The structure and dynamics of networks. Princeton University Press, 2011. [38] NEWMAN, M. E. The structure and function of complex networks. SIAM review 45, 2 (2003), 167–256. [39] OUYANG, M., ZHAO, L., HONG, L., AND PAN, Z. Comparisons of complex network based models and real train flow model to analyze chinese railway vulnerability. Reliability Engineering & System Safety 123 (2014), 38–46. [40] PAGANI, G. A., AND AIELLO, M. The power grid as a complex network: a survey. Physica A: Statistical Mechanics and its Applications 392, 11 (2013), 2688–2700. [41] PE˜ NA-L ´ OPEZ, I., CONGOSTO, M., AND ARAG ´ ON, P. Spanish indignados and the evolution of 15m: towards networked para-institutions. Big Data: Challenges and Opportunities (2013), 25–26. [42] PERIANES-RODR´ IGUEZ, A., OLMEDA-G ´ OMEZ, C., AND DE-MOYA-ANEG ´ ON, F. Introducci´ on al an´ alisis de redes. El profesional de la informaci´ on (2008). [43] PERLIGER, A., AND PEDAHZUR, A. Social network analysis in the study of terrorism and political violence. PS: Political Science & Politics 44, 01 (2011), 45–50. [44] REBOLLO PEDRUELO, M., DEL VAL NOGUERA, E., CARRASCOSA CASAMAYOR, C., PALOMARES CHUST, A., AND PEDROCHE S´ ANCHEZ, F. Consensus over multiplex network to calculate user influence in social networks. In International Journal of Complex Systems in Science (2013), vol. 3, Interlude, pp. 71–75. Bibliograf´ ıa 63 [45] ROMERO, D. M., MEEDER, B., AND KLEINBERG, J. Differences in the mechanics of information diffusion across topics: idioms, political hashtags, and complex contagion on twitter. In Proceedings of the 20th international conference on World wide web (2011), ACM, pp. 695–704. [46] SMITH, M. A., RAINIE, L., SHNEIDERMAN, B., AND HIMELBOIM, I. Mapping twitter topic networks: From polarized crowds to community clusters. Pew Research Center 20 (2014). [47] TRAVERS, J., AND MILGRAM, S. An experimental study of the small world problem. Sociometry (1969), 425–443. [48] TWITTER. Twitter developers. https://dev.twitter.com/, 2016. [Online; accessed 19-May-2016]. [49] WATTS, D. J., DODDS, P. S., AND NEWMAN, M. E. J. Identity and search in social networks. [50] WATTS, D. J., AND STROGATZ, S. H. Collective dynamics of ’small-world’ networks. Nature 393 (1998), 440–442. [51] ZANIN, M., AND LILLO, F. Modelling the air transport with complex networks: A short review. The European Physical Journal Special Topics 215, 1 (2013), 5–21. 64 Bibliograf´ ıa