Die Hyperbolische Geometrie von Netzwerken

• Antragsteller: Professor Tobias Friedrich, Ph.D.
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2018 bis 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 390859508

Netzwerkforschung wird durch die Frage angetrieben, welche strukturellen Eigenschaften große reale Netzwerke haben und wie man diese algorithmisch nutzen kann. Dabei hat sich die hyperbolische Geometrie, dank ihrer unerwarteten Verbindung zu komplexen Netzwerken, als nützliches Werkzeug erwiesen. Dieser Zusammenhang besteht in beiden Richtungen:Die Hyperbolische Geometrie bildet die Grundlage eines natürlichen und erklärenden Modells für reale Netzwerke. Diese hyperbolischen Zufallsgraphen erhält man durch eine zufällige Wahl von Punkten in der hyperbolischen Ebene, wobei Punktepaare genau dann verbunden werden, wenn ihre geometrische Distanz klein ist. Die resultierenden Graphen haben ähnliche strukturelle Eigenschaft wie große reale Netzwerken und eignen sich damit gut für realistische Laufzeitanalysen.Andererseits, von realen Netzwerken hin zur Geometrie, eignet sich die hyperbolische Geometrie sehr gut für metrische Einbettungen. Dabei werden die Knoten des Netzwerkes auf Punkte im Raum abgebildet, sodass geometrische und graphentheoretische Distanzen weitgehend übereinstimmen. Solche Einbettungen haben diverse algorithmische Anwendungen. Sie reichen von Approximationen basierend auf effizienten geometrischen Algorithmen hin zum Greedy Routing, einer Navigationsstrategie, die allein auf den Koordinaten der Knoten basiert.Unser Ziel ist es, das Verständnis dieses Zusammenhanges zwischen großen realen Netzwerken und der hyperbolischen Geometrie zu vertiefen. Um beide Richtungen dieser Beziehung abzudecken, wollen wir sowohl Eigenschaften von hyperbolischen Zufallsgraphen, als auch Einbettungen realer Netzwerke in den hyperbolischen Raum untersuchen. Die daraus gewonnenen Erkenntnisse wollen wir algorithmisch nutzen, indem wir beweisbar schnelle Algorithmen für hyperbolischen Zufallsgraphen entwickeln, die im Anschluss auch in der Praxis auf realen Netzwerken gut funktionieren.

• DFG-Verfahren: Sachbeihilfen
• Mitverantwortlich: Professor Dr. Thomas Bläsius