Dibujo de gráficos dirigidos por fuerzas

Los algoritmos de dibujo de grafos dirigidos por fuerzas son una clase de algoritmos para dibujar grafos de forma estéticamente agradable. Su propósito es posicionar los nodos de un grafo en un espacio bidimensional o tridimensional de manera que todas las aristas tengan una longitud más o menos igual y haya la menor cantidad posible de aristas que se crucen, asignando fuerzas entre el conjunto de aristas y el conjunto de nodos, en función de sus posiciones relativas, y luego utilizando estas fuerzas para simular el movimiento de las aristas y los nodos o para minimizar su energía. ^{[ 2 ]}

Si bien el dibujo de gráficos puede ser un problema difícil, los algoritmos dirigidos por fuerzas, al ser simulaciones físicas, generalmente no requieren conocimientos especiales sobre teoría de gráficos, como la planaridad .

Los algoritmos de dibujo de grafos dirigidos por fuerzas asignan fuerzas entre el conjunto de aristas y el conjunto de nodos de un grafo . Típicamente, se utilizan fuerzas atractivas tipo resorte basadas en la ley de Hooke para atraer pares de extremos de las aristas del grafo entre sí, mientras que simultáneamente se utilizan fuerzas repulsivas como las de partículas cargadas eléctricamente basadas en la ley de Coulomb para separar todos los pares de nodos. En estados de equilibrio para este sistema de fuerzas, las aristas tienden a tener una longitud uniforme (debido a las fuerzas elásticas), y los nodos que no están conectados por una arista tienden a dibujarse más separados (debido a la repulsión eléctrica). Las fuerzas de atracción de aristas y repulsión de vértices pueden definirse utilizando funciones que no se basan en el comportamiento físico de resortes y partículas; por ejemplo, algunos sistemas dirigidos por fuerzas utilizan resortes cuya fuerza atractiva es logarítmica en lugar de lineal.

Un modelo alternativo considera una fuerza elástica para cada par de nodos.${\displaystyle (i,j)}$donde la longitud ideal${\displaystyle \delta _{ij}}$La fuerza de cada resorte es proporcional a la distancia teórica de grafos entre los nodos i y j , sin utilizar una fuerza repulsiva adicional. Minimizar la diferencia (generalmente la diferencia al cuadrado) entre las distancias euclidianas e ideales entre los nodos equivale entonces a un problema de escalamiento métrico multidimensional .

Un grafo dirigido por fuerzas puede involucrar fuerzas distintas a los resortes mecánicos y la repulsión eléctrica. Se puede usar una fuerza análoga a la gravedad para atraer vértices hacia un punto fijo del espacio de dibujo; esto puede usarse para unir diferentes componentes conectados de un grafo desconectado, que de otro modo tenderían a separarse debido a las fuerzas repulsivas, y para dibujar nodos con mayor centralidad en posiciones más centrales del dibujo; ^{[ 3 ]} también puede afectar el espaciado de los vértices dentro de un solo componente. Se pueden usar análogos de campos magnéticos para grafos dirigidos. Se pueden colocar fuerzas repulsivas tanto en aristas como en nodos para evitar superposiciones o casi superposiciones en el dibujo final. En dibujos con aristas curvas, como arcos circulares o curvas spline , también se pueden colocar fuerzas en los puntos de control de estas curvas, por ejemplo, para mejorar su resolución angular . ^{[ 4 ]}

Una vez definidas las fuerzas que actúan sobre los nodos y las aristas de un grafo, se puede simular su comportamiento como si se tratara de un sistema físico . En dicha simulación, las fuerzas se aplican a los nodos, acercándolos o separándolos. Este proceso se repite iterativamente hasta que el sistema alcanza un estado de equilibrio mecánico ; es decir, sus posiciones relativas no cambian entre iteraciones. Las posiciones de los nodos en este equilibrio se utilizan para generar un dibujo del grafo.

Para fuerzas definidas a partir de resortes cuya longitud ideal es proporcional a la distancia teórica de grafos, la mayorización de tensiones proporciona una forma muy bien comportada (es decir, monótonamente convergente ) ^{[ 5 ]} y matemáticamente elegante de minimizar estas diferencias y, por lo tanto, encontrar una buena disposición para el grafo.

