NetLogo: Grafos

A pesar de que ya con anterioridad hemos hablado de los enlaces (links) como el tercer tipo de agentes que se puede manipular en Netlogo, hasta ahora no hemos trabajado con ellos, principalmente por el hecho de que necesitábamos conocer algunas técnicas de programación para poder sacarles todo el partido que nos puedan dar.

¿Para qué puede servir un grafo?

En muchos problemas que necesitamos modelar nos encontraremos que tan importantes como los objetos/entidades/individuos que intervienen son las relaciones/conexiones que se establecen entre ellos. Los grafos (o redes, que es como se conocen en áreas como la Física o las Ciencias Sociales) proporcionan la representación más flexible y sencilla de las que pueden servirte para representar esos dos niveles de la realidad: los objetos y sus relaciones.

Estas relaciones pueden ser reales o figuradas, es decir, admiten tanta abstracción como tú, modelador del problema, quieras darles, pudiendo representar conexiones físicas en el mundo real (por ejemplo, una red de carreteras que conectan entre sí pueblos de una determinada región, enlaces químicos entre átomos de una molécula, etc.) o relaciones abstractas que queremos analizar (por ejemplo, podemos conectar 2 números si tienen algún divisor común, relaciones semánticas entre palabras de un dominio, etc.).

Una vez representado nuestro problema con grafos, descubriremos que muchas de las preguntas que el fenómeno real nos plantea se traducen en preguntas similares en el modelo matemático. Así, conocer qué ciudad es la que ofrece mejores condiciones para, por ejemplo, colocar un centro de distribución de productos, y conocer qué número tiene mayor cantidad de divisores en común con la mayoría, son cuestiones que se traducen en analizar, en cada uno de los grafos asociados, el número y tipo de conexiones que los nodos que representan esos objetos del mundo real tienen.

Debido a que el mismo modelo matemático (el de los grafos) puede representar objetos y relaciones tan distintas entre sí, será necesario establecer primero algunas definiciones generales que nos permitan hablar de los mismos conceptos independientemente del origen del problema... y con ellos, buscar soluciones comunes a preguntas planteadas desde dominios y con objetivos completamente distintos.

En la actualidad, las redes sociales y fenómenos como el uso de internet y buscadores web han despertado en el gran público el interés por este tipo de objetos matemáticos, ya que muchos de los problemas “reales” sólo se pueden resolver de forma eficiente conociendo la teoría de grafos y/o modelando dichos problemas con alguna herramienta que permita realizar experimentos que arrojen alguna luz sobre aquellos para los que no se conoce una solución.

Antes de entrar en los detalles técnicos de cuáles son los comandos que permiten manipularlos con NetLogo, se aconseja hacer un breve repaso a los fundamentos de la teoría de Grafos por medio de cualquiera de los múltiples recursos que se pueden encontrar en internet o en libros.

Representación de Grafos en NetLogo

La forma de conseguir que NetLogo represente grafos por medio de los agentes que maneja pasa por construir agentes de tipo enlace (link) entre pares de agentes móviles (de tipo tortuga). De esta forma:

• los nodos del grafo estarán asociados a los agentes móviles, y
• las relaciones del grafo vendrán representadas por medio de agentes de enlace.

Es decir, en NetLogo, no sólo los nodos o vértices del grafo serán agentes que nos limitamos a conectar entre sí, sino que estas conexiones se establecen usando otro tipo de agentes, con lo que ello conlleva: que estas relaciones pueden tener sus propiedades particulares independientes de los nodos, pueden formar familias que enriquezcan la interpretación del modelo, pueden realizar acciones y tener comportamientos de manera que no sean elementos estáticos del modelo, etc. 

Ya comentamos que los links (enlaces) no son agentes móviles, en el sentido de que no puedo situarlos donde quiero, pero tampoco son estáticos, pues su posición depende de los agentes móviles que conecta y que sí se pueden desplazar. 

