Master Thesis MSTR-2020-35

BibliographyHermann, Matthias: Graph sparsification techniques for triangle counting.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Master Thesis No. 35 (2020).
77 pages, english.
Abstract

The triangle count of a graph is a key metric in graph analysis. Especially for social networks, the triangle count is important to assess connectedness of vertices in the graph. However, these social networks in particular can produce large graphs with trillions of edges. In fact, the size of graphs appears to grow faster than the computational resources to analyze and process these graphs. Confronted with similar problems in the past, the solutions for developers of algorithms were oftentimes approximating algorithms. Research in approximate triangle counting algorithms has led to a multitude of various approximating algorithms. Comparing and understanding the differences in the mechanisms they use to provide faster and more accurate results has therefore become complicated. This work presents an analysis on existing triangle counting algorithms to improve understanding of which mechanisms work best for fast triangle count approximations. In order to further this understanding even more, an analysis on graph structures and their influence on triangle counts is presented, as well. Results of this analysis include a method for decentralized coordination and reducing communication in distributed computations as well as a method for estimating a triangle count of a graph by using a small sample of vertices and their degree values.

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 dateDecember 17, 2020
   Publ. Computer Science