Genetic Algorithm with Ensemble Learning for Detecting Community Structure in Complex Networks

Community detection in complex networks is a topic of considerable recent interest within the scientific community. For dealing with the problem that genetic algorithm are hardly applied to community detection, we propose a genetic algorithm with ensemble learning (GAEL) for detecting community structure in complex networks. GAEL replaces its traditional crossover operator with a multi-individual crossover operator based on ensemble learning. Therefore, GAEL can avoid the problems that are brought by traditional crossover operator which is only able to mix string blocks of different individuals, but not able to recombine clustering contexts of different individuals into new better ones. In addition, the local search strategy, which makes mutated node be placed into the community where most of its neighbors are, is used in mutation operator. At last, a Markov random walk based method is used to initialize population in this paper, and it can provide us a population of accurate and diverse clustering solutions. Those diverse and accurate individuals are suitable for ensemble learning based multi-individual crossover operator. The proposed GAEL is tested on both computer-generated and real-world networks, and compared with current representative algorithms for community detection in complex networks. Experimental results demonstrate that GAEL is highly effective at discovering community structure.
6 pages, 2 figures, 1 table 2009 Fourth International Conference on Computer Sciences and Convergence Information Technology(ICCIT '09)