Sparse stress minimization: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
=Sparse Stress Layout= | =Sparse Stress Layout= | ||
===Method=== | ===Method=== | ||
The | The sparse stress layout is a heuristic to approximate the (full) stress layout. The goal of the stress minimization is to find a layout, <math>x</math>, such that <math>\sum_{i<j}w_{ij}(||x_i - x_j|| - d_{ij})^2 \text{ is as small as possible.}</math> 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 <math>n^2</math> to <math>m+np</math> with <math>p</math> denoting the number of pivots. | |||
More detailed background information can be found in | |||
* Mark Ortmann, Mirza Klimenta, and Ulrik Brandes: [https://dx.doi.org/10.1007/978-3-319-50106-2_2 A sparse Stress Model], GD'16, 18-32, 2016. | |||
=== Complexity === | === Complexity === | ||
Revision as of 17:10, 23 February 2017
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, , such that 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 to with 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.