Improving Efficiency of Graph Clustering by Genetic Algorithm Using Multi-Objective Optimization

Information networks, like social networks on the internet, evolve naturally without constraint on degree or connectivity. The distribution of degree of such network is exponential, with a few nodes having a large degree, forming what is called a scale-free network. Scale-free networks form communities, or clusters of nodes. Discovering such clusters is the most important step for analysis of the information network. This is a NP-hard problem. Recently, genetic algorithm based works are reported, where the optimum number of clusters evolve automatically. The optimization criterion, the modularity index, is used as the fitness function of the chromosome. We observed that, if the diameter of the clusters are constrained to a lower value, during evolution of genetic search, a faster convergence is achieved. We used a multi-objective genetic search with two optimization criteria: the modularity index (the higher the better), and the largest diameter (the lower the better) of the communities defined by a chromosome. Simulation results, using network with known communities, show that using this multi-objective GA the result is stable, and achieves better modularity compared to the most often used Louvain algorithm.