Los algoritmos de dibujo de gráficos dirigidos por la fuerza son una clase de algoritmos para dibujar gráficos de una manera estéticamente agradable. Su propósito es colocar los nodos de un gráfico en un espacio bidimensional o tridimensional de manera que todos los bordes sean de más o menos igual longitud y haya el menor número 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 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 la fuerza, al ser simulaciones físicas, generalmente no requieren conocimientos especiales sobre la teoría de grafos, como la planitud .
Efectivo
Los algoritmos de dibujo de gráficos dirigidos por fuerza asignan fuerzas entre el conjunto de aristas y el conjunto de nodos de un dibujo de gráfico . Por lo general, las fuerzas de atracción similares a un resorte basadas en la ley de Hooke se usan para atraer pares de extremos de los bordes del gráfico hacia el otro, mientras que simultáneamente se usan 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, 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 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 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 de la teoría gráfica entre los nodos i y j , sin usar una fuerza repulsiva separada. Minimizar la diferencia (generalmente la diferencia al cuadrado) entre las distancias euclidiana e ideal entre nodos es equivalente a un problema de escalamiento multidimensional métrico .
Un gráfico de fuerza dirigida puede involucrar fuerzas distintas de los resortes mecánicos y la repulsión eléctrica. Puede usarse una fuerza análoga a la gravedad para tirar de los vértices hacia un punto fijo del espacio de dibujo; esto puede usarse para juntar diferentes componentes conectados de un gráfico desconectado, que de otra manera tenderían a separarse entre sí 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. Pueden usarse análogos de campos magnéticos para gráficos dirigidos. Se pueden colocar fuerzas repulsivas en los bordes y 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 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 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 más. 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 de la teoría del gráfico, la mayorización de la tensión 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 los mínimos de energía, ya sea en lugar de o junto con la simulación física. Dichos mecanismos, que son ejemplos de métodos generales de optimización global , incluyen algoritmos genéticos y de recocido simulado .
Ventajas
Las siguientes se encuentran entre las ventajas más importantes de los algoritmos dirigidos por la fuerza:
- Resultados de buena calidad
- Al menos para gráficos de tamaño medio (hasta 50-500 vértices), los resultados obtenidos suelen tener muy buenos resultados basados en los siguientes criterios: longitud de borde uniforme, distribución uniforme de vértices y mostrar simetría. Este último criterio se encuentra entre los más importantes y es difícil de conseguir con cualquier otro tipo de algoritmo.
- Flexibilidad
- Los algoritmos dirigidos por la 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. Ejemplos de extensiones existentes incluyen las de gráficos dirigidos, dibujo de gráficos en 3D, [6] dibujo de gráficos de conglomerados, 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 de 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 las de los diseños ortogonales, suelen ser mucho más complicadas.
- 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 y ver cómo se desarrolla de un enredo 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 verlos migrar de nuevo a su posición. Esto los convierte en una opción preferida para los sistemas de dibujo de gráficos dinámicos y en línea .
- Sólidos fundamentos teóricos
- Si bien los algoritmos simples ad-hoc dirigidos por la fuerza a menudo aparecen 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 escala multidimensional (MDS) desde la década de 1930, y los físicos también tienen una larga historia de trabajo con problemas relacionados con n-cuerpos , por lo que existen enfoques extremadamente maduros. A modo de ejemplo, el enfoque de mayorización de tensiones a MDS métricas se puede aplicar al dibujo de gráficos como se describe anteriormente. Se ha demostrado que esto converge de forma monótona. [5] La convergencia monótona, la propiedad de que el algoritmo en cada iteración disminuirá 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 funcionamiento
- En general, se considera que los algoritmos típicos dirigidos por la fuerza tienen un tiempo de ejecución equivalente a O (n 3 ), donde n 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 O (n) 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 N-cuerpos en física. Sin embargo, dado que las fuerzas repulsivas son de naturaleza local, el gráfico se puede dividir de manera 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 la incrustación de alta dimensión, [7] dibujo de múltiples capas 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 an * log (n) por iteración. Como una guía aproximada, en unos pocos segundos se puede esperar dibujar como máximo 1,000 nodos con una técnica estándar de n 2 por iteración y 100,000 con una técnica de * log (n) por iteración. [8] Los algoritmos dirigidos por la fuerza, cuando se combinan con un enfoque multinivel, pueden dibujar gráficos de millones de nodos. [9]
- Mínimos locales deficientes
- Es fácil ver que los algoritmos dirigidos por la fuerza producen un gráfico 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 cuesta abajo 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 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 es útil para resolver este problema. [10] Por ejemplo, usando 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 la fuerza en el dibujo de gráficos se remontan al trabajo de Tutte (1963) , quien mostró que los gráficos poliédricos se pueden dibujar 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 convexo. posición , colocando una fuerza de atracción similar a un resorte en cada borde y dejando que el sistema se establezca 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 hacia 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 usar solo fuerzas de resorte entre todos los pares de vértices, con longitudes de resorte ideales iguales a la distancia teórica de los gráficos de los vértices, es de Kamada y Kawai (1989) . [11]
Ver también
- Cytoscape , software para visualizar redes biológicas. El paquete básico incluye diseños dirigidos a la fuerza como uno de los 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 , software que implementa un algoritmo de diseño dirigido por fuerza multinivel (entre muchos otros) capaz de manejar gráficos muy grandes.
- Tulip , software que implementa la mayoría de los algoritmos de diseño dirigidos a la fuerza (GEM, LGL, GRIP, FM³).
- Prefuse
Referencias
- ↑ Grandjean, Martin (2015), "Introduction à la visualization de données, l'analyse de réseau en histoire", Geschichte und Informatik 18/19 (PDF) , págs. 109-128
- ^ Kobourov, Stephen G. (2012), Spring Embedders and Force-Directed Graph Drawing Algorithms , arXiv : 1201.3011 , Bibcode : 2012arXiv1201.3011K.
- ^ Bannister, MJ; Eppstein, D .; Goodrich, MT ; Trott, L. (2012), "Dibujo de gráficos dirigidos por la fuerza utilizando gravedad social y escala", Proc. 20 ° Int. Symp. Dibujo gráfico , arXiv : 1209.0748 , Código Bib : 2012arXiv1209.0748B.
- ^ Chernobelskiy, R .; Cunningham, K .; Goodrich, MT ; Kobourov, SG; Trott, L. (2011), "Dibujo gráfico estilo Lombardi dirigido por la fuerza", Proc. XIX Simposio sobre dibujo de gráficos (PDF) , págs. 78–90.
- ^ a b de Leeuw, Jan (1988), "Convergence of the majorization method for multidimensional scaling", Journal of Classification , Springer, 5 (2): 163–180, doi : 10.1007 / BF01897162.
- ^ Vose, Aaron. "Visor de árboles filogenéticos 3D" . Consultado el 3 de junio de 2012 .[ enlace muerto permanente ]
- ^ Harel, David ; Koren, Yehuda (2002), "Dibujo gráfico mediante incrustación de alta dimensión", Actas del 9º Simposio Internacional sobre Dibujo Gráfico , págs. 207–219, CiteSeerX 10.1.1.20.5390 , ISBN 3-540-00158-1
- ^ a b Quigley, Aaron; Eades, Peter (2001), "FADE: Dibujo de gráficos, agrupación y abstracción visual", Actas del 8º Simposio internacional sobre dibujo de gráficos (PDF) , págs. 197–210, ISBN 3-540-41554-8 (PDF) Verificar
|archive-url=
valor ( ayuda ) . - ^ "Una galería de grandes gráficos" . Consultado el 22 de octubre de 2017 .
- ^ Collberg, Christian; Kobourov, Stephen; Nagra, Jasvir; Pitts, Jacob; Wampler, Kevin (2003), "A System for Graph-based Visualization of the Evolution of Software", Actas del Simposio ACM 2003 sobre Visualización de Software (SoftVis '03) , Nueva York, NY, EE. UU .: ACM, págs. 77– 86, cifras en la pág. 212, doi : 10.1145 / 774833.774844 , ISBN 1-58113-642-0,
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í mismo, sino que crea un buen diseño aproximado para que los cálculos de Fruchterman-Reingold puedan "Ordene" rápidamente el diseño.
- ^ a b Kamada, Tomihisa; Kawai, Satoru (1989), "Un algoritmo para dibujar gráficos generales no dirigidos", Information Processing Letters , Elsevier, 31 (1): 7–15, doi : 10.1016 / 0020-0190 (89) 90102-6.
- ^ a b Fruchterman, Thomas MJ; Reingold, Edward M. (1991), "Dibujo de gráficos por ubicación dirigida por la fuerza", Software: práctica y experiencia , Wiley, 21 (11): 1129-1164, doi : 10.1002 / spe.4380211102.
- ^ http://jgaa.info/accepted/2003/Walshaw2003.7.3.pdf Un algoritmo multinivel para el dibujo de gráficos dirigido por la fuerza
- ^ Tutte, WT (1963), "Cómo dibujar un gráfico", Proceedings of the London Mathematical Society , 13 (52): 743–768, doi : 10.1112 / plms / s3-13.1.743.
- ^ Eades, Peter (1984), "A Heuristic for Graph Drawing", Congressus Numerantium , 42 (11): 149-160.
Otras lecturas
- 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), Dibujar gráficos: métodos y modelos , Lecture Notes in Computer Science 2025, 2025 , Springer, doi : 10.1007 / 3-540-44969-8 , ISBN 978-3-540-42062-0
enlaces externos
- Video del algoritmo Spring [enlace muerto al 27 de mayo de 2016]
- Visualización en vivo en flash + código fuente y descripción
- Disertación de Daniel Tunkelang sobre el diseño de gráficos dirigidos por la fuerza (código fuente disponible en Github )
- Algoritmo de mapa hiperasociativo
- Algoritmos de gráficos interactivos y dirigidos por fuerza en tiempo real utilizados en una herramienta de modelado de bases de datos en línea