Generador de Grafos Multi-relacionales a partir de redes sociales

GENERADOR DE GRAFOS MULTI-RELACIONALES A PARTIR DE REDES SOCIALES

A MULTI-RELATIONAL GRAPH GENERATOR BASED-ON SOCIAL NETWORKS DATA

Pedro Almagro Blanco ¹, Sonia Ordoñez Salinas ²

¹ Grupo de Modelado de Sistemas Complejos. Universidad Central de Ecuador.

² Grupo de Investigación Gesdatos. Universidad Distrital Francisco José de Caldas.

lpalmagroblanco@gmail.com, sordonez@udistrital.edu.co

Recibido: 07/11/2013 - Aceptado: 30/05/2014

Resumen

La herramienta presentada en este artículo, CorpuRed, permite obtener datos de plataformas sociales en línea para ser utilizados en proyectos de investigación que requieran de información sobre el comportamiento social en Internet. La forma de obtener dichos datos depende ligeramente de cada plataforma (se muestra el caso particular de Facebook), y posteriormente son almacenados en una base de datos en grafo que será accesible a través de una API bajo una licencia académica.

Palabras clave: Redes Sociales en Línea, Grafos Multi-relacionales.

Abstract

The tool introduced in this paper, CorpuRed, allows obtaining a dataset from online social networks that can be used for research projects that require information about social behaviour on Internet. The way to obtain such data is slightly platform dependent (the Facebook case is described) and they are stored in a graph database that will be accessible through an academic license API.

Keywords: Online Social Networks, Multi-Relational Graphs.

1. INTRODUCCIÓN

A partir del inicio de Facebook en el 2006 en la universidad de Harvard por Mark Zuckerberg, la creación e incidencia de las relaciones virtuales se ha incrementado vertiginosamente. A diferencia de los correos electrónicos y las salas de chat, las redes sociales en línea facilitan el establecimiento de amistades nuevas, y la conexión entre personas (o entidades) por sus gustos, por terceros y por comentarios, entre otros. Según cifras oficiales de la propia compañía, para el 2013 [1], Facebook cuenta con 1.150 millones de usuarios activos al mes en todo el mundo; 699 millones de usuarios entran a la red social cada día; cada usuario en promedio tiene relación con 89 páginas y grupos, con 141.5 amigos y gasta 20 minutos al día en navegar dentro de la red. Facebook cuenta en la actualidad con aproximadamente 50 millones de páginas, 240 millones de fotografías y 110 millones de canciones y álbumes compartidos. Estas cifras ponen de manifiesto la riqueza del conocimiento inmerso dentro de estas redes, así como la necesidad de teorías que puedan modelar dichas relaciones, entre las cuales, los grafos muti-relacionales parecen disponer de las características más adecuadas.

A pesar de que una red social como Facebook contiene una gran cantidad de información útil para la investigación, ésta no está disponible como se quisiera para la academia. Si bien estas redes sociales incluyen algunas herramientas dirigidas al público para interactuar con la información almacenada en su red cercana, no existe un aplicativo que permita obtener grandes conjuntos de datos sociales interrelacionados para ser utilizados en tareas de investigación como, por ejemplo, el análisis de comportamientos con intenciones delictivas, emergencia de movimientos sociales, análisis de sentimientos, etc. En este artículo se describe el desarrollo de un aplicativo que pretende cubrir esta carencia.

Para describir el trabajo desarrollado se presenta en el siguiente apartado, y a modo de contextualización, una visión general de los conceptos principales relacionados con las redes sociales, y el aparato matemático utilizado para la gestión computacional de tales de redes. Posteriormente, pasamos a describir las funcionalidades de la herramienta, la arquitectura utilizada, el modelo lógico usado internamente para el almacenamiento y manipulación de los datos, así como ejemplos de redes obtenidas por la herramienta. Finalmente, en el apartado 4, se muestran los primeros resultados y el trabajo futuro planificado.

2. TRABAJO RELACIONADO

A continuación se presentan los conceptos fundamentales que permiten contextualizar el trabajo desarrollado. Por una parte, y con el fin de fijar el ámbito de estudio, se incluyen algunas definiciones básicas sobre redes sociales. Por otra parte, se incluyen los fundamentos de los Grafos Multi-relacionales y se muestran sus bondades y características generales. Este marco teórico se vuelve aún más robusto en el momento en el que existen en el panorama de desarrollo actual herramientas de software que permiten una implementación práctica de los mismos.

2.1. Redes Sociales

