PDF de programación - Tema 4 - 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 (1)

La sobrecarga de información (information overload) se ha convertido en un
problema fundamental debido al crecimiento exponencial de la información accesible
en la sociedad actual

Es obligatorio considerar métodos de filtrado y
compartición de información para resolver este problema

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

Definición R.A.E: “Representar mediante imágenes ópticas fenómenos de otro
carácter. || Formar en la mente una imagen visual de un concepto abstracto”

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

C. Chen. Information Visualization. 2nd edition. Springer 2004

INTRODUCCIÓN

Necesidad de la simplificación y visualización de redes (2)

El objetivo del modelado estructural es detectar, extraer y simplificar las relaciones
subyacentes en nuestro dominio de aplicación

Estas relaciones forman una estructura que caracteriza
el sistema o conjunto de datos estudiado. Ej: una
pregunta típica es ¿cuál es la estructura de una red?

Por el contrario, 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

Ej: una estructura jerárquica se puede representar
como un árbol cónico o un grafo hiperbólico

Las dos etapas suelen estar bastante mezcladas

INTRODUCCIÓN

Necesidad de la simplificación y visualización de redes (3)

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

Problemática:

1. Calidad: cuanto más grande es la red, más

probabilidad hay de que existan errores en los datos

2. Complejidad: más variables, más detalle, más

categorías

3. Velocidad: Hoy en día, el interés se centra en obtener resultados de nuestra red lo

bastante rápido como para que pueda considerarse un proceso interactivo

4. Análisis: ¿Qué orden de complejidad se requiere para los algoritmos que manejan

redes de gran tamaño?

Unwin A., Theus M., Hofmann, H. 2008. Graphics of Large Datasets: Visualizing a Million. Springer

INTRODUCCIÓN

Necesidad de la simplificación y visualización de redes (4)

La solución se basa procesar las matrices de adyacencia de la red (cuyas entradas indican
similitud o distancia entre las componentes) usando técnicas de reducción de la dimensión que
faciliten la visualización de la red. Este tipo de técnicas se pueden clasificar en dos grupos:

1. Técnicas de naturaleza estadística, basadas en el análisis multivariante, como el clustering,

el análisis de componentes principales (PCA) y el escalado multidimensional (MDS)

2. Técnicas de naturaleza conexionista, basadas habitualmente en el modelo de mapa auto-

organizativo (SOM) de red neuronal

Su función es simplificar el complejo patrón de asociación existente entre
las entidades de la red proyectando su gran número de dimensiones en un
número mucho más pequeño, normalmente dos o tres, las procesables
gráficamente por el ser humano (representaciones 2D y 3D)

Esa reducción suele implicar una pérdida de información como
consecuencia del proceso de agregación de las múltiples dimensiones.
Además, estas técnicas no muestran los enlaces y sólo representan las
relaciones individuales (locales) mediante proximidad espacial

INTRODUCCIÓN

Necesidad de la simplificación y visualización de redes (4)

Ej: redes de cocitación científica

(White, Lin y McCain. 1998)

INTRODUCCIÓN

Necesidad de la simplificación y visualización de redes (5)

Alternativamente, existen métodos de poda de redes basados en la eliminación de nodos
y/o enlaces que sacrifican la pérdida de información para obtener una ganancia en simplicidad

Se pueden hacer distintos tipos de poda. La más básica en una red ponderada es una poda por
umbral, eliminando directamente aquellos nodos/enlaces cuyo valor/peso sea inferior o superior
al valor límite. Sin embargo, puede provocar la pérdida de la conectividad de la red

También se puede reducir el número de enlaces de la red usando su árbol generador minimal
(minimum spanning tree, MST). Esta filosofía realiza una poda más radical (cada par de nodos
queda conectado por un único enlace) pero desde una perspectiva más global

http://decsai.ugr.es/~ta_ii/algoritmos/seccion.php?id=teoria&subseccion=applets/kef5_4

Finalmente, otra alternativa reduce la red original a una de sus redes Pathfinder (PFNETs). El
algoritmo Pathfinder se desarrolló en el marco de la ciencia cognitiva. Su función es construir
varias redes distintas formadas sólo por los enlaces más relevantes de la red original según se
satisfaga la desigualdad triangular en caminos de un tamaño determinado

Schvaneveldt, R.W., et al. 1989. Network structures in proximity data. En G. Bower (Ed.), The psychology of
learning and motivation: Advances in research and theory, Vol. 24, pp. 249–284. Academic Press

