Sparse stress minimization

Sparse Stress Layout

Method

The sparse stress layout is a heuristic to approximate the (full) stress layout. The goal of the stress minimization is to find a layout, $x$, such that $\sum _{i<j}{w}_{ij}(||x_i-x_j||-d_{ij}{)}^2\text{ is as small as possible.}$ In other words stress minimization tries to find a layout in which the euclidean distance of each pair of nodes matches their graph-theoretical distance, i.e. shortest-path distance.

In comparison to the (full) stress minimization, sparse stress on the one hand requires less space and running time, but on the other hand the resulting layouts have a slightly lower quality. The space and running time reduction is achieved by restricting the stress function from $n^2$ to $m+np$ with $p$ denoting the number of pivots.

More detailed background information can be found in

• Mark Ortmann, Mirza Klimenta, and Ulrik Brandes: A sparse Stress Model, GD'16, 18-32, 2016.