Sparse stress minimization: Difference between revisions
Jump to navigation
Jump to search
(Created page with "content will follow.") |
No edit summary |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
=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, <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 === | |||
The computation of the sparse stress layout requires <math>O(m+np)</math> time and space and a <math>O(p(m+n \log n))</math> preprocessing time. | |||
=== Parameters & Their Influence === | |||
* By its iterative nature the quality of the stress minimized layout depends on the initialization. Therefore, we recommend to check the "init with PivotMDS" box. | |||
* The number of pivots influences the quality of the final layout. A higher number of pivots increases the quality, but also space and running time. | |||
* The pivot strategy allows to choose between various (pivot) sampling strategies. We recommend K_MEANS_SSSP as it has advantages over the other routines respective the layout quality. However if time is the most important factor we recommend Random. The other two strategies are a compromise between quality and running time. | |||
* The link lengths defines the distance between adjacent nodes in the euclidean space and is used for the shortest-path computation. | |||
* The maximum number of iterations defines after how many executions of the iterative stress minimization algorithm the procedure should stop. A higher number of iterations results in a higher quality. | |||
* Given the case that the layouts of two consecutive iterations of the sparse stress algorithm differ only by a very small amount we say that the algorithm has converged. Since, often the number of iterations is often higher than necessary, we recommend to check the "stop on convergence" box to decrease the running time of the algorithm. | |||
Latest revision as of 17:28, 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.
Complexity
The computation of the sparse stress layout requires time and space and a preprocessing time.
Parameters & Their Influence
- By its iterative nature the quality of the stress minimized layout depends on the initialization. Therefore, we recommend to check the "init with PivotMDS" box.
- The number of pivots influences the quality of the final layout. A higher number of pivots increases the quality, but also space and running time.
- The pivot strategy allows to choose between various (pivot) sampling strategies. We recommend K_MEANS_SSSP as it has advantages over the other routines respective the layout quality. However if time is the most important factor we recommend Random. The other two strategies are a compromise between quality and running time.
- The link lengths defines the distance between adjacent nodes in the euclidean space and is used for the shortest-path computation.
- The maximum number of iterations defines after how many executions of the iterative stress minimization algorithm the procedure should stop. A higher number of iterations results in a higher quality.
- Given the case that the layouts of two consecutive iterations of the sparse stress algorithm differ only by a very small amount we say that the algorithm has converged. Since, often the number of iterations is often higher than necessary, we recommend to check the "stop on convergence" box to decrease the running time of the algorithm.