Stress Majorisation

Stress Majorisation considers the ideas of the Kamada-Kawai model, but seeks to produce results in a more efficient manner. Work by Gasner et al. in [3] takes the idea of using majorisation from the area of multidimensional scaling and uses it to improve upon the work of Kamada-Kawai. The motivation cited in the literature is that majorisation produces significant advantages over the Newton-Raphson method in trying to reduce the stress of the physical system that is modelling the graph. Majorisation provides a guaranteed monotonic decrease of the stress, a higher probability of not getting stuck in local minima, and a shorter running time.

The same stress function is used in Stress Majorisation, that is used by Kamada-Kawai, as shown in Eq., however Stress Majorisation approximates the stress of the system differently. Stress majorisation simplifies the solving of the non convex stress function through the solving of quadratic functions that bound from above. This guarantees a monotonic decrease in stress. Like Kamada-Kawai it tries to iteratively find a solution for some layout $X(l)$ where $l$ is an iteration counter and in each iteration, $stress(X(l + 1)) < stress(X(l))$ . It is shown that attempting to solve the stress optimisation problem using stress majorisation is a lot more efficient and produces better layouts for graphs.