Drawing large graphs by multilevel maxent-stress optimization

DOI10.1007/978-3-319-27261-0_3MaRDI QIDQ2959740zbMATH OpenOpenAlexFDO

Authors Henning Meyerhenke, Martin Nöllenburg, Christian Schulz

Publication date 10 February 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.04383

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

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.

Recommendations

• scientific article; zbMATH DE number 2080097
• A Multilevel Algorithm for Force-Directed Graph-Drawing
• A Fast Multi-Scale Method for Drawing Large Graphs
• Graph Drawing
• Graph Drawing

Cited in

(11)

• Engineering a combinatorial Laplacian solver: lessons learned
• An experimental evaluation of multilevel layout methods
• Drawing Big Graphs Using Spectral Sparsification
• On multi-objective optimization aided drawing of special graphs
• Graph Drawing
• Multi-level graph drawing using infomap clustering
• Stochastic Gradient Descent Works Really Well for Stress Minimization
• Maxent-stress optimization of 3D biomolecular models
• scientific article; zbMATH DE number 7525513 (Why is no real title available?)
• A sparse stress model
• Data-driven graph drawing techniques with applications for conveyor systems

This page was built for publication: Drawing large graphs by multilevel maxent-stress optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2959740)