Friedrich, Tobias
From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial)
Abstract
Network science is driven by the question which properties large realworld networks have and how we can exploit them algorithmically. In the past few years, hyperbolic graphs have emerged as a very promising model for scalefree 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 realworld 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 realworld network, hyperbolic geometry is wellsuited 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:15:9},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771009},
ISSN = {18688969},
year = {2019},
volume = {126},
editor = {Rolf Niedermeier and Christophe Paul},
publisher = {Schloss DagstuhlLeibnizZentrum 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}
}
12.03.2019
Keywords: 

Graph Theory, Graph Algorithms, Network Science, Hyperbolic Geometry 
Seminar: 

36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Issue date: 

2019 
Date of publication: 

12.03.2019 