Dibujo de gráfico dirigido por fuerza

Simulación física para visualizar gráficos.

Visualización de redes sociales mediante un algoritmo de dibujo de gráficos dirigido por la fuerza ^[1]

Visualización de enlaces entre páginas en una wiki utilizando un diseño dirigido por la fuerza.

Los algoritmos de dibujo de gráficos dirigidos por fuerza son una clase de algoritmos para dibujar gráficos de una manera estéticamente agradable. Su finalidad es posicionar los nodos de un grafo en un espacio bidimensional o tridimensional de manera que todas las aristas tengan más o menos la misma longitud 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 usar estas fuerzas para simular el movimiento de los bordes y 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 la teoría de grafos, como la planaridad .

Efectivo

Los algoritmos de dibujo de gráficos dirigidos por fuerzas asignan fuerzas entre el conjunto de aristas y el conjunto de nodos de un dibujo de gráficos . Normalmente, se utilizan fuerzas de atracción tipo resorte basadas en la ley de Hooke para atraer pares de puntos finales de los bordes del gráfico 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 los estados de equilibrio de este sistema de fuerzas, los bordes tienden a tener una longitud uniforme (debido a las fuerzas del resorte) y los nodos que no están conectados por un borde tienden a separarse más (debido a la repulsión eléctrica). Las fuerzas de atracción de bordes y repulsión de vértices se pueden definir utilizando funciones que no se basan en el comportamiento físico de resortes y partículas; por ejemplo, algunos sistemas dirigidos por fuerza utilizan resortes cuya fuerza de atracción es logarítmica en lugar de lineal.

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

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

Métodos

Una vez definidas las fuerzas sobre los nodos y aristas de un gráfico, se puede simular el comportamiento de todo el gráfico bajo estas fuentes como si fuera un sistema físico. En tal simulación, las fuerzas se aplican a los nodos, acercándolos o separándolos. Esto se repite iterativamente hasta que el sistema llega a un estado de equilibrio mecánico ; es decir, sus posiciones relativas ya no cambian de una iteración a la siguiente. Las posiciones de los nodos en este equilibrio se utilizan para generar un dibujo del gráfico.

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 manera muy bien comportada (es decir, monótonamente convergente ) ^[5] y matemáticamente elegante de minimizar estas diferencias y, por lo tanto, encontrar un buen diseño. para el gráfico.

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

Ventajas

Entre las ventajas más importantes de los algoritmos dirigidos por la fuerza se encuentran las siguientes:

Resultados de buena calidad

Al menos para gráficos de tamaño mediano (hasta 50–500 vértices), los resultados obtenidos suelen tener muy buena calidad según los siguientes criterios: longitud uniforme de los bordes, distribución uniforme de los vértices y simetría. Este último criterio está entre los más importantes y es difícil de lograr con cualquier otro tipo de algoritmo.

Flexibilidad

Los algoritmos dirigidos por la fuerza se pueden adaptar y ampliar fácilmente para cumplir criterios estéticos adicionales. Esto los convierte en la clase más versátil de algoritmos de dibujo de gráficos. Los ejemplos de extensiones existentes incluyen las de gráficos dirigidos, dibujo de gráficos 3D, ^[6] dibujo de gráficos de grupo, dibujo de gráficos restringidos y dibujo de gráficos dinámicos.

Intuitivo

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

Sencillez

Los algoritmos típicos dirigidos por la fuerza son simples y se pueden implementar en unas pocas líneas de código. Otras clases de algoritmos de dibujo de gráficos, como los de diseños ortogonales, suelen ser mucho más complicados.

Interactividad

Otra ventaja de esta clase de algoritmo es el aspecto interactivo. Al dibujar las etapas intermedias del gráfico, el usuario puede seguir cómo evoluciona el gráfico, viéndolo evolucionar desde un enredo hasta una configuración atractiva. En algunas herramientas de dibujo de gráficos interactivos, el usuario puede sacar uno o más nodos de su estado de equilibrio y observar cómo regresan a su posición. Esto los convierte en la opción preferida para sistemas de dibujo de gráficos dinámicos y en línea .

Fuertes fundamentos teóricos

Si bien en la literatura y en la práctica aparecen a menudo algoritmos simples ad hoc dirigidos por la fuerza (porque son relativamente fáciles de entender), enfoques más razonados están comenzando 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 historia de trabajo con problemas relacionados de n-cuerpos , por lo que existen enfoques extremadamente maduros. Como ejemplo, el enfoque de mayorización de tensiones para MDS métrico se puede aplicar al dibujo de gráficos como se describe 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 mínimo local real.

Desventajas

Las principales desventajas de los algoritmos dirigidos por la fuerza incluyen las siguientes:

Alto tiempo de ejecución

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

Mínimos locales pobres

Es fácil ver que los algoritmos dirigidos por fuerza producen un gráfico con energía mínima, en particular uno cuya energía total es sólo 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 sólo permiten movimientos descendentes de los vértices, el resultado final puede verse fuertemente influenciado por el diseño 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 gráfico. Una aplicación combinada de diferentes algoritmos resulta útil para resolver este problema. ^[10] Por ejemplo, utilizando el algoritmo Kamada-Kawai ^[11] para generar rápidamente un diseño 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 utilizar un enfoque multinivel. ^[13]

Historia

