GAKH: A new evolutionary algorithm for graph clustering problem

摘要

Graph clustering has wide applications in different areas such as machine learning, bioinformatics, data mining, social networks and understanding a software. Since it is an NP-hard problem, most approaches use the meta-heuristic and search-based evolutionary methods for solving it. Inspired by optimization algorithms like krill herd (KH) and genetic algorithm (GA), this paper proposes a new graph clustering algorithm. KH is an effective algorithm to solve continuous space optimization problems. It imitates individual and group behavior of krills and, normally, it cannot solve discrete space problems. GA is an evolutionary algorithm that uses search techniques to find near-optimal solutions. However, the main disadvantage of the GA is the lack of strong and effective information flow between generations as well as the lack of local search. In the proposed evolutionary algorithm, we have combined strengths of these two algorithms, e.g., adopting the cycle and GA operators, using swarm intelligence, and inspiring the Krill's movements, we got better results for the graph clustering problem. Initial results of the proposed algorithms on a number of software graphs showed that the clustering results obtained from the proposed algorithm are of higher quality compared to other considered algorithms.