También es posible emplear mecanismos que busquen de forma más directa los mínimos de energía, ya sea en lugar de la simulación física o en combinación con ella. Dichos mecanismos, que son ejemplos de métodos generales de optimización global , incluyen el recocido simulado y los algoritmos genéticos .

Las siguientes son algunas de las ventajas más importantes de los algoritmos basados ​​en fuerzas:

Resultados de buena calidad

Al menos para grafos de tamaño medio (hasta 50-500 vértices), los resultados obtenidos suelen ser de muy buena calidad según los siguientes criterios: longitud uniforme de las aristas, distribución uniforme de los vértices y simetría. Este último criterio es uno de los más importantes y resulta difícil de lograr con cualquier otro tipo de algoritmo.

Flexibilidad

Los algoritmos basados ​​en fuerzas se pueden adaptar y extender fácilmente para cumplir con criterios estéticos adicionales. Esto los convierte en la clase más versátil de algoritmos de dibujo de grafos. Algunos ejemplos de extensiones existentes incluyen las de grafos dirigidos, dibujo de grafos 3D, ^{[ 6 ]} dibujo de grafos de clústeres, dibujo de grafos con restricciones y dibujo de grafos dinámicos.

Intuitivo

Dado que se basan en analogías físicas de objetos comunes, como los resortes, el comportamiento de los algoritmos es relativamente fácil de predecir y comprender. Esto no ocurre con otros tipos de algoritmos de dibujo de grafos .

Sencillez

Los algoritmos típicos basados ​​en fuerzas son sencillos y pueden implementarse en pocas líneas de código. Otros tipos de algoritmos para dibujar grafos, como los de diseños ortogonales, suelen ser mucho más complejos.

Interactividad

Otra ventaja de este tipo de algoritmos es su interactividad. Al dibujar las etapas intermedias del grafo, el usuario puede seguir su evolución, observando cómo se desarrolla desde un enredo desordenado hasta una configuración armoniosa. En algunas herramientas interactivas de dibujo de grafos, el usuario puede desplazar uno o más nodos de su estado de equilibrio y observar cómo vuelven a su posición original. Esto las convierte en la opción preferida para sistemas de dibujo de grafos dinámicos y en línea .

Sólidos fundamentos teóricos

Si bien los algoritmos ad hoc simples dirigidos por fuerza aparecen con frecuencia en la literatura y en la práctica (debido a su relativa facilidad de comprensión), los enfoques más razonados están empezando a ganar terreno. Los estadísticos han estado resolviendo problemas similares en escalamiento multidimensional (MDS) desde la década de 1930, y los físicos también tienen una larga trayectoria trabajando con problemas de n cuerpos relacionados , por lo que existen enfoques extremadamente maduros. Como ejemplo, el enfoque de mayorización de estrés para MDS métrico se puede aplicar al dibujo de grafos como se describió anteriormente. Se ha demostrado que esto converge monótonamente . ^{[ 5 ]} La convergencia monótona, la propiedad de que el algoritmo disminuirá en cada iteración el estrés o el costo del diseño, es importante porque garantiza que el diseño eventualmente alcanzará un mínimo local y se detendrá. Los programas de amortiguación hacen que el algoritmo se detenga, pero no pueden garantizar que se alcance un verdadero mínimo local.

Las principales desventajas de los algoritmos basados ​​en fuerzas incluyen las siguientes:

Alto tiempo de funcionamiento

En general, se considera que los algoritmos típicos dirigidos por fuerza se ejecutan en tiempo cúbico (${\displaystyle O(n^{3})}$), dónde${\displaystyle n}$es el número de nodos del grafo de entrada. Esto se debe a que se estima que el número de iteraciones es lineal (${\displaystyle O(n)}$), y en cada iteración, se deben visitar todos los pares de nodos y calcular sus fuerzas repulsivas mutuas. Esto está relacionado con el problema de N cuerpos en física. Sin embargo, dado que las fuerzas repulsivas son de naturaleza local, el grafo se puede particionar de manera que solo se consideren los vértices vecinos. Las técnicas comunes utilizadas por los algoritmos para determinar la disposición de grafos grandes incluyen la incrustación de alta dimensión, ^{[ 7 ]} el dibujo multicapa y otros métodos relacionados con la simulación de N cuerpos . Por ejemplo, el método FADE ^{[ 8 ]} basado en la simulación de Barnes-Hut puede mejorar el tiempo de ejecución para que sea linealítmico, o${\displaystyle n\log(n)}$por iteración. Como guía aproximada, en unos pocos segundos se puede esperar dibujar como máximo 1000 nodos con un estándar${\displaystyle n^{2}}$por técnica de iteración y 100.000 con una${\displaystyle n\log(n)}$por técnica de iteración. ^{[ 8 ]} Los algoritmos dirigidos por fuerza, cuando se combinan con un enfoque de agrupamiento de grafos, pueden dibujar grafos de millones de nodos. ^{[ 9 ]}

