KIT | KIT-Bibliothek | Impressum | Datenschutz

Force-directed embedding of scale-free networks in the hyperbolic plane

Bläsius, Thomas ORCID iD icon; Friedrich, T.; Katzmann, M.


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.

Verlagsausgabe §
DOI: 10.5445/IR/1000135203
Veröffentlicht am 12.07.2021
DOI: 10.4230/LIPIcs.SEA.2021.22
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2021
Sprache Englisch
Identifikator ISBN: 978-3-9597718-5-6
ISSN: 1868-8969
KITopen-ID: 1000135203
Erschienen in 19th International Symposium on Experimental Algorithms (SEA 2021). Ed.: D. Coudert
Veranstaltung 19th International Symposium on Experimental Algorithms (SEA 2021), Nizza, Frankreich, 07.06.2021 – 09.06.2021
Verlag Schloss Dagstuhl - Leibniz-Zentrum für Informatik (LZI)
Seiten Art.-Nr.: 22
Serie Leibniz International Proceedings in Informatics (LIPIcs) ; 190
Schlagwörter force-directed drawing algorithms, spring embedding, hyperbolic space
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page