Una red, o grafo, es una estructura matemática que contiene un conjunto de objetos, llamados habitualmente nodos o vértices, conectados binariamente entre sí por medio de conexiones, llamadas aristas o enlaces, que pueden ser dirigidas (en caso de que sea importante saber en qué nodo nace la conexión) o no dirigidas (en caso contrario). Desde un punto de vista matemático, los grafos disponen de una robusta teoría, la Teoría de Grafos [15], que facilita su uso como herramienta de análisis y representación de la información.

En el caso particular de que las redes reflejen una realidad social, los nodos pueden representar personas o entidades relacionadas con sus contextos, y las conexiones representarán relaciones sociales existentes entre ellos (amistad, parentesco, membresía, afinidad, etc.). A pesar de que intuitivamente las redes sociales se asemejan a los grafos matemáticos, es más habitual que en ellas se trabaje con distintos tipos de relaciones [2], y no sólo con un tipo de conexión predefinida. Es por ello que en los últimos años se ha hecho necesaria la extensión del concepto de grafo, así como de la teoría asociada, para poder dar cabida a este tipo de redes con características más ricas que las estructuras clásicas.

Desde un punto de vista analítico, las diferentes relaciones que se pueden presentar en una red social permiten su uso en áreas de investigación interdisciplinares, ya que posibilitan el reconocimiento de patrones de comportamiento tanto a nivel individual (micro) como a nivel de la red global (macro), y proporcionan interesantes interpretaciones en ámbitos tan diversos como son el político, social, cultural, económico, educativo, entre otros [16, 17].

2.2. Grafos Multi-relacionales

Para que sea posible reconocer y analizar las interrelaciones y patrones existentes en una red social es necesario representar dicha red a través de estructuras computacionales que aseguren la solidez de los resultados obtenidos. Debido al tamaño y características de las redes sociales, es imprescindible que la representación elegida permita, además de organizar la información, proporcionar un tratamiento computacional escalable que nos asegure el éxito de nuestra tarea. La dificultad del problema que se plantea no responde únicamente a la cantidad de información que se manipula, sino también a la complejidad subyacente de los datos que viene dada por la riqueza de las interrelaciones que presentan. La tarea de encontrar patrones que reflejen relaciones interesantes y no triviales a partir de estos grandes conjuntos de datos adquiere una importancia fundamental.

Hemos de considerar que en las redes sociales, además de la información propia de la red de individuos y sus relaciones, aparece el contexto social en el que éstos se inscriben, por lo que junto a la capa de individuos coexiste la capa de elementos socio-culturales más diversa con la que se relacionan, y que tiene una carga semántica muy elevada y altamente no estructurada.

Cuando la información de la que se dispone es muy rica, tanto en su contenido semántico como en sus relaciones, una opción es modelarla como una red semántica, que consiste en un grafo etiquetado y dirigido en el que las etiquetas de los nodos y aristas del grafo representan, respectivamente, los tipos de entidades y tipos de relaciones existentes entre los datos. Este proceso de etiquetado en las relaciones del grafo obliga a la generación de un nuevo concepto matemático que sea capaz de modelar el problema, y es por ello que aparecen en escena los Grafos Multi-relacionales [6].

La diferencia entre un grafo clásico (que se podría llamar uni-relacional) y un grafo multi-relacional no es menor, ya que la existencia de tipos de relaciones no sólo proporciona un modelo más rico, sino que también actúa como una puerta de entrada a la inferencia lógica haciendo uso de Ontologías y Mapas de Tópicos (que pueden entenderse como estructuras matemáticas que proporcionan relaciones lógicas robustas a la información semántica modelada en la red).

A cambio de la riqueza obtenida al permitir la multi-relacionalidad en los grafos, se pierden algunos de los resultados y herramientas clásicas que nos permiten realzar análisis exhaustivos de los mismos, por lo que se abre una vía nueva de la Teoría de Grafos Multi-relacionales que exige el establecimiento de nuevos resultados y herramientas de análisis.

Desde un punto de vista analítico, se pueden extender de varias formas las medidas ya definidas en la teoría clásica de grafos (tales como grado, centralidad o betweenness) a los grafos multi-relacionales, de forma que podemos utilizar las metodologías ya desarrolladas en los primeros para extraer información de los segundos. Por ejemplo en el caso del grado, que en la teoría clásica nos indica en qué cantidad de relaciones está participando un nodo dado, tendríamos varias formas posibles de extenderla: una primera opción sería contar por separado las relaciones de cada tipo en las que participa el nodo, y construir un vector de grados en el que cada valor del vector indique el grado de ese nodo para cada tipo de relación permitida; una segunda opción sería asignar a cada tipo de relación un peso (que indicaría su importancia en el análisis), para calcular posteriormente el grado como la suma ponderada de los diferentes grados para cada tipo de relación.

