Abstract | ||
---|---|---|
Drawing large graphs appropriately is an important step for the visual analysis of data from real-world networks. Here we present a novel multilevel algorithm to compute a graph layout with respect to a recently proposed metric that combines layout stress and entropy. As opposed to previous work, we do not solve the linear systems of the maxent-stress metric with a typical numerical solver. Instead we use a simple local iterative scheme within a multilevel approach. To accelerate local optimization, we approximate long-range forces and use shared-memory parallelism. Our experiments validate the high potential of our approach, which is particularly appealing for dynamic graphs. In comparison to the previously best maxent-stress optimizer, which is sequential, our parallel implementation is on average 30 times faster already for static graphs and still faster if executed on one thread while producing a comparable solution quality. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1109/TVCG.2017.2689016 | IEEE Trans. Vis. Comput. Graph. |
Keywords | Field | DocType |
Layout,Stress,Computational modeling,Approximation algorithms,Linear systems,Force,Optimization | Graph,Approximation algorithm,Combinatorics,Data analysis,Linear system,Computer science,Algorithm,Thread (computing),Theoretical computer science,Local search (optimization),Solver,Graph Layout | Journal |
Volume | Issue | ISSN |
24 | 5 | 1077-2626 |
Citations | PageRank | References |
6 | 0.44 | 30 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Henning Meyerhenke | 1 | 522 | 42.22 |
Martin Nöllenburg | 2 | 114 | 23.79 |
Christian Schulz | 3 | 240 | 24.10 |