Die Hyperbolische Geometrie von Netzwerken

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

Dieses Projekt zielt darauf ab, die strukturellen und algorithmischen Eigenschaften zu entschlüsseln, die das Verhalten von realen Netzwerken bestimmen. Traditionelle theoretische Modelle sind oft nicht ausreichend, um die Effizienz von Algorithmen in komplexen Netzwerken vorherzusagen. Hyperbolische Zufallsgraphen (HRGs) und geometrisch inhomogene Zufallsgraphen (GIRGs) weisen mehrere Schlüsseleigenschaften von realen Netzwerken auf, wie Heterogenität und hohe Clusterbildung. Basierend auf den Merkmale der beiden Modelle, streben wir danach, die Lücke zwischen theoretischen Vorhersagen und praktischen algorithmischen Ergebnissen zu schließen. Die breitere Auswirkung dieser Arbeit liegt in ihrem Potenzial, neue mathematische Einsichten für komplexe Netzwerke zu etablieren, die durch das Modell gut repräsentiert werden. Als Erweiterung unserer vorherigen Arbeiten analysieren wir Strukturen, die grundlegend für die Leistung von Algorithmen sind. Einer unserer Schwerpunkte liegt auf der Untersuchung struktureller Eigenschaften von HRGs und GIRGs, wie die chromatische Zahl, der Begriff der Temperatur und gerichtete Kanten. Darüber hinaus möchten wir diese strukturellen Eigenschaften nutzen, um effiziente Algorithmen für die Knotenfärbung und die Berechnung des Durchmessers zu entwickeln. Parallel dazu wollen wir den Einfluss der Dimensionalität auf reale Netzwerke erforschen und in welcher Dimension sie tatsächlich liegen. Abschließend möchten wir das Wissen über den hyperbolischen Raum auf andere Bereiche übertragen, wie das grundlegende SAT-Problem und das verteilte Rechnen.

• DFG-Verfahren: Sachbeihilfen