http://en.wikipedia.org/wiki/Pathfinder_network

INTRODUCCIÓN

Necesidad de la simplificación y visualización de redes (6)

Ej: redes de cocitación científica

(Vargas-Quesada y Moya-Anegón, 2007)

INTRODUCCIÓN

Necesidad de la simplificación y visualización de redes (7)

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

De dicha representación dependerá la facilidad con la que las personas dedicadas a analizarla
puedan comprenderla

Dos métodos muy extendidos, basados en la filosofía spring embedders dentro de los métodos
de layout dirigidos por fuerzas son los de Kamada-Kawai y Frutcherman-Reingold

INTRODUCCIÓN

Necesidad de la simplificación y visualización de redes (8)

INTRODUCCIÓN

Necesidad de la simplificación y visualización de redes (9)

TÉCNICAS ESTADÍSTICAS DE REDUCCIÓN DE LA DIMENSIÓN EN REDES (1)

Técnicas de reducción de la dimensión basadas en el análisis multivariante:

1. clustering,

2. análisis de componentes principales (PCA) y

3. escalado multidimensional (MDS)

Los tres trabajan con una matriz de datos simétrica y cuadrada. Las filas y columnas de la
matriz hacen referencia a las mismas entidades, y las celdas corresponden a un valor numérico
que representa un grado de asociación (similitud) o disociación (distancia) entre las entidades

En el caso de clustering y MDS los valores de la matriz de entrada son “brutos”. En PCA se
consideran covarianzas o correlaciones entre las dos variables

MDS y PCA proporcionan salidas parecidas, una nube de puntos (objetos) distribuidos en el
espacio reducido (2D o 3D). El clustering devuelve generalmente un dendrograma
bidimensional donde se representa una estructura jerárquica de clasificación

Los tres métodos pierden las relaciones locales al no representar los enlaces de la red

CLUSTERING JERÁRQUICO (1)

• El objetivo de los métodos de clustering es reducir el volumen de información

mediante la categorización o agrupamiento de datos con características similares

• El clustering aporta herramientas que facilitan la construcción automática de

taxonomías y minimizan la intervención humana en el proceso

• Esta técnica se utiliza para crear una gráfica bidimensional, denominada dendrograma,

de agrupaciones (clusters) de diferentes objetos cuyas relaciones subyacen en la
matriz de datos

• Existen alrededor de 150 técnicas diferentes de clustering, clasificadas en función del

principio de aglomeración utilizado

• Cualquiera de esas técnicas de clustering utiliza al menos dos elementos: la métrica de

distancia y las reglas de aglomeración

• La combinación de ambos factores permite clasificar los objetos partiendo de una

configuración inicial en la que cada uno pertenece a una clase distinta
independientemente de la distancia existente entre ellos

CLUSTERING JERÁRQUICO (2)

• A través de un proceso iterativo se van agrupando los objetos más próximos, al

tiempo que se sube en el nivel de la jerarquía, lo que permite representar las
agrupaciones en forma de árbol

• Entre las reglas de aglomeración más usadas encontramos:

• agrupamiento simple (single linkage), también denominado método del vecino

más cercano (nearest neighbor method),

• agrupamiento completo (complete linkage) o método del vecino más lejano

(furthest neighbor method),

• agrupamiento promedio (average linkage), y

• método de Ward o método de la suma de cuadrados (sum of squares method)

• La regla de aglomeración óptima es aquella que permite la mejor

interpretación de la estructura de cada espacio n-dimensional concreto

CLUSTERING JERÁRQUICO (3)

Clustering basado en Ward de Co-citación de Autores en Biblioteconomía (Moya-Anegón et al. 1998)

ANÁLISIS DE COMPONENTES PRINCIPALES (1)

• El análisis factorial es un método de análisis multivariante que intenta

explicar un conjunto extenso de variables observables mediante un
número reducido de variables hipotéticas llamadas factores comunes sin
perder información ni capacidad explicativa

• El PCA se basa en que no hay factores comunes específicos sino que

cada factor debe explicar el máximo de la variabilidad inicial de los datos

• Se asume que las variables son susceptibles de ser reducidas a factores

comunes, es decir, que cada factor esta presente en mayor o menor grado
en todas las variables

ANÁLISIS DE COMPONENTES PRINCIPALES (2)

Mapa PCA 3D de Co-citación de Autores en Biblioteconomía (Moya-Anegón et al. 1998)

ESCALADO MULTIDIMENSIONAL (1)

• El MDS incluye u