24.5 Disposición espectral

Es una técnica de visualización de gráficos basada en el álgebra lineal, en particular en los valores y vectores propios de las matrices del gráfico.

Se toma la matriz de adyacencia del grafo (\(A\)) y a partir del número de enlaces que tiene cada nodo se construye una matriz diagonal (\(D\)). Con ellas se calcula la denominada matriz laplaciana: \(L = D - A\). Para la matriz laplaciana, su valor propio más pequeño es siempre 0. El segundo y tercer vector propio proporciona un trazado bidimensional donde ubicar los nodos. Se podría incluso usar tres dimensiones.

El trazado espectral trata de situar los nodos de tal forma que los nodos conectados estén cerca unos de otros, de forma similar al principio del force-directed-placement.

A menudo producen disposiciones que enfatizan la estructura global del gráfico. Se aplica principalmente a grafos no dirigidos. Adaptarlo a grafos dirigidos es más complicado. La visualización puede no ofrecer siempre la mejor claridad para ciertos detalles, especialmente en el caso de grafos de gran tamaño.