Dibujo de un gráfico dirigido por fuerzas

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

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

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

Efectivo

Los algoritmos de dibujo de grafos dirigidos por fuerzas asignan fuerzas entre el conjunto de aristas y el conjunto de nodos de un dibujo de grafo . Normalmente, se utilizan fuerzas de atracción similares a las de los resortes basadas en la ley de Hooke para atraer pares de puntos finales de las aristas del grafo entre sí, mientras que simultáneamente se utilizan fuerzas repulsivas como las de las 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 del resorte), y los nodos que no están conectados por una arista tienden a estar más separados (debido a la repulsión eléctrica). Las fuerzas de atracción de aristas 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 fuerzas utilizan resortes cuya fuerza de atracción es logarítmica en lugar de lineal.

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

Un grafo dirigido por fuerzas puede involucrar fuerzas distintas a resortes mecánicos y repulsión eléctrica. Una fuerza análoga a la gravedad puede usarse para jalar vértices hacia un punto fijo del espacio de dibujo; esto puede usarse para juntar diferentes componentes conectados de un grafo desconectado, que de otra manera tenderían a separarse unos de otros debido a las fuerzas repulsivas, y para dibujar nodos con mayor centralidad en posiciones más centrales en el dibujo; ^[3] también puede afectar el espaciado de vértices dentro de un solo componente. Se pueden usar análogos de campos magnéticos para grafos dirigidos. Las fuerzas repulsivas pueden colocarse en los bordes así como en los nodos para evitar la superposición o casi superposición en el dibujo final. En dibujos con bordes curvos 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]

Métodos

Una vez que se han definido las fuerzas sobre los nodos y los bordes de un grafo, se puede simular el comportamiento de todo el grafo bajo estas fuentes como si fuera un sistema físico. En una simulación de este tipo, las fuerzas se aplican a los nodos, acercándolos o alejá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 grafo.

Para fuerzas definidas a partir de resortes cuya longitud ideal es proporcional a la distancia gráfica teórica, la mayorización del estrés 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 de manera más directa los 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 el recocido simulado y los algoritmos genéticos .

Ventajas

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

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 en función de 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 es difícil de conseguir con cualquier otro tipo de algoritmo.
Flexibilidad: Los algoritmos dirigidos por fuerza se pueden adaptar y ampliar fácilmente para cumplir con criterios estéticos adicionales. Esto los convierte en la clase más versátil de algoritmos de dibujo de gráficos. Entre los ejemplos de extensiones existentes se incluyen los de gráficos dirigidos, el dibujo de gráficos en 3D, ^[6] el dibujo de gráficos en clúster, el dibujo de gráficos restringidos y el 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. Esto no sucede con otros tipos de algoritmos de dibujo de gráficos .
Sencillez: Los algoritmos típicos de dirección de 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 complejos.
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 pasar de un lío enredado a 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 vuelven a su posición original. Esto las convierte en la opción preferida para los sistemas de dibujo de gráficos dinámicos y en línea .
Sólidas bases teóricas: Si bien los algoritmos simples dirigidos por fuerza ad hoc suelen aparecer en la literatura y en la práctica (porque son relativamente fáciles de entender), los 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 tensión para MDS métrico se puede aplicar al dibujo de gráficos como se describió anteriormente. Se ha demostrado que esto converge de manera monótona . ^[5] La convergencia monótona, la propiedad de que el algoritmo en cada iteración disminuirá la tensión 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 amortiguamiento hacen que el algoritmo se detenga, pero no pueden garantizar que se alcance un mínimo local verdadero.

Desventajas

Las principales desventajas de los algoritmos dirigidos por fuerza 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 ( ), 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, 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 gráfico se puede particionar 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 basado en simulación de Barnes-Hut FADE ^[8] puede mejorar el tiempo de ejecución para que sea lineal 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 fuerza, cuando se combinan con un enfoque de agrupamiento de gráficos, pueden dibujar gráficos de millones de nodos. ^[9] $O(n^{3})$ ${\estilo de visualización n}$ $O(n)$ ${\estilo de visualización n\log(n)}$ ${\estilo de visualización n^{2}}$ ${\estilo de visualización n\log(n)}$

