ARS 101: Algoritmo Kamada-Kawai

Algoritmo de Kamada y Kawai

En su artículo, Kamada y Kawai proponen que, en algunos casos, la reducción del número de cruces de enlaces que posee una grafo no es un buen criterio estético para implementar un algoritmo de diseño de redes. Afirman que el saldo total de la disposición que se relaciona con las características individuales de la grafo es tan importante, o pueden considerarse más importante que la reducción de los cruces de eje en el gráfico dado un escenario particular. Kamada Kawai y calcula el saldo total del grafo, como la suma cuadrada de las diferencias entre la distancia ideal y la distancia real para todos los vértices mediante el cálculo:

por algún par de nodos i y j, donde  es la distancia ideal entre los vértices correspondientes a la ruta más corta entre los vértices, X es el conjunto de coordenadas 2D o 3D y  Kamada Kawai y eligen , donde como Cohen en [4] optó  o 1. Elegir  parece producir el mejor diseño como se evidencia en [ 3,23 ]. Kamada Kawai y utilizan el método de Newton-Raphson [10] para optimizar con respecto a un solo vértice. Al iterativamente realizar la solución para cada vértice se reduce el estrés en general.


Mediante la aproximación y minimizar la tensión en la ecuación [*], el método de Kamada - Kawai conserva el equilibrio total de un grafo, y produce diseños con pequeñas cantidades de los cruces de enlace.


Visualization of the Kamada-Kawai layout algorithm from Computational Legal Studies on Vimeo.

Referencias

Tomihisa Kamada, Satoru Kawai. An Algorithm for Drawing General Undirected Graphs. Information Processing Letters, 31:7-15, 1988.

Monash University