License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2019.5
URN: urn:nbn:de:0030-drops-102445
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10244/
Go to the corresponding LIPIcs Volume Portal

Friedrich, Tobias

From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial)

pdf-format:
LIPIcs-STACS-2019-5.pdf (3 MB)

Abstract

Network science is driven by the question which properties large real-world networks have and how we can exploit them algorithmically. In the past few years, hyperbolic graphs have emerged as a very promising model for scale-free networks. The connection between hyperbolic geometry and complex networks gives insights in both directions:
(1) Hyperbolic geometry forms the basis of a natural and explanatory model for real-world networks. Hyperbolic random graphs are obtained by choosing random points in the hyperbolic plane and connecting pairs of points that are geometrically close. The resulting networks share many structural properties for example with online social networks like Facebook or Twitter. They are thus well suited for algorithmic analyses in a more realistic setting.
(2) Starting with a real-world network, hyperbolic geometry is well-suited for metric embeddings. The vertices of a network can be mapped to points in this geometry, such that geometric distances are similar to graph distances. Such embeddings have a variety of algorithmic applications ranging from approximations based on efficient geometric algorithms to greedy routing solely using hyperbolic coordinates for navigation decisions.

BibTeX - Entry

@InProceedings{friedrich:LIPIcs:2019:10244,
  author =	{Tobias Friedrich},
  title =	{{From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial)}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{5:1--5:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Rolf Niedermeier and Christophe Paul},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10244},
  doi =		{10.4230/LIPIcs.STACS.2019.5},
  annote =	{Keywords: Graph Theory, Graph Algorithms, Network Science, Hyperbolic Geometry}
}

Keywords: Graph Theory, Graph Algorithms, Network Science, Hyperbolic Geometry
Collection: 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Issue Date: 2019
Date of publication: 12.03.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI