Genetic Algorithm with Local Search for Community Detection in Large-scale Complex Networks
局部搜索与遗传算法结合的大规模复杂网络社区探测

Detecting communities from complex networks by genetic algorithm has triggered a great common interest. For this problem, a genetic algorithm with local search (LGA) which employs network modularity Q as objective function is given in this work. An effective as well as efficient mutation method combined with a local search strategy is proposed based on our profound analysis on local monotonicity of function Q, meanwhile, a label propagation based method is adopted to produce the accurate and diverse initial population, which can further improve the search efficiency of LGA. The proposed LGA has been tested on both benchmark networks and some large-scale complex networks, and compared with some competitive community detection algorithms. Experimental result has shown that LGA is highly effective and efficient for discovering community structure.