(openPR) „Um solche Veränderungen zu erfassen, betrachtet man nicht nur einen einzelnen Graphen, sondern eine ganze Folge von Graphen. Solche zeitabhängigen Strukturen werden temporale Graphen genannt“, sagt Professor Johannes Carmesin, Betreuer der Promotion von Will Turner an der TU Bergakademie Freiberg.
Im Zentrum der Forschung steht eine grundlegende Frage: Wann lässt sich eine Folge von Netzwerken so zeichnen, dass die einzelnen Darstellungen über die Zeit hinweg zueinander passen? Bei einem einzelnen Netzwerk ist diese Frage eng mit der klassischen Graphentheorie verbunden. Bei temporalen Graphen wird sie deutlich schwieriger, weil sich die Verbindungen zwischen den einzelnen Zeitschritten verändern können: „Man kann sich das wie eine Reihe von Karten desselben Verkehrsnetzes vorstellen, die zu verschiedenen Zeitpunkten aufgenommen wurden“, erklärt Professor Johannes Carmesin. „Wir wollen verstehen, wann diese Karten so zueinander passen, dass die Veränderung des Netzwerks konsistent dargestellt werden kann.“
Graphenminorentheorie auf zeitabhängige Netzwerke übertragen
Die neue Arbeit nutzt Methoden der sogenannten Graphenminorentheorie. Dieses Gebiet untersucht, wie sich große und komplexe Graphen auf kleinere Grundstrukturen zurückführen lassen. Die beiden Wissenschaftler der TU Bergakademie Freiberg übertragen diese Denkweise nun auf zeitabhängige Netzwerke. Für zweifach zusammenhängende temporale Graphen geben sie eine vollständige strukturelle Beschreibung und daraus folgend einen effizienten Algorithmus.
Das Ergebnis zeigt: Jeder temporale Graph lässt sich entweder Schritt für Schritt vereinfachen, ohne die entscheidende Information zu verlieren, oder er enthält eines von fünf in der Mathematik genau beschriebenen Hindernissen. Diese Hindernisse erklären, warum eine gemeinsame konsistente Darstellung nicht möglich ist.
Langfristig können die strukturellen Methoden dazu beitragen, dynamische Netzwerke besser algorithmisch zu analysieren — etwa wenn sich Kommunikationsnetze, Verkehrsflüsse oder Datenstrukturen im Laufe der Zeit verändern. Anwendungen der neuen Methoden entwickelt die TU Bergakademie Freiberg aktuell gemeinsam mit Forschenden des Hasso-Plattner-Instituts in Potsdam.
Forschung an der Schnittstelle von Mathematik und Informatik
Die Präsentation bei der Konferenz STOC knüpft an frühere Freiberger Erfolge an der Schnittstelle von Mathematik und Informatik an: Bereits 2023 wurden Ergebnisse zur kanonischen Zerlegung 3-zusammenhängender Graphen bei der Konferenz FOCS vorgestellt, der zweiten der beiden weltweit führenden Konferenzen der theoretischen Informatik. Zusammen zeigen diese Arbeiten, dass die TU Bergakademie Freiberg in mathematisch geprägter theoretischer Informatik international sichtbar ist.
wissenschaftliche Ansprechpartner:
Prof. Dr. Johannes Carmesin
Professur für Diskrete Strukturen
Originalpublikation:
Graph Minors Approach to Temporal Sequences, https://doi.org/10.48550/arXiv.2504.00704
