Novel multilevel particle swarm optimization algorithm for graph partitioning

Abstract

Graph partitioning is crucial step in resolving real time applications in the field of image analysis, smart city designing, wireless communications, data analysis etc. Though considerable research has been done for getting an optimal partitioning of graphs still it demands enhancement for diverse application problems. Hybrid graph partitioning approaches are promising and possess ability to partition graphs with large number of vertices. In our research we have developed multilevel particle swarm optimization algorithm for graph partitioning. Size of the graph is reduced by heavy edge matching algorithm and then greedy graph growing partitioning is used to divide the graph. Discrete particle swarm optimization used at the most important stage of refinement. Performance is evaluated by using Walshaw’s Benchmark graphs and from analysis it has been observed that proposed algorithm generates optimal partitioning with reduced cut values and computational cost.