Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2021.22
URN: urn:nbn:de:0030-drops-137944
URL: https://drops.dagstuhl.de/opus/volltexte/2021/13794/
Bläsius, Thomas ; Friedrich, Tobias ; Katzmann, Maximilian
Force-Directed Embedding of Scale-Free Networks in the Hyperbolic Plane
| pdf-format: |
|
Abstract
Force-directed drawing algorithms are the most commonly used approach to visualize networks. While they are usually very robust, the performance of Euclidean spring embedders decreases if the graph exhibits the high level of heterogeneity that typically occurs in scale-free real-world networks. As heterogeneity naturally emerges from hyperbolic geometry (in fact, scale-free networks are often perceived to have an underlying hyperbolic geometry), it is natural to embed them into the hyperbolic plane instead. Previous techniques that produce hyperbolic embeddings usually make assumptions about the given network, which (if not met) impairs the quality of the embedding. It is still an open problem to adapt force-directed embedding algorithms to make use of the heterogeneity of the hyperbolic plane, while also preserving their robustness.We identify fundamental differences between the behavior of spring embedders in Euclidean and hyperbolic space, and adapt the technique to take advantage of the heterogeneity of the hyperbolic plane.
BibTeX - Entry
@InProceedings{blasius_et_al:LIPIcs.SEA.2021.22,
author = {Bl\"{a}sius, Thomas and Friedrich, Tobias and Katzmann, Maximilian},
title = {{Force-Directed Embedding of Scale-Free Networks in the Hyperbolic Plane}},
booktitle = {19th International Symposium on Experimental Algorithms (SEA 2021)},
pages = {22:1--22:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-185-6},
ISSN = {1868-8969},
year = {2021},
volume = {190},
editor = {Coudert, David and Natale, Emanuele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13794},
URN = {urn:nbn:de:0030-drops-137944},
doi = {10.4230/LIPIcs.SEA.2021.22},
annote = {Keywords: force-directed drawing algorithms, spring embedding, hyperbolic space}
}
| Keywords: | force-directed drawing algorithms, spring embedding, hyperbolic space | |
| Seminar: | 19th International Symposium on Experimental Algorithms (SEA 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 31.05.2021 | |
| Supplementary Material: | Software (Source Code): https://github.com/maxkatzmann/hyperbolic-spring-embedder.git archived at: https://archive.softwareheritage.org/swh:1:dir:7b9445f64fae3be4bbe3a692c2f94ded0bc600d1 |
