Graph partitioning algorithms for minimizing inter-node communication on a distributed system

Processing large graph datasets represents an increasingly important area in computing research and applications. The size of many graph datasets has increased well beyond the processing capacity of a single computing node, thereby necessitating distributed approaches. As these datasets are processed over a distributed system of nodes, this leads to an inter-node communication cost problem (also known as inter-partition communication), negatively affecting the system performance. This research proposes new graph partitioning algorithms to minimize the inter-node communication by achieving a sufficiently balanced partition. Initially, an intuitive graph partitioning algorithm using Random Selection method coupled with Breadth First Search is developed for reducing inter-node communication by achieving a sufficiently balanced partition. Second, another graph partitioning algorithm is developed using Particle Swarm Optimization with Breadth First Search to reduce inter-node communication further. Simulation results demonstrate that the inter-node communication using PSO with BFS gives better results (reduction of approximately 6% to 10% more) compared to the RS method with BFS. However, both the algorithms minimize the inter-node communication efficiently in order to improve the performance of a distributed system.