Standard Framework for Comparison of Graph Partitioning Techniques

Graph Partitioning is used to distribute graph partitions across nodes for processing. It is very important in the pre-processing step for distributed graph processing. In Math and Computer Science, many different distributed graph processing solutions use different partitioning approaches. This research deals with the identification of issues associated with the different graph partitioning approaches. This research paper compared the different graph partitioning solution (GraphLab, ParMetis, PT-Scotch) by applying them on different real world datasets and obtained the I/O and partitioning variation between them using different technique. This paper describes the procedure of configuring the GraphLab on Ubuntu OS and applying partitioning and pagerank techniques on it. Pmetis and Kmetis are two graph partitioning algorithms used in ParMetis. These algorithms were on same graph for different numbers of partitions and obtained the I/O and partitioning comparison between Pmetis and Kmetis. Different vertex cut strategies are also discussed in this paper. In this paper, the behavior of PowerGraph and PT-Scotch was explored while working on a very large datasets.