idw – Informationsdienst Wissenschaft
Nachrichten, Termine, Experten
Nachrichten, Termine, Experten
Soziale Netzwerke, Verkehrsnetze oder auch Modelle in der Künstlichen Intelligenz lassen sich mathematisch als Graphen beschreiben: Punkte stehen dabei etwa für Personen, Orte oder Recheneinheiten, Linien für ihre Verbindungen. In vielen Anwendungen verändert sich ein solches Netzwerk jedoch mit der Zeit, etwa bei der Verkehrsplanung, bei Social Media oder KI-Modellen. Mathematiker der TU Bergakademie Freiberg haben nun einen neuen Ansatz entwickelt, um diese temporalen Graphen besser zu verstehen. Doktorand Will J. Turner stellt die Arbeit jetzt beim ACM Symposium on Theory of Computing, kurz STOC, vor —eine der beiden weltweit führenden Konferenzen der theoretischen Informatik.
„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.
Prof. Dr. Johannes Carmesin
Professur für Diskrete Strukturen
Johannes.Carmesin@math.tu-freiberg.de
Graph Minors Approach to Temporal Sequences, https://doi.org/10.48550/arXiv.2504.00704
Criteria of this press release:
Journalists
Information technology, Mathematics
transregional, national
Research results
German
You can combine search terms with and, or and/or not, e.g. Philo not logy.
You can use brackets to separate combinations from each other, e.g. (Philo not logy) or (Psycho and logy).
Coherent groups of words will be located as complete phrases if you put them into quotation marks, e.g. “Federal Republic of Germany”.
You can also use the advanced search without entering search terms. It will then follow the criteria you have selected (e.g. country or subject area).
If you have not selected any criteria in a given category, the entire category will be searched (e.g. all subject areas or all countries).
