PDF de programación - Análisis de Redes Sociales a Gran Escala

CENTRO DE INVESTIGACIÓN Y DE ESTUDIOS AVANZADOS

DEL INSTITUTO POLITÉCNICO NACIONAL

DEPARTAMENTO DE COMPUTACIÓN

Análisis de Redes Sociales a Gran Escala

Tesis que presenta

Cristian Paolo Mejia Olivares

Para obtener el grado de

Maestro en Ciencias en Computación

Directores de Tesis:

Dra. Xiaoou Li Zhang

Dr. Luis E. Rocha Mier

México, D. F.

Febrero, 2010

ii

Agradecimentos

iii

A mi padre Ramón Mejia y a mi madre Estela Olivares por brindarme su apoyo siempre
y estar en los momentos felices y difíciles de mi vida, por ayudarme a cumplir mis sueños
y nunca darme la espalda por más complicado que esto pareciera, porque no existe manera
alguna en esta vida en que pueda pagarles todo lo que han hecho por mi.

A mis hermanos, mis sobrinos y mis cuñadas por apoyarme y por brindarme buenos con-
sejos y lecciones muy importantes en mi vida, por haberme dado momentos de alegria y de
distracción y sobre todo por ser parte de mi familia.

A Edith Tamaya por ser mi compañera en gran parte de mi vida y por compartir tantos
momentos a mi lado, por enseñarme a valorar las cosas, por apoyarme en todo momento
y por brindarme un espacio dentro de tu corazón y de tu familia, porque las cosas nunca
hubieran sido las mismas sin ti :).

A la Dra. Xiaoou Li y al Dr. Luis Rocha por dedicarme tiempo y orientarme durante mi
trabajo de tesis, y por siempre escucharme, brindarme su apoyo y darme consejos cuando
yo me acercaba a ustedes.

A mis sinodales, Dr. Pedro Mejia Alvarez y Dr. Amilcar Meneses Viveros por el tiempo

dedicado para la revisión de este documento y por sus comentarios para mejorarlo.

Gracias a mis amigos del CINVES, Pam, july, beto, jonhy, don gabo, andres, migue, ray,
pau, adri, lupita, lil, christian, madai, paco, bris por dejarme muchos recuerdos felices den-
tro y fuera del CINVES.

A Sofi por siempre apoyarnos bajo cualquier situación y escucharnos cuando necesitabamos

de alguien que nos echara la mano.

A Alan y a Fernanda por brindarme su amistad cuando más la necesitaba.

A la Universidad Rey Juan Carlos de España por permitirme realizar una estancia, y so-
bre todo a la gente de LibreSoft por brindarme su apoyo y ser tan amables durante la estancia.

Al CONACyT y al CINVESTAV por el apoyo económico para la realización de mis estu-

dios de maestría y ofrecerme la oportunidad de conocer muchas cosas nuevas.

iv

Resumen

v

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 sis-
temas, 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 es-
cala 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 con-
ceptos 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 es-
tudio 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éc-
nias 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 agru-
pamiento 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 de-
muestran 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 so-
ciales, 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 creci-
miento como una red libre de escala y poseen una forma del tipo mundo pequeño.

vi

Abstract

vii

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 and Wikipedia (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 ex-
perimental 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 so-
cial 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 behav-
ior 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.

viii

Contenido

Resumen

Abstract

Índice de figuras

Índice de tablas

1

.

.

.

Introducción
1.1 Antecedentes
.
1.2 Trabajo Relacionado .
.
1.3 Motivación .
.
1.4 Objetivos .
1.5 Organización .
.

.
.
. .
.

.
. .

.
.
.

.
.
.

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Redes Sociales

.

.

.

.

. . . . . . . . . . . . . . . . . . . . . .

2.1 Orígen de las Redes Sociales . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Análisis de Redes Sociales . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
2.3 Propiedades de las Redes Sociales
2.3.1 Distancias en las redes . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.2 Tipos de interacción . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.3 Coeficiente de Agrupamiento . . . . . . . . . . . . . . . . . . . . . .
2.3.4 Cliques .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4 Clasificación de Redes Sociales . . . . . . . . . . . . . . . . . . . . . . . . .
2.4.1 Redes de Mundo Real
. . . . . . . . . . . . . . . . . . . . . . . . . .
2.4.2 Redes Sociales en línea . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5 Representación de las Redes Sociales . . . . . . . . . . . . . . . . . . . . . .
2.6 Estructura de las Redes Sociales . . . . . . . . . . . . . . . . . . . . . . . . .
2.6.1 El componente gigante de las redes sociales . . . . . . . . . . . . . .
2.6.2 Redes Complejas . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Redes aleatorias. . . . . . . . . . . . . . . . . . . . . . . . .
Redes de mundo pequeño . . . . . . . . . . . . . . . . . .
Redes ley de potencia . . . . . . . . . . . . . . . . . . . . .
Redes libres de escala . . . . . . . . . . . . . . . . . . . . .

2.6.2.1
2.6.2.2
2.6.2.3
2.6.2.4

ix

vi

viii

xiv

xv

1
1
2
3
3
4

5
5
6
6
6
7
7
8
8
10
10
11
13
13
14
14
15
15
17

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

x

CONTENIDO

Ejemplo del cálculo de la centralidad para un grafo.

2.7 Modelos de redes sociales . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.7.1 Modelos de Redes Aleatorias . . . . . . . . . . . . . . . . . . . . .

2.6.3 Centralidad en