Los métodos dirigidos por fuerza en el dibujo de gráficos se remontan al trabajo de Tutte (1963), quien demostró que se pueden dibujar gráficos poliédricos en el plano con todas las caras convexas fijando los vértices de la cara exterior de una incrustación plana del gráfico en superficies convexas. posición , colocando una fuerza de atracción similar a un resorte en cada borde y dejando que el sistema alcance el equilibrio. ^[14] Debido a la naturaleza simple de las fuerzas en este caso, el sistema no puede quedarse atrapado en mínimos locales, sino que converge a una configuración óptima global única. Debido a este trabajo, las incrustaciones de gráficos planos con caras convexas a veces se denominan 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 un trabajo pionero adicional sobre este tipo de diseño dirigido por la fuerza. ^[12] La idea de utilizar sólo fuerzas de resorte 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]

Ver también

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

Referencias

1. Grandjean, Martin (2015), "Introducción a la visualización de données, l'analyse de réseau en histoire", Geschichte und Informatik 18/19 (PDF) , págs.
2. Kobourov, Stephen G. (2012), Incrustadores de resorte y algoritmos de dibujo de gráficos dirigidos por fuerza , arXiv : 1201.3011 , Bibcode : 2012arXiv1201.3011K.
3. Barandilla, MJ; Eppstein, D .; Goodrich, MT ; Trott, L. (2012), "Dibujo de gráficos dirigido por la fuerza utilizando gravedad social y escala", Proc. 20° Int. Síntoma. Dibujo gráfico , arXiv : 1209.0748 , Bibcode : 2012arXiv1209.0748B.
4. Chernobelskiy, R.; Cunningham, K.; Goodrich, MT ; Kobourov, SG; Trott, L. (2011), "Dibujo de gráficos estilo Lombardi dirigido por la fuerza", Proc. XIX Simposio sobre dibujo de gráficos (PDF) , págs. 78–90.
5. de Leeuw, Jan (1988), "Convergencia del método de mayorización para escalamiento multidimensional", Journal of Classification , 5 (2), Springer: 163–180, doi :10.1007/BF01897162, S2CID  122413124.
6. Vose, Aarón. "Visor de árboles filogenéticos 3D" . Consultado el 3 de junio de 2012 .
7. Harel, David ; Koren, Yehuda (2002), "Dibujo de gráficos mediante incrustación de alta dimensión", Actas del noveno Simposio internacional sobre dibujo de gráficos , págs. 207-219, CiteSeerX 10.1.1.20.5390 , ISBN  3-540-00158-1
8. Quigley, Aaron; Eades, Peter (2001), "FADE: dibujo de gráficos, agrupación y abstracción visual", Actas del octavo simposio internacional sobre dibujo de gráficos (PDF) , págs. 197–210, ISBN 3-540-41554-8.
9. "Una galería de gráficos grandes" . Consultado el 22 de octubre de 2017 .
10. Collberg, cristiano; Kobourov, Stephen; Nagra, Jasvir; Pitts, Jacob; Wampler, Kevin (2003), "Un sistema para la visualización basada en gráficos de la evolución del software", Actas del Simposio ACM sobre visualización de software de 2003 (SoftVis '03), Nueva York, NY, EE. UU.: ACM, págs. 86, cifras en la pág. 212, doi :10.1145/774833.774844, ISBN 1-58113-642-0, S2CID  824991, Para lograr un diseño estéticamente agradable del gráfico, también es necesario emplear fuerzas de Fruchterman-Reingold modificadas, ya que el método Kamada-Kawai no logra métodos satisfactorios por sí solo, sino que crea un buen diseño aproximado para que Fruchterman- Los cálculos de Reingold pueden "ordenar" rápidamente el diseño.
11. Kamada, Tomihisa; Kawai, Satoru (1989), "Un algoritmo para dibujar gráficos generales no dirigidos", Information Processing Letters , 31 (1), Elsevier: 7–15, doi :10.1016/0020-0190(89)90102-6.
12. Fruchterman, Thomas MJ; Reingold, Edward M. (1991), "Dibujo de gráficos mediante colocación dirigida por fuerza", Software: práctica y experiencia , 21 (11), Wiley: 1129–1164, doi :10.1002/spe.4380211102, S2CID  31468174.
13. http://jgaa.info/accepted/2003/Walshaw2003.7.3.pdf Un algoritmo multinivel para el dibujo de gráficos dirigido por la fuerza
14. Tutte, WT (1963), "Cómo dibujar una gráfica", Actas de la Sociedad Matemática de Londres , 13 (52): 743–768, doi :10.1112/plms/s3-13.1.743.
15. Eades, Peter (1984), "Una heurística para el dibujo de gráficos", Congressus Numerantium , 42 (11): 149-160.

Lectura adicional

• di Battista, Giuseppe; Peter Eades ; Roberto Tamassia ; Ioannis G. Tollis (1999), Dibujo de gráficos: algoritmos para la visualización de gráficos , Prentice Hall, ISBN 978-0-13-301615-4
• Kaufmann, Michael; Wagner, Dorotea , eds. (2001), Dibujo de gráficos: métodos y modelos , Lecture Notes in Computer Science 2025, vol. 2025, Springer, doi :10.1007/3-540-44969-8, ISBN 978-3-540-42062-0, S2CID  1808286

Enlaces externos

• Capítulo de libro sobre algoritmos de dibujo dirigidos por fuerza de Stephen G. Kobourov
• Disertación de Daniel Tunkelang sobre diseño de gráficos dirigido por la fuerza