How to Fit the SCC Algorithm Efficiently into Distributed Graph Iterative Computation

This paper reviews the sequential, parallel and distributed implementations of strongly connected component algorithms, and analyzes the challenges of each implementation in the graph iteration paradigm of distributed processing. We also review the graph data layout and communication mode of each distributed graph processing system, and analyze the defect of high memory usage in the implementation of the strongly connected component algorithm of the existing distributed graph processing system. Therefore, we propose a strongly connected component algorithm that performs pull mode communication on CSR instead of traversing the transposed graph. Experiments show that the memory consumption of our method is greatly reduced, and the running time of the algorithm is much lower than that of the most advanced implementation. On four publicly accessible data sets, our approach reduces computation time and storage space by an average of 26% and 39%, respectively. In addition, we optimize the general pull communication mode, resulting in 15.2°/0 computation time reduction on the four publicly available data sets.