Verteiltes Subgraph-Counting mit Colorcoding

Abstract

Für das Subgraph-Counting-Problem und das Subgraph-Enumeration-Problem sind die Anzahlen und Häufigkeiten der Isomorphismen für bestimmte Subgraphen in größeren Graphen von Interesse. Zur Lösung dieser Probleme gibt es verschiedene Ansätze. Einer dieser Ansätze basiert auf dem Colorcoding [AYZ95] Verfahren von Alon et al. Die beiden Algorithmen PARSE [ZKKM10] und CC [BCK+17] [BCK+18] versuchen diese Probleme mit diesem Ansatz zu lösen. Dabei hat PARSE eine verteilte Version, wohingegen CC lediglich auf einer einzigen Maschine ausführbar ist. Zusätzlich zu diesen beiden Algorithmen wird in dieser Arbeit DistCC, eine verteilte Version CC’s, vorgestellt. DistCC orientiert sich bei der Art und Weise seiner Verteilung am Beispiel von PARSE. Dank der Verteilung sind die Laufzeiten DistCC’s teilweise deutlich kürzer, als die Laufzeiten CC’s. Außerdem wurden neben der natürlichen Sortierung der Graphen auch zwei neue Sortierungen eingeführt, die die Laufzeiten CC’s und somit auch DistCC’s teilweise verbessern.