The Hyperbolic Geometry of Networks

• Applicant: Professor Tobias Friedrich, Ph.D.
• Subject Area: Theoretical Computer Science
• Term: since 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 390859508

This project aims to uncover the structural and algorithmic properties that dictate the behavior of real-world networks. Traditional theoretical models often fall short on predicting the efficiency of algorithms within complex networks. Hyperbolic Random Graphs (HRGs) and Geometric Inhomogeneous Random Graphs (GIRGs) share several key properties of real-world networks like heterogeneity and high clustering. Guided by the principal features of these two models, we aim to close the gap between theoretical predictions and practical algorithmic outcomes. The broader impact of this work lies in its potential to establish new mathematical insights for complex networks that are represented well by the model. As an extension of our previous work, we are analyzing structures that are fundamental for algorithmic performances. One of our main focuses lies on studying structural properties of HRGs and GIRGs, such as the chromatic number, the notion of temperature and directed edges. Furthermore, we want to use these structural properties to compute efficient algorithms for vertex coloring and diameter computation. In parallel, we aim to explore the effect of dimensionality on real-world networks and in which dimension they actually lie. Finally, we want to transfer hyperbolic space knowledge to other domains, such as the fundamental SAT problem and distributed computing.

• DFG Programme: Research Grants