Bibliography | Schmid, 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 date | April 28, 2022 |
---|