Mínimos locales deficientes

Es fácil ver que los algoritmos dirigidos por fuerza producen un grafo con energía mínima, en particular uno cuya energía total es solo un mínimo local . El mínimo local encontrado puede ser, en muchos casos, considerablemente peor que un mínimo global, lo que se traduce en un dibujo de baja calidad. Para muchos algoritmos, especialmente aquellos que solo permiten movimientos descendentes de los vértices, el resultado final puede verse fuertemente influenciado por la disposición inicial, que en la mayoría de los casos se genera aleatoriamente. El problema de los mínimos locales deficientes se vuelve más importante a medida que aumenta el número de vértices del grafo. Una aplicación combinada de diferentes algoritmos es útil para resolver este problema. ^{[ 10 ]} Por ejemplo, usar el algoritmo Kamada-Kawai ^{[ 11 ]} para generar rápidamente una disposición inicial razonable y luego el algoritmo Fruchterman-Reingold ^{[ 12 ]} para mejorar la ubicación de los nodos vecinos. Otra técnica para lograr un mínimo global es usar un enfoque multinivel. ^{[ 13 ]}

Los métodos de dibujo de grafos basados ​​en fuerzas se remontan al trabajo de Tutte (1963) , quien demostró que los grafos poliédricos pueden dibujarse en el plano con todas las caras convexas fijando los vértices de la cara exterior de una incrustación planar del grafo en posición convexa , aplicando una fuerza atractiva tipo resorte en cada arista y dejando que el sistema alcance un equilibrio. ^{[ 14 ]} Debido a la simplicidad de las fuerzas en este caso, el sistema no puede quedarse atascado en mínimos locales, sino que converge a una única configuración óptima global. Por este motivo, las incrustaciones de grafos planares con caras convexas se denominan a veces incrustaciones de Tutte .

La combinación de fuerzas atractivas en vértices adyacentes y fuerzas repulsivas en todos los vértices fue utilizada por primera vez por Eades (1984) ; ^{[ 15 ]} Fruchterman y Reingold (1991) realizaron trabajos pioneros adicionales sobre este tipo de disposición dirigida por fuerzas . ^{[ 12 ]} La idea de utilizar únicamente fuerzas elásticas entre todos los pares de vértices, con longitudes de resorte ideales iguales a la distancia teórica de grafos de los vértices, proviene de Kamada y Kawai (1989) . ^{[ 11 ]}

• Cytoscape es un software para visualizar redes biológicas. El paquete básico incluye diseños basados ​​en fuerzas como uno de sus métodos integrados.
• Gephi , una plataforma interactiva de visualización y exploración para todo tipo de redes y sistemas complejos, gráficos dinámicos y jerárquicos.
• Graphviz es un software que implementa un algoritmo de diseño multinivel basado en fuerzas (entre muchos otros) capaz de manejar gráficos muy grandes.
• Tulip , software que implementa la mayoría de los algoritmos de diseño dirigidos por fuerza (GEM, LGL, GRIP, FM³).
• Prefusor

• di Battista, Giuseppe; Peter Eades ; Roberto Tamassia ; Ioannis G. Tollis (1999), Graph Drawing: Algorithms for the Visualization of Graphs , Prentice Hall, ISBN 978-0-13-301615-4
• Kaufmann, Michael; Wagner, Dorothea , eds. (2001), Drawing graphs: methods and models , Lecture Notes in Computer Science 2025, vol.  2025, Springer, doi : 10.1007/3-540-44969-8 , ISBN 978-3-540-42062-0, S2CID 1808286 

• Capítulo de libro sobre algoritmos de dibujo dirigidos por fuerza, de Stephen G. Kobourov.