PDF de programación - Tema 4-2: Algoritmos de Poda y Visualización de Redes

Redes y Sistemas Complejos

Cuarto Curso del Grado en Ingeniería Informática

Tema 4: Algoritmos de Poda y Visualización de Redes

Oscar Cordón García

Dpto. Ciencias de la Computación e Inteligencia Artificial

[email protected]

INTRODUCCIÓN

Necesidad de la simplificación y visualización de redes

La visualización de información tiene el potencial necesario para ayudar a las
personas a acceder a la información necesaria de una forma más eficaz e intuitiva

La visualización de información comprende dos aspectos directamente relacionados:
Modelado estructural y Representación gráfica

El propósito de la representación gráfica es transformar
un modelo previo de una estructura en un modelo gráfico
que permita examinar visualmente la estructura original
e interactuar con ella

En el dominio de la visualización de redes complejas,
la gran dimensión de las redes genera dificultades para
obtener representaciones gráficas útiles para el análisis

Una misma red puede representarse gráficamente de diversas formas → uso de
distintos algoritmos de distribución (layout), con distintas filosofías

INTRODUCCIÓN

Historia de la visualización de información (1)

John W. Tukey:

• Fue el que acuñó los términos software y análisis

exploratorio de datos, así como la expresión: “es mejor
tener una respuesta aproximada a la pregunta correcta
que una respuesta precisa a la pregunta equivocada”

Edward F. Tufte:

• Su libro de 1983 popularizó las ideas de Tukey: “el éxito de
una visualización se basa en el conocimiento profundo y el
cuidado de la sustancia, así como en la calidad, relevancia e
integridad del contenido”

• En nuestro ámbito, ¡conoce la red!

INTRODUCCIÓN

Historia de la visualización de información (2)

Maximización de la información útil en una ventana de visualización limitada

INTRODUCCIÓN

Historia de la visualización de información (3)

Tufte enunció los cinco principios básicos de la visualización de datos:

• Lo principal, mostrar los datos

• Maximizar el ratio data-ink, dentro de lo razonable

(data-ink es la “tinta” usada para la presentación de los datos. Si se eliminara, el gráfico
perdería contenido. Non-Data-Ink es la “tinta” que no contiene información y se usa para
escalas, etiquetas y enlaces)

• Eliminar el contenido que no sea data-ink, dentro de lo razonable

• Eliminar el contenido data-ink redundante

• Revisar y editar

http://www.edwardtufte.com/tufte/

INTRODUCCIÓN

Aspectos básicos de la visualización de redes (1)

Tamaño de la red:

A mayor número de nodos, mayor número de píxeles serán necesarios para
visualizar la red en la pantalla:

800 × 600 = 480,000 pixels
1024 × 768 = 786,432 pixels
1920 × 1200 = 2,304,000 pixels

¡Puede ocurrir que no tengamos suficientes
píxeles para visualizar la red!

Cuanta más información tengamos que presentar en pantalla, más importancia
tendrá el diseño y la gestión de la ventana de visualización

INTRODUCCIÓN

Aspectos básicos de la visualización de redes (2)

Aspectos de distribución (layout):

¿Cómo representar un nodo?

Forma

Tamaño

Color

A

Etiquetado

B

Localización

INTRODUCCIÓN

Aspectos básicos de la visualización de redes (3)

Representación de los enlaces:

Etiquetado

A

Anchura

Color

Dirección

Forma

INTRODUCCIÓN

Aspectos básicos de la visualización de redes (4)

Ejemplo: anchura de los
enlaces:

E-mails en un departamento
de los AT&T Bell Labs:

• 1 mes de datos
• 1500 usuarios
• Umbral: usuarios con más

de 20 mensajes

R.A. Becker, S.G. Eick, A.R.
Wilks. 1995. Visualizing Network
Data. IEEE Trans. Visualization
and Computer Graphics 1(1):
16-21

INTRODUCCIÓN

Aspectos básicos de la visualización de redes (4)

La visualización de un subconjunto de una red resaltando los atributos
de los nodos mediante forma y color mejora su comprensión:

Una red de atracción en una

clase de cuarto curso (Moreno,
‘Who shall survive?’, 1934).

Alden Klovdahl: Parte central (n~ 450)

de una red social de unos 5000
residentes en Canberra, Australia

INTRODUCCIÓN

Aspectos básicos de la visualización de redes (5)

Ejemplo: color = género:

Citas en el instituto:

P.S. Bearman, J. Moody, K. Stovel.
2004. Chains of affection: The
structure of adolescent romantic
and sexual networks. American
Journal of Sociology 110: 44-91

(imagen de Mark Newman)

INTRODUCCIÓN

Aspectos básicos de la visualización de redes (6)

Ejemplo: forma de los nodos:

Integración racial en el colegio:

J. Moody. 2001. Race, School
Integration, and Friendship
Segregation in America. American
Journal of Sociology 107(3): 679-716

INTRODUCCIÓN

Aspectos básicos de la visualización de redes (7)

Ejemplo: forma de los nodos:

Integración racial en el colegio:

J. Moody. 2001. Race, School
Integration, and Friendship
Segregation in America. American
Journal of Sociology 107(3): 679-716

9th

10th

11th

12th

white

non-white

INTRODUCCIÓN

Aspectos básicos de la visualización de redes (8)

Posibilidad de combinar la visualización de la red con información geográfica:

Tráfico de datos en el backbone de la red
ANS/NSFnet T3 en Noviembre de 1993

