Representación matricial de un grafo. Cada dimensión se representa en un eje paralelo a los de las demás dimensiones. En este caso en cada fila y columna se hallan miembros del Xerorx PARC y se puede ver quien colabora con quien Fuente: Tesis doctoral de Natalie Henry. Pulsa sobre la imagen para agrandarla

En el mundo real y, especialmente en Internet, las relaciones entre individuos, objetos y conceptos tienen una importancia creciente. Por poner un ejemplo, ¿quién no está conectado hoy en día a una o más redes sociales? Éstas se han hecho ubicuas y forman un vasto entramado de relaciones profesionales y de ocio en las que tejemos nuestros intereses.

Por tanto, las redes se han convertido en importantes fuentes de información. ¿Cómo visualizarlas de forma efectiva? 

Desde un punto de vista matemático una red se puede considerar como un grafo (véase también el artículo 137). Cada elemento de un grafo (también llamado nodo) puede estar relacionado con otros elementos del mismo. Cada relación se denomina arco, arista o también enlace.

La representación tradicional de un grafo consiste en un conjunto de puntos que representan los nodos unidos por unas líneas que unen aquellos nodos relacionados. No obstante, cuando el número de nodos se empieza a hacer elevado (por encima de unos 20 nodos y 20-30 enlaces para algunos autores*), los problemas de oclusión entre enlaces e incluso entre los propios nodos comienzan a prevalecer y hacen muy difícil la comprensión y la interacción con la representación.

Una representación alternativa que, pese a su relativo desconocimiento, resulta muy útil  es la matricial.

Para nuestros efectos la representación matricial de un grafo es una disposición en filas y columnas en las que cada fila y cada columna representa un nodo (por ejemplo una persona) y en las intersecciones entre ellas se coloca un 0 o un 1 (o un cuadrado de color o su ausencia) para denotar que hay un enlace entre los nodos correspondientes.

Así pues lo que pintamos es una matriz booleana de conectividad, también llamada matriz de adyacencia. Fijémonos que ello nos permite visualizar enlaces uno a uno, uno a muchos y muchos a uno de manera muy sencilla.

Obviamente el paradigma matricial se puede extender más allá de la matriz de adyacencia asignando una variable visual como por ejemplo el color a cada celda en función del valor de una variable como por ejemplo el tráfico de un enlace web o el número de publicaciones de las que dos nodos son co-autores.

La disposición matricial garantiza que no hay oclusión ni entre enlaces ni entre nodos. Por otro lado el estudio de los patrones visuales que surgen permite identificar agrupaciones y "comunidades" permutando el orden de filas y columnas de manera que los nodos más enlazados mutuamente se encuentren cercanos. 

Siendo más sistemáticos, las ventajas e inconvenientes de tal representación son, siguiendo la tesis doctoral de Nathalie Henry y el artículo antes mencionado, los siguientes

Ventajas

• Ausencia de oclusión entre los nodos, lo que permite siempre leer su etiqueta.
   
• No hay cruzamiento entre enlaces , lo que permite identificar fácilmente el origen y el destino del enlace.
   
• Fácil identificación de la ausencia de conexiones.
   
• Supera sistemáticamente a los grafos en diferentes tareas como contar nodos, encontrar enlaces etc cuando el número de nodos supera los 20.

Inconvenientes

• Para un mismo nivel de detalle se requiere un espacio mayor que en el grafo tradicional.
   
• Para redes pequeñas (<20 nodos, 20-30 enlaces) el grafo es más efectivo.
   
• Mayor dificultad para seguir caminos (por ejemplo del nodo A al B pasando por el C)
   
• Falta de familiaridad, constituyen un paradigma mucho menos conocido e intuitivo.

J. Bertin, lamentablemente desaparecido hace apenas unas semanas, ya presentaba en su libro Semiologie Graphique la matriz reordenable. Efectivamente, el poder permutar el orden de las filas y columnas apropiadamente permite entender mejor la estructura de los enlaces e identificar características haciendo aflorar patrones de nuestro interés.

En cierta forma lo que Bertin viene a decir es que la matriz nos proporciona una representación válida pero lo que la hace usable es escoger una ordenación apropiada de filas y columnas.

Equivalencia entre la representación matricial y en forma de grafo: en A se aprecia un actor que une  varias comunidades, en B dos comunidades y en C un clique. Fuente: Tesis doctoral de Nathalie Henry. Pulsa sobre la imagen para agrandarla

En particular se pueden detectar

• Cliques todos los miembros de un clique están conectados entre si. Se asocian con grupos sociales muy cohesionados
   
• Comunidades, en las que los miembros están interconectados de manera menos cohesionada, no todos tiene que estar interconectados entre si.
   
• Actores individuales
   
• Influencias y relaciones entre los elementos anteriores.

Sin embargo la permutación de la ordenación en las filas y columnas no es única, de forma que es posible obtener distintas vistas de las comunidades que forman una red social.

No es fácil escoger qué reordenación es la idónea en general. Es claro que diferentes reordenaciones dan lugar a diferentes vistas y, por tanto a diferentes aproximaciones al problema. Cuál sea la mejor es un aspecto clave de la utilidad que se le puede dar y depende muy probablemente de las necesidades del usuario, esto es, del objetivo que perseguimos al analizar una red social.

Las representaciones matriciales se han utilizado con éxito en el estudio de las publicaciones científicas para indagar, a base de las citaciones y co-autorías qué investigadores trabajan  más a menudo juntos, cuales son las relaciones profesionales entre ellos, los campos en los que se desenvuelven, quines son los investigadores principales, etc.

En el campo del análisis de patentes, como ya vimos en el número 167 se han utilizado profusamente para detectar alianzas entre empresas y comunidades de investigadores que trabajan colaborativamente entre distintas instituciones o dentro de las mismas.

Pero hay muchas más aplicaciones que se benefician de este tipo de representación y permiten encontrar grupos sociales que comparten hábitos de compra o grupos de personas conectados mediante la telefonía móvil que pueden tener intereses comunes.

No es difícil imaginar el interés que una visualización reveladora puede tener a la hora de tomar decisiones de Mercadotecnia que afecten a redes sociales de tamaño considerable. No obstante cuanto más grande son las redes más complejo resulta adquirir conocimiento. La visualización tiene un largo recorrido en este campo.

On the readability of graphs using node-link and matrix based representations: a controlled experiment and statistical analysis. Information Visualization (2005) 4, 114–135, Palgrave Mac Millan

Dedicado a la memoria de Jacques Bertin

Enlaces de este artículo: