Bachelor Thesis BCLR-2021-88

BibliographySchmid, Noah-Yannick: Graph sampling for subgraph counting on directed graphs.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 88 (2021).
51 pages, english.
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.

Full text and
other links
Volltext
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Superviser(s)Rothermel, Prof. Kurt; Schramm, Michael
Entry dateApril 28, 2022
   Publ. Computer Science