Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees

Graphs in real life applications are often huge, such as the Web graph and various social networks. These massive graphs are often stored and processed in distributed sites. In this paper, we study graph algorithms that adopt Google’s Pregel, an iterative vertex-centric framework for graph processing in the Cloud. We first iden-tify a set of desirable properties of an efficient Pregel algorithm, such as linear space, communication and computation cost per it-eration, and logarithmic number of iterations. We define such an algorithm as a practical Pregel algorithm (PPA). We then propose PPAs for computing connected components (CCs), biconnected com-ponents (BCCs) and strongly connected components (SCCs). The PPAs for computing BCCs and SCCs use the PPAs of many funda-mental graph problems as building blocks, which are of interest by themselves. Extensive experiments over large real graphs verified the efficiency of our algorithms. 1