Document Open Access Logo

Force-Directed Embedding of Scale-Free Networks in the Hyperbolic Plane

Authors Thomas Bläsius, Tobias Friedrich , Maximilian Katzmann

PDF
Thumbnail PDF

File

LIPIcs.SEA.2021.22.pdf
  • Filesize: 8.79 MB
  • 18 pages

Document Identifiers

Author Details

Thomas Bläsius
  • Karlsruhe Institute of Technology, Germany
Tobias Friedrich
  • Hasso Plattner Institute, University of Potsdam, Germany
Maximilian Katzmann
  • Hasso Plattner Institute, University of Potsdam, Germany

Funding

This research was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - Grant No. 390859508.

Cite As Get BibTex

Thomas Bläsius, Tobias Friedrich, and Maximilian Katzmann. Force-Directed Embedding of Scale-Free Networks in the Hyperbolic Plane. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.SEA.2021.22

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Random projections and metric embeddings
Keywords
  • force-directed drawing algorithms
  • spring embedding
  • hyperbolic space

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Josh Barnes and Piet Hut. A hierarchical O(N log N) force-calculation algorithm. Nature, 324(6096):446-449, 1986. URL: https://doi.org/10.1038/324446a0.
  2. Thomas Bläsius, Tobias Friedrich, Anton Krohmer, and Sören Laue. Efficient embedding of scale-free graphs in the hyperbolic plane. In 24th Annual European Symposium on Algorithms, ESA 2016, pages 16:1-16:18, 2016. URL: https://doi.org/10.4230/LIPIcs.ESA.2016.16.
  3. Marián Boguñá, Fragkiskos Papadopoulos, and Dmitri Krioukov. Sustaining the internet with hyperbolic mapping. Nature Communications, 1(62), 2010. URL: https://doi.org/10.1038/ncomms1063.
  4. Markus Chimani, Carsten Gutwenger, Michael Jünger, Gunnar W. Klau, Karsten Klein, and Petra Mutzel. The Open Graph Drawing Framework (OGDF). In Handbook of Graph Drawing and Visualization, chapter 17. CRC Press, 2014. Google Scholar
  5. D. Eppstein and M. T. Goodrich. Succinct greedy geometric routing using hyperbolic geometry. IEEE Transactions on Computers, 60(11):1571-1580, 2011. URL: https://doi.org/10.1109/TC.2010.257.
  6. R. Gove. A Random Sampling O(n) Force-calculation Algorithm for Graph Layouts. Computer Graphics Forum, 38(3):739-751, 2019. URL: https://doi.org/10.1111/cgf.13724.
  7. Gaël Guennebaud, Benoît Jacob, et al. Eigen v3. http://eigen.tuxfamily.org, 2010. Google Scholar
  8. Luca Gugelmann, Konstantinos Panagiotou, and Ueli Peter. Random hyperbolic graphs: Degree sequence and clustering. In Automata, Languages, and Programming, pages 573-585, 2012. URL: https://doi.org/10.1007/978-3-642-31585-5_51.
  9. Stefan Hachul and Michael Jünger. Drawing large graphs with a potential-field-based multilevel algorithm. In Graph Drawing, 12th International Symposium, GD 2004, pages 285-295, 2004. URL: https://doi.org/10.1007/978-3-540-31843-9_29.
  10. Robert Kleinberg. Geographic routing using hyperbolic space. In 26th IEEE International Conference on Computer Communications, pages 1902-1909, 2007. URL: https://doi.org/10.1109/INFCOM.2007.221.
  11. Stephen G. Kobourov. Force-directed drawing algorithms. In Handbook of Graph Drawing and Visualization, chapter 12. CRC Press, 2014. Google Scholar
  12. Stephen G. Kobourov and Kevin Wampler. Non-euclidean spring embedders. IEEE Transactions on Visualization and Computer Graphics, 11(6):757-767, 2005. URL: https://doi.org/10.1109/TVCG.2005.103.
  13. Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguñá. Hyperbolic geometry of complex networks. Physical Review E, 82(3):036106, 2010. URL: https://doi.org/10.1103/PhysRevE.82.036106.
  14. John Lamping, Ramana Rao, and Peter Pirolli. A focus+context technique based on hyperbolic geometry for visualizing large hierarchies. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, pages 401-408, 1995. URL: https://doi.org/10.1145/223904.223956.
  15. Tamara Munzner. H3: Laying out large directed graphs in 3d hyperbolic space. In Proceedings of the 1997 IEEE Symposium on Information Visualization (InfoVis '97), pages 2-10, 1997. URL: https://doi.org/10.1109/INFVIS.1997.636718.
  16. Alessandro Muscoloni, Josephine Maria Thomas, Sara Ciucci, Ginestra Bianconi, and Carlo Vittorio Cannistraci. Machine learning meets complex networks via coalescent embedding in the hyperbolic space. Nature Communications, 8(1):1615, 2017. URL: https://doi.org/10.1038/s41467-017-01825-5.
  17. Fragkiskos Papadopoulos, Rodrigo Aldecoa, and Dmitri Krioukov. Network geometry inference using common neighbors. Physical Review E, 92(2):022807, 2015. URL: https://doi.org/10.1103/PhysRevE.92.022807.
  18. Fragkiskos Papadopoulos, Constantinos Psomas, and Dmitri Krioukov. Network mapping by replaying hyperbolic growth. IEEE/ACM Transactions on Networking, 23(1):198-211, 2015. URL: https://doi.org/10.1109/TNET.2013.2294052.
  19. Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015. URL: http://networkrepository.com.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact