Graph sampling for subgraph counting on directed graphs

Abstract

Calculating the count of subgraphs in a given network is a vital graph mining primitive with multidisciplinary applicability. Many analytical methodologies, such as discovering network motifs, rely precisely on the subgraph census problem. Further, an accurate census is often unnecessary togain the required information, and approximating the census can significantly benefit the runtime. Elenberg et al. proposed a method to approximate the census on undirected graphs for 3- and 4-profiles through sub-sampling the edges of the input network. The goal of this thesis is to generalize this method to directed networks with variable subgraph sizes. Thus providing an algorithm that sub-samples the input network, transfers it to an existing census algorithm and estimates the census from the gained result, which is then called SampleCensus. The algorithm is then tested with a set of symbolic networks, comparing the runtime and accuracy with the present algorithms, Rand-FaSE and FaSE. Additionally, we give an implementation using the distributed algorithm MR-GTrie and also analyze further runtime enhancements. With that, we show how this approach can contribute to a more efficient census estimation. Die Anzahl der Teilgraphen in einem größeren Netzwerk zu berechnen ist eine wichtige Aufgabe in der Graphanalyse mit verschiedenen Anwendungsbereichen. Viele analytische Methoden, beispielsweise das Suchen nach Netzwerk Motifs, basieren auf dem Problem des Teilgraphzählens. Eine exakte Zählung ist für solche analytische Methoden oft nicht notwendig und die Anzahl nur zu überschlagen kann die Laufzeit wesentlich verringern. Elenberg et. al. präsentierte eine Methode 3- und 4-Profile zu approximieren, indem die Kanten aus dem Eingangsgraphen nur teilweise abgetastet werden. Das Ziel dieser Bachelorarbeit ist diesen Ansatz auf gerichtete Graphen auszuweiten und für beliebige Teilgraphgrößen zu verallgemeinern. Dafür wird ein Algorithmus namens SampleCensus vorgeschlagen, welcher die Kanten des Eingangsnetzwerks stichprobenartig abtastet, das abgetastete Netzwerk an einen exakten Algorithmus weitergibt und mit Hilfe des erhaltenen Ergebnisses die Anzahl auf dem ursprünglichen Netzwerk schätzt. Dieser Algorithmus wurde auf einer Menge repräsentativer Netzwerke getestet und die Laufzeit und Genauigkeit mit den aktuellen Algorithmen,Rand-FaSE und FaSE, verglichen. Zusätzlich wird eine Implementierung mit einem verteilten Algorithmus, MR-GTries präsentiert und die Laufzeitverbesserungen analysiert. Mit diesem Ansatz zeigen wir wie SampleCensus zu einer effizienteren Schätzung von Teilgraphzählungen beitragen kann.