Algoritmos de visualización de gráficos de potencia

Los algoritmos de visualización de gráficos de potencia  son una clase de algoritmos de visualización de gráficos de una manera estéticamente agradable. Su objetivo es organizar los nodos del gráfico en un espacio 2D o 3D para que todos los bordes tengan más o menos la misma longitud y minimizar el número de intersecciones de los bordes mediante la asignación de fuerzas a múltiples bordes y nodos en función de sus posiciones relativas, y luego mediante el uso de estas fuerzas para simular el movimiento de bordes y nodos, o para minimizar su energía [2] .

Si bien visualizar gráficos puede ser una tarea difícil, los algoritmos de fuerza, al ser modelos físicos, no suelen requerir conocimientos especiales en teoría de gráficos, como la planaridad de gráficos .

Fuerzas

Los algoritmos de visualización de gráficos de fuerza asignan fuerzas en un conjunto de aristas y nodos de un gráfico . Es común usar fuerzas atractivas similares a resortes basadas en la ley de Hooke para asignar fuerzas a pares de extremos de un borde de un gráfico. Al mismo tiempo, se utilizan fuerzas de repulsión, similares a la repulsión de partículas cargadas eléctricamente según la ley de Coulomb , para separar todos los pares de nodos. Para obtener un estado de equilibrio de este sistema de fuerzas, las aristas tienden a adquirir longitudes uniformes (debido a la acción de los resortes), y los nodos que no están conectados por una arista tienden a ubicarse a una distancia entre sí (debido a la acción de los resortes). la acción de fuerzas repulsivas). Las fuerzas de atracción (costillas) y las fuerzas de repulsión (nudos) se pueden definir mediante funciones que no se basan en el comportamiento físico de resortes y partículas. Por ejemplo, algunos sistemas de energía usan resortes cuyas fuerzas varían logarítmicamente en lugar de linealmente.

Un modelo alternativo considera fuerzas similares a las de un resorte para cada par de nodos, donde la longitud ideal de cada resorte es proporcional a la distancia en el gráfico entre los nodos i y j , y no se utilizan fuerzas de repulsión. Minimizar la diferencia (por lo general, el cuadrado de la diferencia) entre la distancia euclidiana y la distancia ideal entre los nodos es equivalente al problema de la métrica de escalamiento multivariable .

Un gráfico de fuerza puede utilizar otras fuerzas además de los resortes mecánicos y las fuerzas de repulsión de carga. Se puede usar una fuerza similar a la gravedad para tirar de los vértices hacia un punto fijo en el espacio de dibujo de gráficos. Esto se puede usar para reducir los diversos componentes conectados de un gráfico desconectado en un solo todo, de lo contrario, estas partes se separarían entre sí bajo la acción de fuerzas repulsivas. También le permite obtener nodos con una posición central mejorada en la Figura [3] . Esto también puede afectar el espacio entre vértices en el mismo componente conectado. Se pueden usar análogos de campos magnéticos para gráficos dirigidos. Las fuerzas de repulsión se pueden colocar en ambos bordes y nodos para evitar superposiciones o casi superposiciones en el dibujo final. En dibujos con bordes curvos, como arcos circulares o splines , las fuerzas también se pueden ubicar en los puntos de control de esas curvas, por ejemplo, para mejorar la resolución angular [4] .

Métodos

Una vez que se determinan las fuerzas en los nodos y los bordes, el comportamiento de todo el gráfico bajo estas fuerzas se puede modelar iterativamente como si fuera un sistema físico. En tal situación, las fuerzas que actúan sobre los nodos intentan acercarlos o alejarlos entre sí. Esto continúa hasta que el sistema llega a un estado de equilibrio mecánico , es decir, la posición de los nodos no cambia de una iteración a otra. La posición de los nodos en este estado de equilibrio se utiliza para generar el dibujo del gráfico.

Para las fuerzas definidas a partir de resortes cuya longitud ideal es proporcional a la distancia en el gráfico, la mayorización de la tensión produce un comportamiento muy bueno (es decir, convergencia monótona ) [5] y una forma matemáticamente elegante de minimizar esta diferencia y, por lo tanto, de una buena ubicación de los vértices del gráfico.

