Bachelorarbeit BCLR-2021-88

Bibliograph.
Daten
Schmid, Noah-Yannick: Graph sampling for subgraph counting on directed graphs.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Bachelorarbeit Nr. 88 (2021).
51 Seiten, englisch.
Kurzfassung

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.

Volltext und
andere Links
Volltext
Abteilung(en)Universität Stuttgart, Institut für Parallele und Verteilte Systeme, Verteilte Systeme
BetreuerRothermel, Prof. Kurt; Schramm, Michael
Eingabedatum28. April 2022
   Publ. Abteilung   Publ. Institut   Publ. Informatik