Por otra parte, al surgir nuevas necesidades en un panorama por ahora casi inexplorado, es probable que haya que introducir nuevas medidas, no extensiones de las clásicas, que sean capaces de reflejar la riqueza de interacciones que las nuevas estructuras tienen.

2.3. Extracción de grafos Multi-relacionales a partir de redes sociales

Dentro de las aplicaciones que utilizan grafos para representar el contenido de la web destaca la presentada recientemente por Google, Knowledge Graph [3], donde afirman que el futuro de las búsquedas será a través de un grafo de conocimiento, creado parcialmente por las interacciones sociales de los usuarios del servicio. Dicha herramienta permitirá navegar entre los diferentes sitios, personajes, eventos y objetos haciendo uso de un grafo multi-relacional, y no por medio de la selección entre una lista de enlaces tal y como se hace actualmente. Para esta aplicación, en la actualidad Google ofrece 500 millones de tópicos y más de 3.500 millones de hechos y relaciones acerca de ellos [4].

La construcción de grafos a partir de información disponible en la web se puede apreciar no sólo en la información gestionada por los buscadores, sino también en muchos otros repositorios de información disponibles en Internet. Por ejemplo, en [7] se construye un grafo a partir de los mensajes de correo electrónico de un grupo de usuarios; mientras que en [8] se representa por medio de un grafo dirigido la interacción entre los diferentes servicios web que intervienen cuando un usuario hace una petición a través de uno de ellos.

Sin embargo, la tarea de extraer información de estos servicios y estructurarla adecuadamente no siempre es sencilla. En el más favorable de los escenarios el propio servicio ofrece las herramientas para poder extraer secciones locales, más o menos limpias, de la información y es el investigador el que debe seguir un protocolo para darle la estructura que considere más adecuada para su análisis. En los menos favorables no existen tales herramientas de extracción, ni siquiera a nivel local, y han de desarrollarse web crawlers que permitan ir recopilando grandes cantidades de datos que después han de ser filtrados y estructurados.

Precisamente la ausencia de este tipo de herramientas de extracción es la que motiva la construcción del aplicativo que se describe en las siguientes secciones, con referencia concreta a la red social de Facebook.

A diferencia de otras herramientas como [18, 19] en las que se recopilan datos de redes sociales concretas, nuestro sistema permite reutilizar la capa de almacenamiento para adaptarla dinámicamente a las características propias de cada plataforma de red social en línea, extendiendo el esquema existente sin necesidad de hacer ningún cambio estructural en los datos (la adición de nuevos tipos y relaciones es incremental), esto permite hacer unificación (merging) de los datos de un mismo individuo por agregación de información de las diferentes plataformas en las que participa.

3. LA HERRAMIENTA CORPURED

A continuación presentamos la aplicación que se ha desarrollado para extraer conjuntos de datos en forma de grafo multi-relacional, ejemplificado con el caso específico de la red social Facebook. Debido a las características del acceso que ofrece el servicio, el grafo se construye a partir de entornos locales de cada usuario que haga uso de la aplicación. Nuestra herramienta reconoce los puntos de conexión entre las distintas redes personales a las que tiene acceso y va construyendo una red global, de forma que finalmente disponemos de un grafo muy rico en el que se pueden hacer estudios transversales y no únicamente relacionados con la ego-red de cada usuario.

3.1. Funcionalidad

El objetivo de la aplicación desarrollada es ofrecer una interfaz sencilla que permita extraer conjuntos de datos sociales para su posterior uso por parte de la comunidad académica.

Uno de los problemas principales que se han encontrado a la hora de extraer el conjunto global de datos sociales es que servicios como Facebook limitan las consultas y sólo permiten acceder a los datos de los amigos del usuario que esté utilizando el sistema. Por ello, el desarrollo se enfocó a extraer información del círculo del usuario que ejecuta la aplicación, que es almacenada en una base de datos orientada a grafos.

Es importante señalar que la herramienta CorpuRed recopila la información disponible en el momento de la extracción. Publicaciones y actualizaciones futuras no quedarán registradas y es necesaria una nueva extracción para recopilarlas.

3.2. Arquitectura y Modelo de Datos

La herramienta CorpuRed ha sido implementada haciendo uso del lenguaje de programación Javascript [9]. Cuando un usuario accede a la aplicación con su cuenta de Facebook, ésta extrae la información de su círculo social y la añade a la base de datos en grafo almacenada en un servidor (ver figura 1). La tecnología utilizada para esta tarea ha sido Neo4j [10].

