Graph sparsification techniques for triangle counting

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.

Der Triangle-Count eines Graphen ist eine wichtige Metrik für Graphanalysen. Besonders für soziale Netzwerke ist der Triangle-Count wichtig, um die Verbundenheit der Knoten im Graphen beurteilen zu können. Gerade diese sozialen Netzwerke können jedoch große Graphen mit Billionen von Kanten darstellen. Die Größe von Graphen scheint auch schneller anzuwachsen als die zur Verfügung stehenden Ressourcen zur Analyse und Verarbeitung dieser Graphen. In der Vergangenheit wurden derartige Probleme bereits öfters mithilfe von approximativen Algorithmen gelöst. Die Forschung im Bereich von approximativen Triangle-Counting-Algorithmen hat bereits eine Vielzahl von approximativen Algorithmen hervorgebracht. Daher wurde das Vergleichen und Verstehen der jeweiligen Mechanismen, durch welche schnelle und genaue Ergebnisse ermöglicht werden, zunehmend kompliziert. In dieser Arbeit wird eine Analyse von existierenden Triangle-Counting-Algorithmen vorgestellt, durch die ein besseres Verständnis dafür geschaffen werden soll, welche Mechanismen am besten geeignet sind schnelle Approximationen des Triangle-Count zu ermöglichen. Eine Analyse der Strukturen von Graphen und deren Einfluss auf den Triangle-Count ist ebenfalls Teil der Arbeit, um dieses Verständnis zu vertiefen. Die Ergebnisse der Analyse beinhalten eine Methode zur dezentralen Koordination und zur Reduzierung von Kommunikation in verteilten Berechnungen sowie eine Methode zur Abschätzung des Triangle-Count unter Zuhilfenahme einer kleinen Stichprobe von Knoten des Graphen mitsamt ihrer Knotengrade.