Mínimos locales pobres: 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 los que solo permiten movimientos descendentes de los vértices, el resultado final puede estar 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 pobres 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, 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 colocació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 grafos 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 plana del grafo en la posición convexa , colocando una fuerza atractiva similar a un resorte en cada borde y dejando que el sistema se asiente en un equilibrio. ^[14] Debido a la naturaleza simple de las fuerzas en este caso, el sistema no puede quedarse atascado en mínimos locales, sino que converge a una configuración óptima global única. Debido a este trabajo, las incrustaciones de grafos planares 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 trabajos pioneros adicionales sobre este tipo de diseño dirigido por fuerzas. ^[12] La idea de utilizar solo fuerzas de resorte entre todos los pares de vértices, con longitudes de resorte ideales iguales a la distancia teórica de los vértices, es de Kamada y Kawai (1989). ^[11]

Véase también

Cytoscape , software para visualizar redes biológicas. El paquete básico incluye diseños dirigidos por fuerza como uno de los métodos integrados.
Gephi , una plataforma de visualización y exploración interactiva para todo tipo de redes y sistemas complejos, gráficos dinámicos y jerárquicos.
Graphviz , un 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 dirigidos por fuerza (GEM, LGL, GRIP, FM³).
Prefusible

Referencias

^ 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.
^ Kobourov, Stephen G. (2012), Incrustadores de resortes y algoritmos de dibujo de gráficos dirigidos por fuerza , arXiv : 1201.3011 , Bibcode :2012arXiv1201.3011K.
^ Bannister, MJ; Eppstein, D .; Goodrich, MT ; Trott, L. (2012), "Dibujo de gráficos dirigido por fuerza utilizando gravedad social y escalado", Proc. 20th Int. Symp. Graph Drawing , arXiv : 1209.0748 , Bibcode :2012arXiv1209.0748B.
^ Chernobelskiy, R.; Cunningham, K.; Goodrich, MT ; Kobourov, SG; Trott, L. (2011), "Dibujo de grafos al estilo Lombardi dirigido por fuerza", Actas del 19.° Simposio sobre dibujo de grafos (PDF) , págs. 78-90.
^ ab 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.
^ Vose, Aaron. «Visualizador de árboles filogenéticos en 3D» . Consultado el 3 de junio de 2012 .
^ Harel, David ; Koren, Yehuda (2002), "Dibujo de gráficos mediante incrustación de alta dimensión", Actas del 9.º Simposio internacional sobre dibujo de gráficos , Springer, págs. 207-219, CiteSeerX 10.1.1.20.5390 , ISBN 3-540-00158-1
^ ab Quigley, Aaron; Eades, Peter (2001), "FADE: Dibujo de gráficos, agrupamiento y abstracción visual", Actas del 8º Simposio internacional sobre dibujo de gráficos (PDF) , págs. 197-210, ISBN 3-540-41554-8.
^ "Una galería de gráficos grandes" . Consultado el 22 de octubre de 2017 .
^ Collberg, Christian; 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 de 2003 sobre visualización de software (SoftVis '03), Nueva York, NY, EE. UU.: ACM, págs. 77-86, figuras 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 los cálculos de Fruchterman-Reingold puedan "ordenar" rápidamente el diseño.
^ ab 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.
^ ab 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.
^ http://jgaa.info/accepted/2003/Walshaw2003.7.3.pdf Un algoritmo multinivel para el dibujo de gráficos dirigidos por fuerza
^ Tutte, WT (1963), "Cómo dibujar un gráfico", Actas de la London Mathematical Society , 13 (52): 743–768, doi :10.1112/plms/s3-13.1.743.
^ 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, Dorothea , 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, S2CID1808286

Enlaces externos

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