Tribus Urbanas

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

iiiAgradecimentos
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 porapoyarme y por brindarme buenos consejos 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 tufamilia, 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 porsus 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 dentro 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 suamistad cuando más la necesitaba. A la Universidad Rey Juan Carlos de España por permitirme realizar una estancia, y sobre 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 estudios de maestría y ofrecerme la oportunidad de conocer muchas cosas nuevas.

iv

v

Resumen
Lamayorí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 crearnuevas 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 bolade 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....