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

Imágen de pdf Visualización de redes complejas

Visualización de redes complejasgráfica de visualizaciones

Publicado el 15 de Mayo del 2019
86 visualizaciones desde el 15 de Mayo del 2019
32,1 MB
139 paginas
Creado hace 10a (08/09/2008)
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

. . . . . . . . . . . . . . .
  • Links de descarga
http://lwp-l.com/pdf15929

Comentarios de: Visualización de redes complejas (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios
Es necesario revisar y aceptar las políticas de privacidad

Revisar política de publicidad