ALZI: An Improved Parallel Algorithm for Finding Connected Components in Large Graphs

Finding connected components is a fundamental problem in graph and network analysis. It also serves as a subroutine in other graph problems. There are efficient sequential algorithms for finding connected components in a graph. However, a sequential algorithm can take a long time for a large graph. Parallel algorithms can significantly speed up computation using multiple processors. This paper presents a fast shared-memory parallel algorithm named ALZI (Afforest with LinkJump and Zero Implant) to find connected components in a graph. ALZI is an improvement of a recent state-of-the-art parallel algorithm called Afforest. We propose a few non-trivial optimizations that result in better performance in terms of runtime and scalability. We performed rigorous experimentation using a wide variety of real-world and artificial graphs to evaluate the performance of ALZI. The experimental results show that ALZI is 1.4–2.3 times faster than Afforest on these graphs and provides better scalability than Afforest. ALZI has the ability to work with very large graphs. On a Kronecker graph with 4.2 billion edges, ALZI can find the connected components in just 1.02 s using 128 processors.