Sparse stress minimization: Difference between revisions

From visone manual
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 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 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.  
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

Complexity