Detailansicht
Color update propagation
dynamic color refinement in evolving graphs
Julia Korol
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Mathematik
Betreuer*in
Nils Morten Kriege
DOI
10.25365/thesis.81862
URN
urn:nbn:at:at-ubw:1-16257.11877.542027-3
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Color Refinement ist ein klassischer Algorithmus auf Graphen, auch bekannt als naive Vertexklassifikation oder, formaler, als der eindimensionale Weisfeiler-Leman-Algorithmus. Er verbindet Konzepte aus der Graphentheorie und Gruppentheorie, indem er die Knoten eines Graphen in Farbklassen partitioniert. Bereits kleine strukturelle Änderungen, wie das Hinzufügen oder Entfernen einer Kante oder eines Knotens, können zu einer deutlich anderen Verfeinerung führen. In der Praxis betreffen solche Änderungen jedoch häufig nur einen begrenzten Teil der Knoten, während die globale Partition weitgehend erhalten bleibt. Dies führt zu der Frage, ob sich die ursprüngliche Färbung nutzen lässt, um die aktualisierte Partition nach einer Änderung effizient zu bestimmen. In dieser Arbeit wird eine dynamische Variante von Color Refinement vorgestellt, die als Color Update Propagation bezeichnet wird. Anstatt den Verfeinerungsprozess nach jeder Änderung vollständig neu zu starten, nutzt dieser Ansatz die Informationen aus dem ursprünglichen Verlauf und aktualisiert nur diejenigen Teile des Graphen, die tatsächlich von der Änderung betroffen sind. Es werden drei Strategien zur Bestimmung des betroffenen Bereichs untersucht. Die einfachste Methode aktualisiert die gesamte Nachbarschaft der Änderung, während weiterentwickelte Ansätze erhaltene Symmetrien ausnutzen, um unveränderte Knoten auszuschließen und so den Rechenaufwand zu reduzieren. Experimentelle Ergebnisse zeigen, dass dieser Ansatz für verschiedene Graphklassen und unterschiedliche Arten von Änderungen gute Leistungen erzielt. Im Rahmen der Arbeit wird zudem eine Implementierung des vorgeschlagenen Algorithmus bereitgestellt, die auf einer Variante von Color Refinement basiert, dem sogenannten Power Iterated Color Refinement.
Abstract
(Englisch)
Color refinement is a classical graph algorithm, also known as naive vertex classification or, more formally, the 1-dimensional Weisfeiler–Leman algorithm. It connects graph theory with group theory by partitioning a graph’s vertices into color classes. Even a small structural modification, such as the addition or removal of a vertex or edge, can produce a very different refinement. In practice, however, such changes often influence only a limited subset of vertices, while the global partition is largely preserved. This raises the question: can the original vertex colors be used to efficiently obtain the updated partition after a graph modification? In this thesis, I propose a dynamic variant of color refinement, called Color Update Propagation. Instead of restarting the refinement from scratch after each modification, this approach exploits the history of the original process and updates only those parts of the graph actually affected by the change. I introduce three strategies for identifying the affected region. The most naive method updates the entire neighborhood of the modification, while more refined approaches exploit preserved symmetries to exclude unaffected vertices, thereby reducing computational effort. Experimental results show that this approach performs well across a variety of graphs and their changes. As part of the thesis, I provide an implementation of the proposed algorithm, based on a variant of color refinement known as Power Iterated Color Refinement.
Schlagwörter
Schlagwörter
(Deutsch)
Color Refinement Weisfeiler-Leman-Algorithmus Dynamische Graphalgorithmen Graphentheorie
Schlagwörter
(Englisch)
Color Refinement Weisfeiler-Leman Algorithm Dynamic Graph Algorithms Graph Theory
Autor*innen
Julia Korol 
Haupttitel (Englisch)
Color update propagation
Hauptuntertitel (Englisch)
dynamic color refinement in evolving graphs
Publikationsjahr
2026
Umfangsangabe
53 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*in
Nils Morten Kriege
Klassifikationen
31 Mathematik > 31.12 Kombinatorik. Graphentheorie ,
54 Informatik > 54.00 Informatik. Allgemeines
AC Nummer
AC18015231
Utheses ID
80384
Studienkennzahl
UA | 066 | 821 | |