(Cox & Patterson)

Imágenes Walrus de datos Skitter de Internet

(54893 nodos y 79409 enlaces)

Walrus está disponible con licencia GPL:

http://www.caida.org/tools/visualization/walrus/gallery1/

PROBLEMAS DE LA DISTRIBUCIÓN (LAYOUT) DE REDES

¡¡El problema de los enlaces es que pueden tapar partes del grafo!!

Antes de pintar los enlaces

Después de pintar los enlaces

DISTRIBUCIONES BÁSICAS

Aleatoria

Se escogen aleatoriamente las
coordenadas (x,y) para cada nodo

• Ventaja: muy rápida

•

Inconveniente: imposible de
interpretar

DISTRIBUCIONES BÁSICAS

Circular

Se distribuyen los nodos en círculo y se
dibujan los enlaces entre ellos

• Ventajas:

• Muy rápida

•

Las coordenadas circulares pueden
representar una propiedad de los datos
(p.ej. latitudes o edades)

•

Inconvenientes: difícil de interpretar en
redes grandes y densas:
• mucho solapamiento de enlaces
• muchos enlaces largos (los nodos

conectados no tienen por qué estar cerca)

• Es difícil identificar clusters

DISTRIBUCIONES BÁSICAS

Radial (1)

• Se distribuyen los nodos en círculo

• Se localiza el nodo central en el centro de la ventana de visualización

• Se distribuyen sus vecinos en círculos concéntricos de radio equivalente

al peso de su enlace

DISTRIBUCIONES BÁSICAS

Radial (2)

Ejemplo:

• Grafo de Internet IPv4

• Mapa de Internet a nivel
de sistemas autónomos
(AS-level)

http://www.caida.org/research/topology/as_core_network/

DISTRIBUCIONES BÁSICAS

Radial (3)

Se comienza con un nodo y se
dibujan todos los demás nodos
en capas semicirculares de
acuerdo a cuántos saltos hay
que dar para alcanzar a cada
uno de ellos desde el inicial

• Ventajas: Muy rápida

•

Inconvenientes: No se tiene
en cuenta que los nodos que
estén conectados entre sí
deberían estar cercanos en
cada capa

CRITERIOS ESTÉTICOS PARA VISUALIZACIÓN DE REDES (1)

• Minimizar los cruces entre enlaces:

• No permitir que los nodos se

superpongan a enlaces que no
incidan en ellos:

• En redes no ponderadas, mantener

una longitud de enlace uniforme:

En redes ponderadas, la longitud
de cada enlace debe ser
proporcional a su peso

mejor que

mejor que

mejor que

CRITERIOS ESTÉTICOS PARA VISUALIZACIÓN DE REDES (2)

INTRODUCCIÓN

Los métodos de distribución guiados por fuerzas son algoritmos de dibujado de
grafos generales no dirigidos con enlaces de líneas rectas en el plano (demo)

En general, fueron propuestos para verificar distintos criterios estéticos:

1. Distribución uniforme de los nodos

2. Longitud uniforme de los enlaces

3. Minimización de los cruces (superposiciones) entre enlaces

4. Simetría

Cada método pone un énfasis especial en algunos de estos criterios

Los criterios pueden ser mutuamente excluyentes. P.ej. un grafo simétrico puede
requerir un cierto número de cruces entre enlaces, incluso si se pueden evitar

Un enfoque pragmático consiste en darle a los algoritmos la suficiente flexibilidad
para adaptarse a aplicaciones concretas

http://en.wikipedia.org/wiki/Force-directed_graph_drawing

EL PROBLEMA

Problema: Dado un conjunto de nodos y enlaces, calcular las posiciones de
los nodos en el plano

El objetivo es doble, pintar el grafo bien (uso de heurísticas) y pintarlo rápido
(necesidad de escalado para grafos grandes)

Es un problema muy complicado porque presenta muy pocas restricciones

Los métodos de distribución guiados por fuerzas se propusieron inicialmente
para el diseño VLSI para optimizar el diseño de un circuito con el menor
número posible de cruces entre líneas

Existen muchas variantes distintas. La primera, basada en representaciones
barimétricas, fue propuesta por Tutte en 1963

W.T. Tutte. 1963. How to draw a graph. Proc. London Math. Society 13(52): 743-768

LA METÁFORA DEL SISTEMA DE MUELLES (1)

P. Eades. 1984. A heuristic for graph drawing. Congressus Numerantium, 42: 149-160

Modelo spring embedder: Analogía física para dibujar grafos, interpreta los grafos
como un sistema de objetos con fuerzas:

•

•

Los nodos son anillos de metal con cargas eléctricas
Todos los nodos ejercen una fuerza repulsiva (fr) entre sí
•

Los enlaces son muelles
•

Ejercen una fuerza atractiva entre los nodos conectados (fa)

Los nodos no conectados tienden a alejarse y los conectados a acercarse

Se persigue que la distancia Euclidea entre los nodos en la visualización equivalga a
una longitud natural de enlace prefijada

Se asume que un sistema equilibrado, aquel en el que todos los nodos se encuentran
a esa distancia teórica, implica una buena visualización

LA METÁFORA DEL SISTEMA DE MUELLES (2)

El sistema empieza con una distribución inicial aleatoria

Los nodos se van moviendo de acuerdo a la acción de las fuerzas,
cambiando la distribución

Cada distribución tiene una energía global

La distribución óptima corresponde a la distribución estable en la que la
suma de fuerzas de