Name
Abstract | ||
|---|---|---|
In some applications of graph visualization, input edges have associated target lengths. Dealing with these lengths is a challenge, especially for large graphs. Stress models are often employed in this situation. However, the traditional full stress model is not scalable due to its reliance on an initial all-pairs shortest path calculation. A number of fast approximation algorithms have been proposed. While they work well for some graphs, the results are less satisfactory on graphs of intrinsically high dimension, because some nodes may be placed too close together, or even share the same position. We propose a solution, called the maxent-stress model, which applies the principle of maximum entropy to cope with the extra degrees of freedom. We describe a force-augmented stress majorization algorithm that solves the maxent-stress model. Numerical results show that the algorithm scales well, and provides acceptable layouts for large, nonrigid graphs. This also has potential applications to scalable algorithms for statistical multidimensional scaling (MDS) with variable distances. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/TVCG.2012.299 | IEEE Transactions on Visualization and Computer Graphics |
Keywords | Field | DocType |
maxent-stress model,acceptable layout,force-augmented stress majorization algorithm,traditional full stress model,stress model,graph layout,fast approximation algorithm,extra degree,algorithm scale,graph visualization,large graph,data visualisation,maximum entropy principle,layout,approximation theory,graph drawing,computational modeling,graph theory,entropy,stress,force | Graph drawing,Graph theory,Approximation algorithm,Mathematical optimization,Indifference graph,Computer science,Algorithm,Theoretical computer science,Hopcroft–Karp algorithm,Stress majorization,1-planar graph,Longest path problem | Journal |
Volume | Issue | ISSN |
19 | 6 | 1941-0506 |
Citations | PageRank | References |
27 | 0.84 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Emden R. Gansner | 1 | 1117 | 115.32 |
| Yifan Hu | 2 | 85 | 5.50 |
| Stephen North | 3 | 442 | 19.56 |