Las propiedades que por defecto tiene un link (que se pueden ampliar, como veremos, siguiendo el mismo método que en la definición de propiedades adicionales para los otros tipos de agentes) se muestran en la siguiente ventana de inspección, a la que se puede acceder, como en los otros casos, seleccionándola en el menú emergente que aparece al hacer cllic con el botón derecho sobre el enlace:

• end1, end2: representan los dos extremos del enlace, es decir, qué agentes móviles son los que quedan relacionados por él. El orden depende de cómo se haya formado el enlace, y será relevante para el caso en que el enlace sea dirigido (que, aunque podemos modificarlo, se representa por defecto como una flecha que parte de end1 y llega a end2). En cambio, si es no dirigido, end1 será siempre el que tenga identificador (who) más bajo.
• color, label, label-color, hidden?, breed, shape: tienen el mismo significado que en los agentes de tipo tortuga. 
• thickness: el grosor de la línea que se usa para representarlo en el mundo. Se mide en unidades de patch, siendo 0 la medida mínima, que se corresponde con un pixel. 
• tie-mode: establece si el enlace entre las dos tortugas hace que el movimiento de una de ellas afecte al de la otra. Esta propiedad, así como el concepto de ligadura, no las veremos en esta entrada.

Como hemos visto, los links pueden ser dirigidos o no dirigidos, pero existe una restricción importante: en cada familia de links sólo puede haber de un tipo. Esta restricción no es tal si tenemos en cuenta que podemos crear familias de links, por lo que la única exigencia que impone en este sentido NetLogo es que los enlaces se agrupen por familias. Sin embargo, sí existe otra restricción que, aunque salvable en la mayoría de los casos, puede limitar algunas de las posibilidades de modelado por medio de links: de cada familia, sólo podrá haber un enlace como máximo uniendo dos nodos, y no hay forma de enlazar un agente con él mismo... es decir, para cada familia de links definida, sólo se pueden definir grafos simples, no multigrafos. Sí está permitido que dos nodos se unan con diversos enlaces, siempre y cuando sean de familias distintas (o bien sean dirigidos y estén orientados en direcciones contrarias).

Nota: Lo anterior aplica también al caso en que no haya razas de links definidas, por lo que la raza por defecto, links (al igual que existían turtles y patches) tendrá que estar formada, o bien solo por enlaces dirigidos, o bien solo por enlaces no dirigidos. Qué tipo de enlaces contenga vendrá determinado por el primer link que se cree (si es dirigido, todos tendrán que ser dirigidos, si es no dirigido, todos tendrán que ser no dirigidos). Sin embargo, si se eliminan todos los links, el proceso puede empezar de nuevo y será el primer link nuevo el que determine el tipo de los siguientes.

Cómo crear enlaces entre agentes

Como veremos, existen varias formas de crear enlaces que dependerán, entre otras cosas, del tipo de enlace que queremos crear. En general, para crear un enlace siempre es necesario que sea uno de los agentes el que se decida a crearlo (es decir, todos los comandos que veremos son comandos de tortuga). Los más comunes son:

• create-link-with agente2: El agente que lo ejecuta crea un link no dirigido con el agente2. En caso de que ya existiera este link, no produce ningún efecto.
• create-links-with conj-agentes: El agente que lo ejecuta crea un link no dirigido con cada uno de los agentes que hay en conj-agentes. Los enlaces que ya pudieran existir se omiten. 
• create-link-to agente2: El agente que lo ejecuta crea un link dirigido que comienza en él y acaba en agente2. En caso de que ya existiera este link, no produce ningún efecto.
• create-links-to conj-agentes: Idem.
• create-link-from agente2: El agente que lo ejecuta crea un link dirigido que comienza en agente2 y acaba en él. En caso de que ya existiera este link, no produce ningún efecto. 
• create-links-from conj-agentes: Idem.

Si quisiéramos crear razas de enlaces, éstas deben declararse en la cabecera del código, tal y como vimos para el resto de razas, pero debemos especificar si la raza contendrá enlaces dirigidos o no dirigidos usando un comando específico para cada caso:

undirected-link-breed [raza-links-plural raza-links-singular]
directed-link-breed [raza-links-plural raza-links-singular]

Y, posteriormente, por medio de la partícula -own podemos definir nuevas propiedades para los links (o razas de ellos).

Vamos a hacer como ejemplo un procedimiento que reciba como dato de entrada el número de nodos, y genere un grafo completo no dirigido con ese número de nodos (y todos los nodos conectados entre sí):

Observa dos detalles:

1. Realmente, en el procedimiento anterior cada link se intenta crear 2 veces. 
2. Los enlaces que se generan viven en el toro (que es la topología por defecto en NetLogo), esta es la razón por la que algunos de los enlaces se ven cruzando el mundo por los lados identificados, ya que buscan la distancia más corta (en el toro) para unir ambos nodos. Si no quieres que sea así, debes cambiar la topología para que no se identifiquen los límites. La siguiente imagen muestra el mismo grafo completo, pero en el que se han eliminado las identificaciones entre límites del mundo:

Al igual que al crear una tortuga podemos pedirle que inmediatamente tras el nacimiento realice un bloque de acciones, con los links podemos seguir el mismo procedimiento. Por ejemplo: 

provocará que el link recién creado se ponga de color rojo. Los enlaces tienen algunos comandos particulares que sólo tienen sentido en ellos, por ejemplo: link-length devuelve la longitud del enlace (la distancia entre sus extremos).

Pero no sólo se puede acceder a los links desde las tortugas sino que, una vez creado un link, éste puede acceder a sus dos extremos usando directamente las propiedades end1 y end2, o bien con el reporte both-ends, que devuelve el conjunto de agentes formado por sus dos extremos.

Si queremos eliminar todos lo links disponemos de la instrucción clear-links. Y los reportes booleanos que permiten preguntar si un objeto es un link, y qué tipo de link es son: is-link?, is-directed-link?, is-undirected-link?.

Pero lo interesante de los links no es sólo que establecen una relación entre dos agentes, sino que al establecerla generan entre los agentes una relación de vecindad similar a la que los patches tienen por su distribución en el plano: ahora, los vecinos de un agente serán aquellos otros agentes que están conectados con él por medio de links. Así como tenemos familias de enlaces, tendremos familias de vecinos para cada nodo. 

El reporte más simple para obtener los vecinos es link-neighbors, que devuelve todos los agentes que están conectados por medio de enlaces no dirigidos con el agente que ejecuta el reporte. Por ejemplo:

De forma análoga, si quisiéramos calcular los vecinos respecto de una raza que se haya definido de enlaces no dirigidos tenemos: raza-neighbors.

Para el caso de enlaces dirigidos tenemos dos posibilidades: pedir los vecinos que me apuntan a mí, o pedir los vecinos a los que yo apunto. Los comandos en el caso general son respectivamente: in-link-neighbors, out-link-neighbors. O en sus versiones para razas: in-raza-neighbors, out-raza-neighbors.

También podemos hacer que un agente pregunte directamente si otro está en su vecindad:

• link-neighbor? otra-tortuga (o raza-neighbor? otra-tortuga): devuelve true si existe un enlace no dirigido (o de tipo raza) entre la tortuga que ejecuta el reporte y otra-tortugat.
• in-link-neighbor? otra-tortuga (o in-raza-neighbor? otra-tortuga) : devuelve true si existe un enlace dirigido (o de tipo raza) que llega a la tortuga que ejecuta el reporte desde otra-tortuga.
• out-link-neighbor? otra-tortuga (o out-raza-neighbor? otra-tortuga): devuelve true si existe un enlace dirigido (o de tipo raza) que va desde la tortuga que ejecuta el reporte hasta otra-tortuga.

O, desde alguna de las tortugas, podemos encontrar el enlace que la une a otra (si existe, si no, los siguientes reportes devuelven nobody):

• link-with otra-tortuga (o raza-with otra-tortuga): devuelve el link no dirigido (o de tipo raza) entre la tortuga que ejecuta el reporte y otra-tortuga.
• in-link-from otra-tortuga (o in-raza-from otra-tortuga): devuelve el link dirigido (o de tipo raza) que va desde otra-tortuga hasta la tortuga que ejecuta el reporte.
• out-link-to otra-tortuga (o out-raza-to otra-tortuga): devuelve el link dirigido (o de tipo raza) que va desde la tortuga que ejecuta el reporte hasta la otra-tortuga.

