Thrifty Label Propagation: Fast Connected Components for Skewed-Degree Graphs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Various concurrent algorithms have been proposed in the literature in recent years that mostly focus on the disjoint set approach to the Connected Components (CC) algorithm. However, these CC algorithms do not take the skewed structure of real-world graphs into account and as a result they do not benefit from common features of graph datasets to accelerate processing.

We investigate the implications of the skewed degree distribution of real-world graphs on their connectivity and we use these features to introduce Thrifty Label Propagation as a structure-aware CC algorithm obtained by incorporating 4 fundamental optimization techniques in the Label Propagation CC algorithm.

Our evaluation on 15 real-world graphs and 2 different processor architectures shows that Thrifty accelerates the flow of labels and processes only 1.4% of the edges of the graph.

In this way, Thrifty is up to 16× faster than state-of-the-art CC algorithms such as Afforest, Jayanti-Tarjan, and Breadth-First Search CC. In particular, Thrifty delivers 1.5-19.9× speedup for graph datasets larger than one billion edges.

https://blogs.qub.ac.uk/GraphProcessing/thrifty-label-propagation-fast-connected-components-for-skewed-degree-graphs/
Original languageEnglish
Title of host publication 2021 IEEE International Conference on Cluster Computing (CLUSTER'21)
Publisher IEEE
DOIs
Publication statusPublished - 13 Oct 2021
Event2021 IEEE International Conference on Cluster Computing (CLUSTER'21) -
Duration: 07 Sep 202110 Sep 2021

Publication series

NameThrifty Label Propagation: Fast Connected Components for Skewed-Degree Graphs
PublisherIEEE
ISSN (Print)1552-5244
ISSN (Electronic)2168-9253

Conference

Conference2021 IEEE International Conference on Cluster Computing (CLUSTER'21)
Period07/09/202110/09/2021

Keywords

  • High Performance Computing
  • Connected components
  • Label propagation
  • Graph Processing
  • Graph Connectivity
  • Graph Traversal

Cite this