24.4 Disposición force-directed
La idea del algoritmo es tratar los enlaces como si fuesen resortes. Cada resorte tiene una longitud natural controlada por un parámetro denominado de tensión. Si el resorte está “estirado”, aumenta su tensión y la disminuye acercando ambos nodos.
El algoritmo, de manera general, inicia ubicando los nodos de manera aleatoria y simula las fuerzas de manera iterativa hasta obtener una configuración estable, la cual se obtiene a medida se logra reducir el agregado de la tensión de todo el conjunto. Sucede rápido. En cada iteración modifica la disposición en función de la ubicación de los nodos en la iteración anterior y el nuevo cálculo.
Algunos algoritmos incorporan los nodos como partículas cargadas que producen una fuerza repulsiva que los separa entre sí. Dicha fuerza es inversamente proporcional al cuadrado de la distancia. En el paralelismo con el resorte, éste también actúa como un amortiguador. Si el resorte está apretado, también hay tensión y la libera alejando los nodos.
Minimiza los solapamientos en el gráfico, distribuye uniformemente los nodos y enlaces y organiza los elementos de modo que los enlaces tengan una longitud similar. Suele generar una disposición legible, útil para encontrar patrones y simetrías.
En términos de escalabilidad, puede contener decenas o cientos de nodos, pero manteniendo una relación de densidad nodo/enlace tal que \(enlaces < 4nodos\). De otro modo, se podrían formar bolas de pelo sin sentido.
Ejemplos de este tipo de configuraciones son: Fruchterman-Reingold, Kamada-Kawai y Barnes-Hut. Esta última en disposiciones 3D.
En el método de Fruchterman-Reingold, la fuerza de atracción para la distancia entre los nodos i, j es: \(f(d_{i,j}) = \frac{d_{i,j}^2}{k}\), y la fuerza de repulsión es \(f(d_{i,j}) = \frac{k}{d_{i,j}^2}\), siendo \(k = \sqrt{\frac{area}{\mid n\mid}}\), esta vez con área igual a la del lienzo y \(\mid n\mid\) el número de nodos.
24.4.1 Kamada-Kawai
En el método Kamada-Kawai, las fuerzas entre nodos están influidas por sus distancias teóricas, determinadas por las trayectorias geodésicas entre ellos. En geometría diferencial, una geodésica es el camino más corto entre dos puntos de una superficie curva, como la superficie de la Tierra. Sin embargo, en teoría de grafos, una geodésica se refiere al camino más corto entre dos nodos de un grafo, es decir, el número mínimo de nodos que hay que recorrer para conectar un nodo con el otro. En el contexto del algoritmo Kamada-Kawai, antes de que los nodos tengan posiciones definidas, sus distancias geodésicas se denotan como \(d_{ij}\). Una vez que los nodos se han posicionado en el espacio de visualización, sus distancias entre pares basadas en estas posiciones se representan como las distancias euclidianas \(d'_{ij}\).
La función de costo a minimizar es17 \(Tensión = \sum_{i=1}^{n-1}\sum_{j = i + 1}^{n}\frac{1}{2}k_{ij}{\left(\mid \mid y_i-y_j\mid \mid - l_{ij}\right)^2}\)
La distancia deseada entre los nodos \(i, j\) en la pantalla es \(l_{ij} = L \cdot d_{ij}\), donde L es la dimensión mas grande, alto o ancho, del área de visualización. Y \(k_{ij}\) representa la fuerza del resorte, \(k_{ij} = K/d_{ij}^2\). \(K\) es una constante que debe definir el usuario18. La constante \(K\) garantiza que los nodos más alejados en términos de distancia del grafo estarán separados una distancia de L en la visualización. Obsérvese, entonces, que la distancia deseada es inversamente proporcional a su distancia geodésica inicial.
A diferencia del Fruchterman-Reingold, en cada iteración el algoritmo mueve solo el nodo que más bajaría el nivel de Tensión.
https://coursepages2.tuni.fi/mttts17/wp-content/uploads/sites/136/2020/04/drv_2020_lecture13.pdf↩︎
Finalmente, se está calculando una proporción de la longitud del enlace respecto al área de visualización↩︎