The layout is computed by iteration using a simulating annealing strategy.
iterate M-times
foreach v in V do
disp(v)=0; // vector containing displacement for v
foreach u in V and u != v do
d = v.pos - u.pos; // vector pointing from u to v
disp(v) = disp(v) + (d/norm(d)) * fr(norm(d)) // fr is repulsive force
foreach e in E do
d = v.pos - u.pos; // e = {v,u}
disp(v) = disp(v) - (d/norm(d)) * fa(norm(d))
disp(u) = disp(u) + (d/norm(d)) * fa(norm(d))
foreach v in V do
/* limit max displacement to frame; use temperature t to scale */
v.pos = v.pos + (disp(v)/norm(disp(v)) * min(t,norm(disp(v))
/* check that node is in window, otherwise clip */
v.pos.x = min(W/2, max(-W/2, v.pos.x))
v.pos.y = min(L/2, max(-L/2, v.pos.y))
t = cool(t) ; /* reduce temperature for next iteration */
The forces acting on a node are: \[ \mathbf{f}_a = \frac{d^2}{k} \hat{\mathbf{r}} \qquad \mathbf{f}_r = \frac{-k^2}{d} \hat{\mathbf{r}} \] with distance \(d\) between the nodes, and choose \(k\) to optimize distance between nodes in the drawing area: \[ k = C \sqrt{\frac{\text{area}}{\text{nr. of vertices}}} \]
Assumption: real-world graph follows a power-law distribution of degrees, i.e., many leave nodes surrounding a few highly connected nodes. This results in cluttering around these nodes. Improve visualization by making repulsive force dependent on the node's degree
Repulsion force between two nodes \(n_1\) and \(n_2\) (repulsion by degree): \[ \mathbf{f}_r = k_r \frac{(deg(n_1)+1)(deg(n_2)+1)}{d(n_1,n_2)} \]
The attracting force between two nodes \(n_1\) and \(n_2\) is \[ \mathbf{f}_a(n_1,n_2) = d(n_1,n_2) \]