También se pueden utilizar mecanismos que busquen el mínimo de energía de forma más directa, en lugar de según un modelo físico. Dichos mecanismos, que son ejemplos de técnicas generales de optimización global , incluyen recocido simulado y algoritmos genéticos .

Beneficios

Las siguientes propiedades son las ventajas más importantes de los algoritmos de fuerza:

Resultados de buena calidad Al menos para gráficos de tamaño mediano (hasta 50-500 vértices), los resultados obtenidos suelen tener muy buenos patrones de gráficos para los siguientes criterios: uniformidad de longitudes de borde, distribución uniforme de vértices y simetría. El último criterio es el más importante y difícil de lograr en otros tipos de algoritmos. Flexibilidad Los algoritmos de fuerza se pueden adaptar y ampliar fácilmente para criterios estéticos adicionales. Esto hace que los algoritmos sean clases más generales de algoritmos de visualización de gráficos. Algunos ejemplos de extensiones existentes son los algoritmos de gráficos dirigidos, la visualización de gráficos en 3D [6] , la visualización de gráficos en clúster, la visualización de gráficos restringidos y la visualización de gráficos dinámicos. Intuición Dado que los algoritmos se basan en análogos físicos de objetos familiares como resortes, el comportamiento de los algoritmos es relativamente fácil de predecir y comprender. Esto no se encuentra en otros tipos de algoritmos de visualización de gráficos. Sencillez Los algoritmos de fuerza típicos son simples y se pueden implementar en unas pocas líneas de código. Otras clases de algoritmos de representación, como los que se basan en ubicaciones ortogonales, normalmente requieren mucho más trabajo. interactividad Otra ventaja de esta clase de algoritmos es el aspecto de la interactividad. Al dibujar las etapas intermedias del gráfico, el usuario puede seguir cómo cambia el gráfico, rastreando la evolución de un desorden desordenado a una configuración atractiva. En algunas herramientas de dibujo de gráficos interactivos, el usuario puede eliminar uno o más nodos del estado de equilibrio y observar cómo migran los nodos al nuevo estado de equilibrio. Esto le da a los algoritmos una ventaja para los sistemas de visualización de gráficos dinámicos y en línea Respaldo teórico estricto Si bien los algoritmos de fuerza simples aparecen a menudo en la literatura y en la práctica (porque son relativamente simples y comprensibles), la cantidad de enfoques más razonables está comenzando a aumentar. Los estadísticos han estado resolviendo problemas similares en el escalado multidimensional ( MDS ) desde la  década de 1930, y los físicos también tienen una larga historia de trabajo con problemas relacionados con el modelado del movimiento de n cuerpos , por lo que existen enfoques bastante maduros. Como ejemplo, el enfoque de mayorización de estrés para MDS métrico se puede aplicar a la visualización de gráficos, en cuyo caso se puede probar la convergencia monótona [5] . La convergencia monótona, la propiedad de que el algoritmo reducirá el estrés o el costo de colocar vértices en cada iteración, es importante porque asegura que la ubicación finalmente alcance un mínimo local y el algoritmo se detenga. La amortiguación de las oscilaciones hace que el algoritmo se detenga, pero no garantiza que se alcance un verdadero mínimo local.

Desventajas

Las principales desventajas de los algoritmos de fuerza:

