Departamento de Computación

La mayoría de los estudios sobre la estructura de las redes sociales está basado en redes a pequeña escala [56, 61]. Recientemente, las aplicaciones de los sistemas Web proporcionan una nueva fuente de información para poder estudiar las propiedades de las redes sociales del mundo real. Sistemas como Flickr, Twitter, MySpace y Facebook, han permitido retomar la teoría de redes sociales para poder crear nuevas aplicaciones en base a este tipo de sistemas, ya que permiten modelar redes del mundo real con la gran cantidad de información que poseen. En la literatura, se pueden encontrar diferentes trabajos sobre redes sociales a pequeña escala y para redes estáticas. Sin embargo, pocos son los trabajos que estudian las propiedades de las redes sociales a gran escala. El análisis de redes sociales (ARS) proporciona los conceptos y las técnicas para el estudio de redes sociales basado en la teoría de grafos y del cálculo matemático. Nuestra investigación está dividida en tres partes principales, la primera de ellas es un estudio de los diferentes métodos de extracción de información y de las técnicas de muestreo aplicadas a los sistemas de redes sociales en línea. Utilizando un muestreo de bola de nieve y haciendo uso de la interacción entre usuarios, se implementó un algoritmo para obtener un conjunto de datos representativo de los sistemas Flickr y Wikipedia. En la segunda parte de la tesis se estudió la forma de escalar el análisis de redes sociales a gran escala mediante la detección de comunidades, la cual se apoya en las diferentes técnias de la teoría del agrupamiento en grafos. En base al método de propagación de etiquetas [77] para la detección de comunidades disjuntas, se adaptó un algoritmo que permite detectar comunidades traslapadas en redes sociales a gran escala a partir del cálculo del coeficiente de agrupamiento de un nodo en cada comunidad. Para medir el desempeño del algoritmo se realizaron pruebas con diferentes conjuntos de datos con distintos tamaños y características. En general, los resultados experimentales demuestran que el algoritmo presenta un comportamiento estable y un buen desempeño para conjuntos de datos grandes y permite escalar el estudio de las redes sociales a gran escala por medio del traslapamiento de comunidades dentro de las redes sociales. Finalmente, presentamos un análisis de la estructura de dos diferentes tipos de redes sociales, Flickr basada en contenido y la Wikipedia basada la colaboración. En general, los resultados muestran que las redes sociales de estos sistemas presentan un modelo de crecimiento como una red libre de escala y poseen una forma del tipo mundo pequeño.

Abstract

Most studies on the structure of social networks is based on networks small scale [56, 61]. Recently, applications of Web systems provide a new source of information to study the properties of social networks in real world. Systems such as Flickr, MySpace and Facebook, allow new applications using social networks theory, in which real-world networks can be modeled with the large amount of information they have. In literature, much work can be found on studying small-scale social networks and static networks. However, few of them analyze properties of large scale social networks. Social network analysis (SNA) concepts and techniques are generally based on graph theory and mathematical calculation. Our research is divided into three main parts; the first is a study of different methods of extracting information and sampling techniques applied to Online Social Networks. Using a snowball sampling and using the interaction between users, an algorithm was implemented to obtain a representative data set of systems Flickr andWikipedia (Between August 2008 to December 2009) were investigated. In the second part of the thesis we explore the algorithms for detecting social networking communities, and propose a community detection algorithm based on disjoint communities detection using label propagation method of reference . To measure the performance of our algorithm, data sets with different sizes and characteristics were tested. In general, the experimental results show that our algorithm has a stable behavior and a good performance for large-scale networks. Based on disjoint communities detection using label propagation method [77], we adapted an algorithm to detect overlapping communities in large-scale social networks by calculating the clustering coefficient of a node in each community. For measure the performance of the algorithm this was tested with different data sets and characteristics. In general, experimental results show that the algorithm has a stable behavior and good performance for large data sets and allows you to scale the study of large-scale social networks through the overlap of communities within social networks. Finally, we did two case studies to demonstrate our approaches described above. Flickr and Wikipedia were selected for their huge scale and popularity as social networks. The results demonstrate that these social networks present a model of growth as a scale-free network and a shape as small world.