TY  - GEN
A1  - Friedrich, Tobias
T1  - From graph theory to network science
BT  - the natural emergence of hyperbolicity (Tutorial)
T2  - 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
N2  - 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.
KW  - Graph Theory
KW  - Graph Algorithms
KW  - Network Science
KW  - Hyperbolic Geometry
Y1  - 2019
SN  - 978-3-95977-100-9
U6  - https://doi.org/10.4230/LIPIcs.STACS.2019.5
VL  - 126
PB  - Schloss Dagstuhl-Leibniz-Zentrum für Informatik
CY  - Dragstuhl
ER  -