PDF de programación - Visualización de redes complejas

VISUALIZACIÓN DE
REDES COMPLEJAS

TESIS DE GRADO DE

INGENIERÍA INFORMÁTICA



FACULTAD DE INGENIERÍA

UNIVERSIDAD DE BUENOS AIRES

TESISTA: MARIANO GASTÓN BEIRÓ
DIRECTOR: DR. ING. JOSÉ IGNACIO ALVAREZ-HAMELIN


AGOSTO 2008

ii

Agradecimientos

Al terminar esta tesis después de todo un año de trabajo, no puedo dejar

de agradecer a aquellas personas vinculadas a la misma:

A los miembros del jurado, por haber aceptado la lectura y evaluación de

este trabajo.

A José Ignacio por enseñarme tantas cosas y por tenerme inmensa pa-

ciencia. Por incentivarme al estudio y a la investigación.

A Jorge, por sus correcciones y sugerencias.

También en lo personal quiero agradecer:

A mis padres, Mary y Marcelo, por apoyarme siempre en todo, por con-
fiar en mí y por su enorme afecto. Y a mi hermano Sergio por soportarme.
Gracias por haberme dado tanto, y por todo lo que se sacrifican día a día.

A toda mi familia, que es parte de mi, me aconseja y empuja.

A mis profesores de la carrera y del cole, de quienes he aprendido mucho

y les estaré eternamente agradecido.

A mis amigos, sin quienes se haría muy difícil caminar y enfrentar los
problemas y responsabilidades. Gracias por su alegría, por aguantarme y por
estar siempre!

A mis compañeros de la carrera con quienes compartimos días de estudio
y noches sin dormir terminando tps, y que me ayudaron para llegar hasta acá.

A mis compañeros del trabajo, por entenderme cada vez que les dije “ten-

go que irme a trabajar con la tesis...”.

iii

iv

Índice general

1. Introducción

1.1. La complejidad de los sistemas en el mundo actual . . . . . . .
1.2. Visualización de la Información . . . . . . . . . . . . . . . . .
1.3. Notación utilizada y definiciones previas
. . . . . . . . . . . .
1.4. Sistemas Complejos . . . . . . . . . . . . . . . . . . . . . . . .
1.4.1. Distribución de grados scale-free . . . . . . . . . . . . .
1.4.2. La vinculación preferencial . . . . . . . . . . . . . . . .
1.4.3. Assortative mixing . . . . . . . . . . . . . . . . . . . .
1.5. Ejemplos de Sistemas Complejos . . . . . . . . . . . . . . . . .
1.5.1. Redes Sociales . . . . . . . . . . . . . . . . . . . . . . .
1.5.2. Redes Biológicas
. . . . . . . . . . . . . . . . . . . . .
1.5.3. Redes Tecnológicas . . . . . . . . . . . . . . . . . . . .
1.5.4. Redes de Información . . . . . . . . . . . . . . . . . . .
1.6. Organización . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
1
1
2
4
5
5
6
6
6
7
7
8
8

2. Estado del arte

11
2.1. Dirigidos por fuerzas . . . . . . . . . . . . . . . . . . . . . . . 11
2.2. Descomposición en clusters . . . . . . . . . . . . . . . . . . . . 12
2.2.1. Descomposición espectral . . . . . . . . . . . . . . . . . 13
2.2.2. Algoritmos divisivos
. . . . . . . . . . . . . . . . . . . 15
2.3. Descomposición en k-núcleos . . . . . . . . . . . . . . . . . . . 16
2.3.1. Algunas definiciones
. . . . . . . . . . . . . . . . . . . 16
2.3.2. Visualización en 2.5 dimensiones, Batagelj et al. . . . . 17
2.3.3. LunarVis
. . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.4. LaNet-vi 1.0 . . . . . . . . . . . . . . . . . . . . . . . . 19

3. Fundamentos de LaNet-vi

21
3.1. Visualización con LaNet-vi1 . . . . . . . . . . . . . . . . . . . 21
3.1.1. Visualización en capas . . . . . . . . . . . . . . . . . . 22
3.1.2. Distribución dentro de las capas . . . . . . . . . . . . . 22
3.1.3. Escala de colores
. . . . . . . . . . . . . . . . . . . . . 23

v

vi

ÍNDICE GENERAL

3.1.4. Visualización de los grados de los nodos

. . . . . . . . 24
3.2. Descomposición en cliqués . . . . . . . . . . . . . . . . . . . . 25
3.2.1. Algoritmos de búsqueda de cliqués conocidos . . . . . . 26
3.2.2. Heurística de búsqueda de cliqués propuesta . . . . . . 27
3.2.3. Estudio de la complejidad . . . . . . . . . . . . . . . . 34
3.3. Posicionamiento en LaNet-vi2 . . . . . . . . . . . . . . . . . . 37
3.3.1. Despliegue del núcleo central . . . . . . . . . . . . . . . 37
3.3.2. Nuevo cálculo del radio . . . . . . . . . . . . . . . . . . 38
3.3.3. Nuevo cálculo del ángulo . . . . . . . . . . . . . . . . . 39
3.4. Análisis de núcleo-conexidad . . . . . . . . . . . . . . . . . . . 41
3.4.1.
Implementación en LaNet-vi2 . . . . . . . . . . . . . . 45
3.4.2. Estudio de la complejidad . . . . . . . . . . . . . . . . 50
3.5. Etiquetado de nodos
. . . . . . . . . . . . . . . . . . . . . . . 51
3.6. Visualización de multigrafos . . . . . . . . . . . . . . . . . . . 52
. . . . . . . . . . . . . . . . . 53
3.7. Visualización de grafos pesados
3.8. Renderizado y transparencias
. . . . . . . . . . . . . . . . . . 57