De igual forma, si conocemos los dos agentes que están conectados, podemos acceder directamente al link que los une por medio del reporte:

link agente1 agente2

o sus equivalentes: directed-link agente1 agente2, raza-link agente1 agente2.

Por último, cada agente puede tener acceso directo al conjunto de enlaces que lo conectan ejecutando los siguientes reportes:

• my-links (o my-raza): Devuelve el conjunto de todos los enlaces no dirigidos (o de tipo raza) que están conectados con el agente.
• my-in-links (o my-in-raza): Devuelve el conjunto de todos los enlaces dirigidos (o de tipo raza) que apuntan al agente.
• my-out-links (o my-out-raza): Devuelve el conjunto de todos los enlaces dirigidos (o de tipo raza) que salen del agente.

Al igual que teníamos las instrucciones para formar conjuntos de agentes (de tortugas o de patches), podemos trabajar con conjuntos de links:

link-set valor
(link-set valor1 valor2...)

Devuelve el conjunto de enñaces formado por la unión de todos los enlaces que recibe como entrada, que pueden ser enlaces individuales, conjuntos de enlaces, nobody, o listas (incluso listas enlazadas) que contengan los anteriores. Por ejemplo: 

link-set [links] of turtles with [ color = blue ]

O, por ejemplo:

Podemos saber si algo es un conjunto de links por medio del reporte booleano is-link-set?. El reporte no-links devuelve el conjunto de enlaces vacío.

Representación visual de los grafos

Hasta el momento, simplemente podemos crear los enlaces, pero la distribución que tienen los nodos en el mundo no mantiene relación con la distribución del grafo que conforman. Normalmente suele ser complicado ver la distribución que hay entre los nodos si no se ordenan adecuadamente, y las relaciones que se establecen pueden llegar a ser tan complejas que muchas veces una buena distribución visual es el mejor modo de aproximarnos a entenderlas.

NetLogo proporciona algunos procedimientos de distribución automáticos (layouts) que puede ser conveniente conocer para poder extraer más conocimiento de las redes que construyas.

Distribución circular

La más simple de ellas es la representación circular:

layout-circle nodos r

Sitúa los nodos uniformemente distribuidos en un círculo centrado en el mundo con radio r. Por lo general, espera que nodos sea un conjunto de agentes, pero si se le pasa una lista de agentes usa el orden de la lista para ordenar los nodos por ángulos crecientes.

Distribución Radial

La distribución radial es interesante si tienes algo parecido a una estructura de árbol, porque cuantos más ciclos tenga tu grafo, menos clara puede quedar. El comando para conseguirla es:

layout-radial conj-nodos conj-enlaces raiz

toma como dato de entrada los nodos que se redistribuirán, los enlaces que se considerarán para la distribución (a diferencia de la distribución circular, donde no tiene sentido, ésta admite considerar sólo una familia de enlaces con la que se calculará la nueva distribución), y el agente que se convertirá en raíz del árbol. El proceso que sigue es:

1. Toma el agente que será raíz y lo sitúa en el origen del mundo.
2. Los agentes de conj-nodos que estén conectados con él por medio de conj-enlaces los sitúa en círculo alrededor de él.
3. Repite este proceso usando circunferencias concéntricas de radio creciente, y situando los nuevos nodos en los sectores cercanos a los nodos con los que están conectados (por medio de conj-enlaces).

Distribución Tutte

Esta distribución se calcula por aproximaciones sucesivas (se puede probar que converge a una posición estable). Su nombre viene del matemático William Thomas Tutte, que fue quien los propuso. El comando para ejecutarlo es:

layout-tutte nodos enlaces radio

Que, a grandes rasgos, ejecuta el siguiente algoritmo:

1. Los agentes que están conectados por enlaces, pero que no aparecen en nodos se sitúan en una circunferencia centrada en el mundo y del radio indicado. Debe haber, al menos, 3 agentes verificando esta condición.
2. Los agentes que están en nodos se sitúa de la siguiente forma: cada agente se sitúa en el centroide (centro geométrico o baricentro) del polígono formado por sus vecinos en enlaces.
3. Como es posible que la colocación secuencial de los agentes desplace el centroide de otros ya situados, el proceso se repite. Al demostrarse que hay convergencia, estas repeticiones llevan finalmente a una distribución estable.

Los agentes iniciales (que se sitúan en la circunferencia exterior) sirven para que el procedimiento iterado no colapse en un punto.

Distribución Spring

Pertenece a una colección de distribuciones basadas en fuerza, porque se consiguen modelando fuerzas de atracción y repulsión entre los agentes que intervienen. En este caso, se supone que intervienen dos tipos de fuerzas contrapuestas:

• Los agentes se repelen entre sí (como si fueran cargas eléctricas del mismo signo).
• Los enlaces actúan como muelles con una longitud ideal que, si es estirado o contraído, actúa como regulador de la distancia entre los agentes que están en sus extremos.

El comando para ejecutarlo es:

layout-spring nodos-S enlaces-S f-muelle long-muelle f-repulsion

Se deben tener en cuenta los siguientes detalles:

• Solo ordena los nodos que están en nodos-S, y considera como muelles los enlaces de enlaces-S. Los enlaces que puedan existir pero no estén en enlaces-S son ignorados, y los nodos que estén enlazados por enlaces-S a nodos-S pero no aparezcan serán tratados como puntos de anclaje y no se mueven.
• La f-muelle indica la dureza del muelle, la resistencia a cambiar de longitud (teniendo como ideal el valor long-muelle). Formalmente, es la fuerza que el muelle ejercería si su longitud cambia en 1 unidad (si su longitud es long-muelle, esta fuerza es 0). La dirección de la fuerza es opuesta al cambio, de forma que si el muelle se estira, sus nodos extremos estarán bajo una fuerza que los tiende a acercar, y si se contrae, intentará separarlos.
• La f-repulsion indica la repulsión que hay entre nodos. Formalmente es la fuerza que dos nodos que estuviesen a distancia 1 sentirían. Si no hubiera enlaces, los nodos tenderían a separarse continuamente, y es su acción conjunta con los muelles la que produce una distribución estable.
• Es un algoritmo de aproximación continua que, a diferencia de los demás (que aparecen en un paso ya estables) requiere habitualmente que nosotros indiquemos el número de repeticiones para alcanzar la distribución deseada (o incluso poner su llamada dentro de un botón forever de forma que podemos interactuar con ella en tiempo real).

Respecto a este tipo de algoritmos debes saber lo siguiente:

• Proporcionan buenos resultados cuando el número de nodos no es muy elevado, o no tienen una densidad excesiva (es decir, no tiene muchos enlaces en proporción al número de nodos).
• La implementación que incluye NetLogo impone longitud de arista uniforme, aunque visualmente la estabilidad pueda mostrar aristas de distinto tamaño debido a la influencia de las fuerzas repulsivas entre nodos.
• Debido a su baja dependencia de condiciones externas, es muy flexible, por lo que puede adaptarse añadiendo propiedades adicionales (fuerzas en una sola dirección para grafos dirigidos, implementable en 3D, mezcla con otros algoritmos, etc.)
• Es muy intuitivo en su funcionamiento, por lo que resulta más fácil que en otros algoritmos el ajuste de sus parámetros.
• Son relativamente fáciles de implementar.
• Permiten un comportamiento interactivo, como puedes observar en su uso en NetLogo.
• Se fundamentan en resultados teóricos sólidos.
• Como punto negativo, debe tenerse en cuenta que pueden precisar (si el grafo es muy grande) de muchas iteraciones.
• Y, por último, no siempre convergen a la mejor representación, sino que puede depender de la situación inicial de la que se parta, por lo que muchas veces se combinan con otras distribuciones que dan una aproximación inicial que se usa como punto de partida.