Publicado el 30 de Octubre del 2019
523 visualizaciones desde el 30 de Octubre del 2019
7,2 MB
97 paginas
Creado hace 11a (17/03/2014)
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
ocordon@decsai.ugr.es
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
+
Comentarios de: Tema 4-2: Algoritmos de Poda y Visualización de Redes (0)
No hay comentarios