A Two-Stage Graph Computation Model with Communication Equilibrium

Distributed graph computing aims at performing in-depth analysis on large networks in a parallel manner. Iterative communication computation is an important model to perform graph analysis. Moreover, high-efficiency iterative communication computation is necessary for assuring the quality of graph partitioning. Many strategies to improve graph computing are usually based on the hypothesis of single communication iteration which focuses on the optimization of load balance in a single graph partitioning and the improvement of parallel granularity or communication manners. However, a graph in the real-world usually requires complex communication iterations to achieve good analysis results, which often have the problems of data and communication tilting and low analysis efficiency. In this paper, we propose a two-stage graph computing model with communication equilibrium (TSMCE). The model employs a communication-equilibrated graph partitioning strategy (CEGP) for load balancing and a two-stage graph computing mode (TS) to reduce the crossing-partition communication. With the change of graph density, various factors such as load balancing, communication balancing, cross-partition transmission traffic, communication delay, and convergence speed can always maintain an efficient balance. The experiments conducted on the real-world datasets show that the communication-equilibrated graph partitioning strategy can divide a graph with high quality compared with Hash and Metis. Besides, the overall performance of our two-stage graph computing model with communication equilibrium is higher than that of the BSP model.