4. Visualización de redes con LaNet-vi

59
4.1. Redes Biológicas
. . . . . . . . . . . . . . . . . . . . . . . . . 61
4.2. Redes de Transporte . . . . . . . . . . . . . . . . . . . . . . . 64
4.3. Redes Sociales . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.4. Redes de Información . . . . . . . . . . . . . . . . . . . . . . . 72
Internet
4.5.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.5.1. Visualización de Sistemas Autónomos . . . . . . . . . . 74
4.5.2. Visualización a nivel de Ruteadores . . . . . . . . . . . 88

5. Conclusiones

5.1. Contribuciones
5.2. Trabajo futuro

91
. . . . . . . . . . . . . . . . . . . . . . . . . . 91
. . . . . . . . . . . . . . . . . . . . . . . . . . 93

A. Descripción de clases

95
A.1. Module Circular average . . . . . . . . . . . . . . . . . . . . 95
A.2. Module Clique . . . . . . . . . . . . . . . . . . . . . . . . . . 95
A.3. Module Component . . . . . . . . . . . . . . . . . . . . . . . . 96
A.4. Module Files . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
A.5. Module Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
A.6. Module Graph builder . . . . . . . . . . . . . . . . . . . . . . 101
A.7. Module Graph builder nwb . . . . . . . . . . . . . . . . . . . 102
A.8. Module Graph node names . . . . . . . . . . . . . . . . . . . . 103
A.9. Module Graphics . . . . . . . . . . . . . . . . . . . . . . . . . 104
A.10.Module Host . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

ÍNDICE GENERAL

vii

A.11.Module Host list . . . . . . . . . . . . . . . . . . . . . . . . 107
A.12.Module Log . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
A.13.Module Main . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
A.14.Module Network . . . . . . . . . . . . . . . . . . . . . . . . . 110
A.15.Module Normal . . . . . . . . . . . . . . . . . . . . . . . . . . 112
A.16.Module Parameters . . . . . . . . . . . . . . . . . . . . . . . 112
A.17.Module Povray . . . . . . . . . . . . . . . . . . . . . . . . . . 114
A.18.Module Povray renderer . . . . . . . . . . . . . . . . . . . . 115
A.19.Module Svg . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
A.20.Module Svg renderer . . . . . . . . . . . . . . . . . . . . . . 116
A.21.Module Types . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
A.22.Module Uniform . . . . . . . . . . . . . . . . . . . . . . . . . 117
A.23.Module Vertex . . . . . . . . . . . . . . . . . . . . . . . . . . 118

B. Artículo NJP

121

viii

ÍNDICE GENERAL

Índice de figuras

1.1. Distribución potencial de grados con B = 2, 2.

. . . . . . . . .

5

2.1. Red de 15 nodos visualizada con un algoritmo dirigido por

fuerzas. (Imagen generada con Network Workbench [28]). . . . 12
2.2. Matriz de adyacencias de la red. . . . . . . . . . . . . . . . . . 14
2.3. Componentes del autovector asociado al mayor autovalor. . . . 14
2.4. Descomposición en clusters de la red basada en el autovector

asociado al mayor autovalor. . . . . . . . . . . . . . . . . . . . 15

2.5. Descomposición en clusters de las páginas de un sitio Web,
descubriendo estructuras comunitarias. Los distintos colores
representan a los clusters. Las flechas indican el sentido de los
hipervínculos (imágen extraída de [27]).

. . . . . . . . . . . . 16

2.6. Descomposición en k-núcleos de un grafo (imagen extraída

de [10]).

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.7. Visualización de la red de sistemas autónomos en 2,5 dimen-

siones. Baur et al. [11]

. . . . . . . . . . . . . . . . . . . . . . 18
2.8. Visualización de la red de sistemas autónomos con LunarVis [21]. 19
2.9. Visualización de la red de sistemas autónomos con LaNet-vi

1.0 [6].

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.1. Escala de grados (izquierda) y de colores (derecha) de LaNet-
vi. Ejemplo para una red con kmáx = 20 y grado máximo
dmáx = 1236. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.2. Visualización de la red de sistemas autónomos (ASes) con
LaNet-vi (izquierda), y con la nueva versión: LaNet-vi2 (dere-
cha). Obsérvese el nuevo despliegue del núcleo central.

. . . . 25
3.3. Grafos completos (cliqués) de 4 y 6 nodos respectivamente. . . 26
3.4. Grafo de la red a partir de la cual se obtendrán cliqués. (Ima-

gen generada con Network Workbench [28]).

. . . . . . . . . . 31

ix

x

ÍNDICE DE FIGURAS

3.5. Ejes entre vecinos del nodo 1. El eje (2,3) contribuye unitaria-
mente con C1,2 y C1,3. El eje (2,4) contribuye con C1,2 y C1,4.
El eje (3,4) contribuye con C1,3 y C1,4.

. . . . . . . . . . . . . 32

3.6. Descomposición en cliqués de la red ejemplo, empleando el
algoritmo de LaNet-vi2. Observar cómo los cliqués mayores
han sido detectados.

. . . . . . . . . . . . . . . . . . . . . . . 34
. . . . 38

3.7. Posicionamiento de los nodos del núcleo central (kmáx).
3.8. Organización en clusters que tenía LaNet-vi1 (izquierda) con-
trastada con la organización conforme al promedio circular en
LaNet-vi2 (derecha).
3.9. El cluster a está conectado a través de los clusters e, d y b al
núcleo central. El cluster a tiene conexidad kmáx − 2, a pesar
de que el cluster b tiene sólo conexidad m < kmáx − 1. . . . . . 49

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