iPartition: a distributed partitioning algorithm for block-centric graph processing systems

Extracting information from growing networks like social networks has a wide domain of applications. Therefore, many large-scale distributed graph processing systems have been developed. Such systems use some kinds of partitioning to distribute a big graph over machines. Minimizing the number of cutting edges and balancing the load are two general factors that most of the partitioning algorithms try to optimize regardless of the properties of the underlying systems. Although these general factors are necessary, we believe that they are not enough for all systems. In this paper, we investigate common features of block-centric graph processing systems and extract some system-specific core factors that influence on the quality of partitions: minimizing the diameter of the integrated-graph, maximizing the size of integrated vertices, and preventing the skew problem in the size of integrated vertices. The proposed partitioning method, tries to optimize system-specific factors as well as general ones. Evaluating iPartition over real-world graphs showed that it can significantly improve the performance of block-centric graph processing systems in terms of network traffic and synchronization barriers. More specifically, the amount of superstep reduction over frequently-used distributed graph partitioning methods varies from 20 to 75%, based on the type of the graph. The reduction in transmitted messages over the network varies from 10 to 80%.