La comunicación entre CorpuRed y Facebook se hace a través del lenguaje de consulta FQL (Facebook Query Lenguage) [11] y el SDK de Facebook para Javascript [12]. La comunicación entre la aplicación y el servidor Neo4j se hace a través del lenguaje de consulta Cypher [13] y la API REST de Neo4j [14].

Gracias a la arquitectura y las tecnologías escogidas, y debido a que la mayoría de las plataformas de redes sociales en línea suministran una API de acceso a sus datos, CorpuRed se puede ampliar fácilmente incluyendo nuevas redes sociales de las que extraer datos sin necesidad de grandes modificaciones. Para ello solo sería necesario modificar la capa de comunicación de la aplicación con la red social en línea, ya que la capa que interactúa con la Base de Datos permanecería intacta. Por ejemplo, la red social en línea Twitter suministra una REST API [21] que sería fácilmente integrable en CorpuRed.

Partiendo del modelo de datos de Facebook, en nuestra primera versión se ha optado por un esquema de datos en el que contemplamos cuatro tipos de nodos (user, status, comment y photo) y seis tipos principales de relaciones (family, wrote_comment, wrote_status, likes, appears_in, published_photo, comment_on) como se observa en la figura 2. La relación de tipo family a su vez se subdivide en 22 tipos concretos de relaciones dentro del ámbito familiar. Este esquema permite capturar con fidelidad el contenido semántico de los datos extraídos de la red social en línea.

La forma de orquestar la construcción de la red global a partir de las redes individuales es a través de la detección de identificadores comunes: las redes sociales en línea utilizan identificadores únicos para cada elemento (usuarios, páginas, fotografías, comentarios,…), y CorpuRed, haciendo uso de estos identificadores, es capaz de detectar que dos elementos que provienen de dos extracciones independientes representan el mismo nodo, de esta forma se efectúa la unión entre redes locales a la vez que se evita la duplicación de información.

Con el fin de lograr un equilibrio entre el tiempo de extracción y la riqueza de los datos obtenidos, CorpuRed extrae los últimos n status y las últimas m fotografías de cada individuo en el entorno del usuario que ejecuta la aplicación (estos valores, que pueden ser ajustados por el administrador de la herramienta, tienen un valor por defecto de 15). El algoritmo que se sigue para este proceso se detalla en la tabla 1.

4. RESULTADOS PRELIMINARES

Siguiendo el algoritmo de agregación de datos mostrado en la tabla 1, presentamos un ejemplo de dos redes locales extraídas mediante la herramienta Corpured y el resultado de la unión de ambas en la red global.

Como se puede observar, ambas redes comparten un nodo, el user con id 01413275. Aplicando el proceso explicado en el algoritmo anterior obtendríamos la red global mostrada en la figura 4.

Durante una primera fase de pruebas realizada sobre 5 usuarios, se han recopilado aproximadamente 45.000 nodos (contabilizando usuarios, fotografías, estados y comentarios), 75.000 relaciones y 150.000 propiedades. Recordemos que por cada usuario que ejecuta el aplicativo se pueden extraer hasta n status y m fotografías por cada uno de sus amigos, que pueden llevar asociados comentarios, likes, etiquetas y los usuarios que los han generado. Esto significa que por cada usuario se añade una media de 10.000 nodos, lo que explica el elevado crecimiento en el número de datos almacenados. Por supuesto, si los usuarios comparten muchos nodos en sus círculos, la tasa de crecimiento en el número de nodos será más moderada pero la red seguirá creciendo en número de relaciones, aumentando así el grado de interconexión.

5. Conclusiones y trabajo futuro

En este artículo hemos presentado un aplicativo, Corpured, que recopila de manera incremental una colección de datos sociales extraída a partir de los círculos de los usuarios que voluntariamente ceden sus datos. La colección se almacena siguiendo un modelo de Grafo Multi-relacional sobre una plataforma (Neo4J) que permite realizar consultas complejas para buscar patrones de comportamiento. El motor de consultas que permite estas búsquedas, Cypher, es el mismo que el utilizado en la comunicación de CorpuRed con la base de datos durante el almacenamiento.

Este aplicativo es el primer paso de un proyecto de investigación que tiene como objetivo analizar conjuntos de datos sociales para extraer patrones a través de diferentes técnicas de minería de datos. Una de las vías por las que se plantea mejorar CorpuRed es mediante la conexión con otras plataformas de redes sociales en línea. Como hemos comentado, para ello basta realizar modificaciones menores en el esquema de Grafo Multi-relacional que sirve de soporte a la base de datos, junto con la creación de un protocolo de comunicación adaptado a la plataforma. De esta forma, cuando sea posible identificar elementos comunes, se obtendrían relaciones cruzadas a partir de la información social almacenada en distintas plataformas.

