Detailansicht
Algorithm engeneering for fully dynamic subgraph counting
Leonhard Paul Sidl
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Physik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Computational Science
Betreuer*in
Monika Henzinger
DOI
10.25365/thesis.72471
URN
urn:nbn:at:at-ubw:1-10909.13372.922241-0
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
In dieser Arbeit vergleichen wir mehrere Methoden, um die Anzahl an Subgraphen in einem dynamischen Graphen im Laufe der Zeit zu zählen. Die verwendeten Algorithmen starten mit einem leeren Graphen und verändern die Zähler der einzelnen Subgraphen, sobald eine Kante eingefügt oder gelöscht wird. Dabei wird jeder Zähler immer um die Anzahl an Subgraphen verändert, die die betreffende Kante enthalten. Wir beschäftigen uns mit zwei Algorithmen, deren theoretischer Hintergrund bereits erforscht wurde und die das oben erwähnte Prinzip anwenden. Wir implementieren diese Algorithmen in C++ und vergleichen deren praktische Laufzeiten mit den theoretischen Werten. Der erste Algorithmus von Hanauer et al. hat eine Laufzeit von O(m^(2/3)), wenn die Strukturen paw, four-cycle und diamond gezählt werden. Im Vergleich dazu benötigt der zweite Algorithmus von Eppstein et al. ein Laufzeit von O(h^2). Einen Unterschied zwischen den Algorithmen gibt es auch bei den Strukturen three-path und triangle, die Laufzeiten betragen O(m^(1/2)) beziehungsweise O(h). Um die praktischen Ergebnisse gegenüberstellen zu können, vergleichen wir die dynamischen Algorithmen mit einem statischen von Ortmann und Brandes. Die verwendeten Graphen kommen aus verschiedensten Anwendungsbereichen wie Molekularbiologie, Informatik oder Linguistik. Wir zeigen mit diesen Experimenten, dass beide dynamischen Algorithmen dem statischen bezüglich der Laufzeit überlegen sind, wenn die Subgraphen in regelmäßigen Abständen gezählt werden. Der größte Nachteil der dynamischen Algorithmen in dieser Situation ist, dass ihre Laufzeit sehr stark von der momentanen Veränderung im Graphen abhängt. Wir konnten zeigen, dass der Algorithmus von Hanauer et al. sowohl vielfacher einsetzbar, als auch leichter zu beschreiben ist. Allerdings hat der Algorithmus von Eppstein et al. in der Praxis eine kürzere Laufzeit. Zusätzlich stellen wir Strategien vor, um die praktische Laufzeit des Algorithmus von Hanauer et al. noch zu verbessern.
Abstract
(Englisch)
In this thesis, we explore means to maintain the number of size four subgraphs in a dynamic graph over time. To achieve this, we start with an empty graph and change the subgraph counts whenever we insert or delete an edge. The number by which we update the count is the number of subgraphs that contain that edge. This principle is used by two algorithms for which the theoretical foundations have already been laid by Hanauer et al. and Eppstein et al. We implement and test both those algorithms using C++ and contrast the results with the theoretical values. The algorithm by Hanauer et al. has a run time of O(m^(2/3)) for paws, four-cycles and diamonds compared to O(h^2) for the algorithm by Eppstein et al. The run times also differ for threepaths and triangels, with O(m^(1/2) and O(h) respectively. To provide a reference, we compare both algorithms to a static algorithm by Ortmann and Brandes, using a diverse set of real-word graphs that include hyperlink networks of Wikipedia sites and protein-protein interactions in yeast. With this analysis, we show that both dynamic algorithms outperform the static algorithm in settings where the subgraph counts need to be computed regularly over the lifetime of the dynamic graph. The main disadvantage of the dynamic algorithms lies in the irregularity of their run time, with subsequent changes in the graph requiring vastly different computation times. We determined, that the algorithm by Hanauer et al. is more versatile and compact than the algorithm by Eppstein et al., but has a slightly worse practical run time. We also discuss changes to the algorithm by Hanauer et al. that make it possible to improve the run time even further.
Schlagwörter
Schlagwörter
(Deutsch)
Algorithm Engeneering Dynamic Graphs Runtime Analysis
Schlagwörter
(Englisch)
Algorithm Engeneering Dynamische Graphen Laufzeitanalyse
Autor*innen
Leonhard Paul Sidl
Haupttitel (Englisch)
Algorithm engeneering for fully dynamic subgraph counting
Paralleltitel (Deutsch)
Erforschung von Algorithmen zum Zählen von Subgraphen im dynamischen Kontext
Publikationsjahr
2022
Umfangsangabe
37 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*in
Monika Henzinger
AC Nummer
AC16661039
Utheses ID
63862
Studienkennzahl
UA | 066 | 910 | |