gran tiempo de trabajo Generalmente se considera que los algoritmos de fuerza típicos tienen tiempos de ejecución equivalentes a O(n 3 ), donde n es el número de nodos en el gráfico de entrada. Esto se debe a que el número de iteraciones se estima en O(n), y en cada iteración es necesario observar todos los pares de nodos y calcular las fuerzas repulsivas mutuas. Esto es similar al problema de N-cuerpo en física. Sin embargo, dado que las fuerzas de repulsión son de naturaleza local, el gráfico se puede dividir de modo que solo se consideren los vértices vecinos. Las principales técnicas utilizadas por los algoritmos para determinar la ubicación de los nodos en gráficos grandes incluyen incrustaciones de alta dimensión [7] , representaciones en capas y otras técnicas relacionadas con el modelado del problema 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 a n*log(n) por iteración. Como estimación aproximada, en unos pocos segundos puede esperar dibujar un máximo de 1000 nodos con la técnica estándar n 2 por iteración y 100 000 con la técnica n*log(n) por iteración [8] . Los algoritmos de fuerza, cuando se combinan con un enfoque en capas, pueden dibujar gráficos con millones de nodos [9] . Mínimos locales malos Es fácil ver que el algoritmo de fuerza da un gráfico con energía mínima, en particular, solo puede ser un mínimo local . El mínimo local encontrado puede ser, en muchos casos, significativamente peor que el mínimo global, lo que conduce a una representación de mala calidad. Para muchos algoritmos, especialmente aquellos que solo permiten el movimiento de descenso de gradiente , el resultado final puede verse fuertemente influenciado por la posición inicial, que se genera aleatoriamente en la mayoría de los casos. El problema de un mínimo local incorrecto se vuelve especialmente importante a medida que crece el número de vértices del gráfico. La combinación de diferentes algoritmos ayuda a resolver este problema [10] . Por ejemplo, se puede utilizar el algoritmo de Kamada-Kawai [11] para generar rápidamente una ubicación inicial aceptable y luego el algoritmo de Fruchterman-Reinhold [12] para mejorar la posición de los nodos vecinos. Otra técnica para obtener un mínimo global es utilizar un enfoque multinivel [13] .

Historia

Los métodos de visualización de gráficos de fuerza se remontan al trabajo de Tutt [14] en el que mostró que los gráficos poliédricos se pueden dibujar en un plano con caras convexas fijando los vértices de la cara exterior de un gráfico plano incrustado en una posición convexa , colocando resortes. como fuerzas atractivas en cada borde y permitir que el sistema llegue a un estado de equilibrio [15] . En vista de la naturaleza simple de las fuerzas, en este caso el sistema no puede estancarse en un mínimo local, sino que converge a una única configuración global óptima. En vista de este artículo, las incrustaciones de gráficos planos con caras convexas a veces se denominan incrustaciones de Tutt .

Eads [16] [17] utilizó por primera vez la combinación de fuerzas de atracción de vértices adyacentes de un gráfico y fuerzas de repulsión para todos los vértices . Otro trabajo pionero sobre este tipo de colocación de fuerzas fue publicado por Fruchterman y Reingold [18] . La idea de usar solo fuerzas de resorte entre todos los pares de vértices con longitudes de resorte ideales iguales a la distancia del gráfico se debe a Kamada y Kawai [19] [11] .

Véase también

  • Cytoscape , un programa de visualización de redes biológicas. El paquete base incluye colocaciones forzadas como uno de los métodos integrados.
  • Gephi , plataforma interactiva de visualización y exploración de todo tipo de redes y sistemas complejos, grafos dinámicos y jerárquicos.
  • Graphviz , una herramienta de software que implementa un algoritmo de colocación de fuerza multinivel (entre otros) capaz de manejar gráficos muy grandes.
  • Tulip , una herramienta de software que implementa la mayoría de los algoritmos de colocación de fuerza (GEM, LGL, GRIP, FM³).
  • Prefuso

Notas

  1. ↑ Grandjean, 2015 , pág. 109–128.
  2. ↑ Kobúrov, 2012 .
  3. ↑ Bannister, Eppstein, Goodrich, Trott, 2012 .
  4. ↑ Chernobelskiy, Cunningham, Goodrich, Kobourov, Trott, 2011 , pág. 78–90.
  5. ↑ 1 2 de Leeuw, 1988 , p. 163-180.
  6. ↑ Vose, Aaron Visor de árboles filogenéticos 3D . Recuperado: 3 de junio de 2012.  (enlace inaccesible)
  7. ↑ Harel, Koren, 2002 , pág. 207-219.
  8. ↑ 1 2 Quigley, Eades, 2001 , pág. 197-210.
  9. ↑ Una galería de gráficos grandes . Consultado el 22 de octubre de 2017. Archivado desde el original el 25 de mayo de 2021.
  10. ↑ Collberg, Kobourov, Nagra, Pitts, Wampler, 2003 , pág. 77–86; Arroz. en la página 212.
  11. ↑ 1 2 Kamada, Kawai, 1989 , pág. 7-15.
  12. ↑ Fruchterman y Reingold 1991 , pág. 1129-1164.
  13. ↑ http://jgaa.info/accepted/2003/Walshaw2003.7.3.pdf Archivado el 12 de agosto de 2021 en Wayback Machine Un algoritmo multinivel para dibujar gráficos dirigidos por la fuerza
  14. ↑ Tutte, 1963 .
  15. ↑ Tutte, 1963 , pág. 743–768.
  16. ↑ Eades, 1984 .
  17. ↑ Eades, 1984 , pág. 149–160.
  18. ↑ Fruchterman y Reingold 1991 , p. 1129-1164.
  19. ↑ Kamada, Kawai, 1989 .