Confiamos en que un aplicativo de este tipo sea de alto valor en el mundo académico al proporcionar de forma relativamente sencilla y bajo una licencia abierta (tras un proceso de anonimización) un gran conjunto de datos que sirva de soporte para investigaciones en muy diversas áreas de conocimiento.

Agradecimientos

El trabajo se realizó durante la estancia de investigación del primer autor en el grupo Gesdatos de la Universidad Distrital F.J.C de Bogotá, Colombia.

Referencias Bibliográficas

1. Juan Luis Bermúdez “Infografía actual con algunas estadísticas curiosas de Facebook,” 4 Sept. 2013. [Blog entry]. Soft and Apps Blog. http://www.softandapps.info/2013/09/04/infografia-actual-con-algunas-estadisticas-curiosas-de-facebook , visitado sep 21 2013
2. Hanneman Robert A. and Riddle Mark. "Introduction to social network methods," 20015, Riverside, CA: University of California, Riverside (publicado en formato digital en http://faculty.ucr.edu/~hanneman/), visitado sep 12 2013
3. Google. "El grafo del conocimiento." google.com [Online]. http://www.google.com/insidesearch/features/search/knowledge.html, visitado sep 21 2013
4. Google "Introducing Knowledge Graph: thing, not strings." 16 May 2012 [Blog entry]. Google Official Blog. http://googleblog.blogspot.com/2012/05/introducing-knowledge-graph-things-not.html
5. Badia A, Kantardzic M. "Graph building as a mining activity: finding links in the small." LinkKDD '05: Proceedings of the 3rd international workshop on Link discovery, ACM, 2005, 17-24.
6. Rodriguez, M. A.; Shinavier, J. "Exposing multi-relational networks to single-relational network analysis algorithms." Journal of Informetrics, vol. 4, no. 1, pp.2941, 2009.
7. Laclavík M, Dlugolinský S, Šeleng M, Ciglan M, Hluchý L. "Emails as graph: relation discovery in email archive." Proceedings of the 21st international conference companion onWorld Wide Web, 2012
8. Chaker Ben M, Fathia B, Hajer A, Houda S "Towards a Graph-Based Approach for Web Services Composition." IJCSI Volume 10, Issue 1, January 2013 , Page 351
9. Mozzila. "JavaScript reference," developer.mozilla.org. [Online] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference , visitado sep 21 2013
10. Neo4j. "Neo4j Documentation," neo4j.org. [Online] http://docs.neo4j.org/ , visitado sep 21 2013
11. Facebook. "FQL reference," facebook.com [Online] https://developers.facebook.com/docs/reference/fql/a>, visitado sep 21 2013
12. Facebook. "Facebook SDK for JavaScript," facebook.com [Online] https://developers.facebook.com/docs/reference/javascript/ , visitado sep 21 2013
13. Neo4j. "Cypher Query Language," neo4j.org [Online] http://docs.neo4j.org/chunked/milestone/cypher-query-lang.html , visitado sep 2013
14. Neo4j. "REST API," neo4j.org [Online] http://docs.neo4j.org/chunked/milestone/rest-api.html , visitado sep 21 2013
15. Albert-László Barabási, "Linked: The new science of Networks." Perseus Books Group, 2002
16. C.A. Hidalgo, R. B. Klinger, A.-L. Barabási, R. Hausmann. "The product space conditions the development of nations." Science 317, 482 (2007)
17. V. Palchykov, K. Kaski, J. Kertesz, A.-L. Barabási, R. Dunbar. "Sex differences in intimate relationships." Scientific Reports 2:370, 105 (2012)
18. Andrei V. Yakushev, Alexander V. Boukhanovsky, Peter M. A. Sloot. "Topic Crawler for Social Networks Monitoring." Knowledge Engineering and the Semantic Web. Communications in Computer and Information Science Volume 394, 2013, pp 214-227
19. Saroop, A. Karnik, A. "Crawlers for social networks & structural analysis of Twitter." 5th International Conference on Internet Multimedia Systems Architecture and Application (IMSAA), 2011 IEEE
20. Dhiraj Murthy, Alexander Gross, Alexander Takata, Stephanie Bond. "Evaluation and Development of Data Mining Tools for Social Network Analysis." Mining Social Networks and Security Informatics Lecture Notes in Social Networks 2013, pp 183-202
21. Twitter. "The Twitter REST API" twitter.com [Online] https://dev.twitter.com/docs/api , visitado 19 Ene 2014