Fast Distributed Memory Parallel Algorithms for Finding Connected Components in Large Graphs

Finding the connected components in a graph is a fundamental problem in graph theory and network science. A connected component in a graph is a maximal set of vertices such that there is a path between any two vertices in the component. In a serial setting, connected components can be efficiently computed by running a breadth-first search (BFS). However, BFS-based algorithms do not lead to good parallelization. At the early stage, parallel algorithms for the connected component problem were developed for the PRAM model and shared-memory systems. With the availability of big data and big graphs and the development of a new area called network science, there is a renewed interest in developing parallel algorithms for this problem. In recent years, a number of distributed-memory parallel algorithms have been developed. These algorithms are based on mainly Shiloach and Vishkin’s PRAM algorithm, called the SV algorithm, or some variants of SV. In this paper, we present a PRAM algorithm, called SELP, which is elegant and significantly simpler than the SV algorithm. Based on SELP, we develop a distributed-memory parallel algorithm, called DSELP. In addition, we incorporate some novel techniques to minimize communications among the processors. Experimental results show that our algorithms outperform the recent state-of-the-art distributed-memory algorithms significantly on a wide variety of graphs, and scale very well to a large number of processors.