Literatura

  • Martín Grandjean. Introducción a la visualización de données, l'analyse de réseau en histoire // Geschichte und Informatik 18/19 . — 2015.
  • Stephen G. Kobourov. Spring Embedders y algoritmos de dibujo de gráficos dirigidos por fuerza . - 2012. - . -arXiv : 1201.3011 . _
  • Bannister M. J, Eppstein MJ, Goodrich MT, Trott L. Dibujo gráfico dirigido por la fuerza usando gravedad social y escalado // Proc. 20 Int. Síntoma dibujo gráfico. — 2012.
  • Chernobelskiy R., Cunningham K., Goodrich MT, Kobourov SG, Trott L. Dibujo gráfico estilo Lombardi dirigido por la fuerza // Proc. XIX Simposio de Dibujo de Gráficas . — 2011.
  • Jan de Leeuw. Convergencia del método de mayorización para escalamiento multidimensional // Journal of Classification. - Springer, 1988. - V. 5 , no. 2 . - S. 163-180 . -doi : 10.1007/ BF01897162 .
  • David Harel, Yehuda Koren. Dibujo de gráficos mediante incrustación de alta dimensión // Actas del 9º Simposio Internacional sobre Dibujo de Gráficos . - 2002. - S. 207-219. — ISBN 3-540-00158-1 .
  • Aaron Quigley, Peter Eades. FADE: Dibujo gráfico, agrupamiento y abstracción visual // Actas del 8.º Simposio internacional sobre dibujo gráfico . - 2001. - S. 197-210. — ISBN 3-540-41554-8 . Archivado el 21 de mayo de 2006 en Wayback Machine .
  • Christian Collberg, Stephen Kobourov, Jasvir Nagra, Jacob Pitts, Kevin Wampler. 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, 2003. - S. 77-86; figuras en pág. 212. - ISBN 1-58113-642-0 . doi : 10.1145 / 774833.774844 . Cita: Para obtener un diseño gráfico estéticamente agradable, es necesario utilizar fuerzas de Fruchterman-Reingold modificadas, ya que el método de Kamada-Kawai no da resultados satisfactorios, pero crea un buen diseño aproximado a partir del cual los cálculos de Fruchterman-Reingold pueden "terminar" rápidamente. el diseño
  • Tutte WT Cómo dibujar un gráfico // Actas de la London Mathematical Society. - 1963. - T. 13 , núm. 52 . -doi :/ plms/s3-13.1.743 .
  • Pedro Eades. Una heurística para dibujar gráficos // Congressus Numerantium. - 1984. - T. 42 , núm. 11 _
  • Thomas MJ Fruchterman, Edward M. Reingold. Dibujo de gráficos por colocación dirigida por la fuerza // Software: práctica y experiencia. - Wiley, 1991. - T. 21 , no. 11 _ -doi : 10.1002/ spe.4380211102 .
  • Tomihisa Kamada, Satoru Kawai. Un algoritmo para dibujar gráficos generales no dirigidos // Letras de procesamiento de información. - Elsevier, 1989. - T. 31 , no. 1 . - doi : 10.1016/0020-0190(89)90102-6 .

Lectura para leer más

  • Giuseppe di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Dibujo de Grafos: Algoritmos para la Visualización de Grafos. - Prentice Hall, 1999. - ISBN 978-0-13-301615-4 .
  • Dibujo de grafos: métodos y modelos / Michael Kaufmann, Dorothea Wagner. - Springer, 2001. - (Lecture Notes in Computer Science 2025). - ISBN 978-3-540-42062-0 . -doi : 10.1007 / 3-540-44969-8 .

Enlace