Format

Send to

Choose Destination
See comment in PubMed Commons below
IEEE Trans Vis Comput Graph. 2017 Mar 29. doi: 10.1109/TVCG.2017.2689016. [Epub ahead of print]

Drawing Large Graphs by Multilevel Maxent-Stress Optimization.

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.

PMID:
28368821
DOI:
10.1109/TVCG.2017.2689016
PubMed Commons home

PubMed Commons

0 comments
How to join PubMed Commons

    Supplemental Content

    Full text links

    Icon for IEEE Engineering in Medicine and Biology Society
    Loading ...
    Support Center