Meyerhenke, H., Nöllenburg, M., & Schulz, C. (2018). Drawing Large Graphs by Multilevel Maxent-Stress Optimization. IEEE Transactions on Visualization and Computer Graphics, 24(5), 1814–1827. https://doi.org/10.1109/tvcg.2017.2689016
E192-01 - Forschungsbereich Algorithms and Complexity
-
Journal:
IEEE Transactions on Visualization and Computer Graphics
-
ISSN:
1077-2626
-
Date (published):
2018
-
Number of Pages:
14
-
Peer reviewed:
Yes
-
Keywords:
Software; Computer Graphics and Computer-Aided Design; Optimization; Computer Vision and Pattern Recognition; Signal Processing; Computational modeling; Layout; Approximation algorithms; Force; Stress; Linear systems
-
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 the maxent-stress metric proposed by Gansner et al. (2013) that combines layout stress and entropy. As opposed to previous work, we do not solve the resulting 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 a single thread) while producing a comparable solution quality.
