A two stage converging genetic algorithm for graph clustering

A two stage converging genetic algorithm for graph clustering

Graph clustering is a classical problem, and is proven to be NP-complete. It is at the core of many useful algorithms, like Network and VLSI design, computer graphics, data mining etc. In recent years, with exponential increase in the use of social network and strong incentive for creating applications exploiting the information hidden in these networks, clustering of large graphs (social networks) has become an important research topic. As the problem is NP-complete, various heuristic algorithms are proposed to find near optimal solutions efficiently. Optimization criteria are defined depending on the applications. Two important criteria for all heuristic algorithms are quality of the result and its stability over different runs on the same problem. In this work, we proposed a two stage genetic algorithm for network clustering. Modularity index for the partitioned graph is the criterion to optimize. By experimenting with several real-life networks, we have shown that our algorithm is stable and delivers a high modularity partitioning compared to other competitive heuristic algorithms. The stability of the algorithm is analyzed through simulations.