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
Merkmale dieser Pressemitteilung:
Journalisten
Informationstechnik, Mathematik
überregional
Forschungsergebnisse
Deutsch
Sie können Suchbegriffe mit und, oder und / oder nicht verknüpfen, z. B. Philo nicht logie.
Verknüpfungen können Sie mit Klammern voneinander trennen, z. B. (Philo nicht logie) oder (Psycho und logie).
Zusammenhängende Worte werden als Wortgruppe gesucht, wenn Sie sie in Anführungsstriche setzen, z. B. „Bundesrepublik Deutschland“.
Die Erweiterte Suche können Sie auch nutzen, ohne Suchbegriffe einzugeben. Sie orientiert sich dann an den Kriterien, die Sie ausgewählt haben (z. B. nach dem Land oder dem Sachgebiet).
Haben Sie in einer Kategorie kein Kriterium ausgewählt, wird die gesamte Kategorie durchsucht (z.B. alle Sachgebiete oder alle Länder).
