Community Detection In Complex Networks Based On Memetic Algorithm

Many complex systems in the real world can be represented as networks, such as the technology networks, social networks, transportation networks and biological networks. These networks can be modeled as graphs, where nodes represent objects, connection between nodes represent that there is a certain relationship between objects. Community structure is a very important property of complex networks, and it can be defined as a subset of nodes within which connections are dense while between which they are sparser. Detecting the communities of a network could have great significance to analyze the topology of complex networks, understand the function of complex networks and predict the behaviors of complex networks. In recent years, the community detection problem has received the attention of scholars in various fields and many algorithms have also been proposed, such as graph partitioning, hierarchical clustering, spectral clustering, similarity based measures and genetic-based optimization methods.Memetic algorithm is the cross product of computer science and social biology, it is built on the basis of simulating the process of cultural evolution. It is a marriage between a population-based global search and the heuristic local search made by individual. After years’ development, memetic algorithm has been accepted by more and more researchers and widely applied to various fields such as combinatorial optimization, pattern recognition and image processing. This thesis makes a systemic research on the problem of community detection. The main contributions are outlined as follows:1. The basic theory of evolutionary algorithms is studied. Then, the application of memetic algorithm and its improved version on the problem of community detection is investigated. Based on these, a memetic algorithm using local structural information(MA-LSI) is proposed to detect community structure in complex networks. Modularity Q is taken as fitness function and the local search operator is defined by using the function of local community tightness. In addition, vertex moving operator is adopted to improve the partition result. Experiments show its superiority on modularity optimization for community detection problem compared with traditional clustering algorithm and Meme- net.2. The problem of resolution limit of traditional modularity optimization is studied. To overcome the resolution limit, another objective function is adopted: the extended modularity density. This function contains an adjustable parameter and we can analyze the network in different resolution by tuning the parameter. Based on the optimization of the extended modularity density, another memetic algorithm with two different local search operators(MA-SAT) is proposed to detect community structure in complex networks. One local search strategy is simulated annealing(SA), and the other one is Tightness Greedy Optimization(TGO). SA is employed to find individuals with higher modularity density, which helps to enhance the convergence speed of the MA and avoid being trapped into local optimum. TGO adopts the local tightness function which makes full use of local structural information to generate neighbor partition, which increases very little computation cost and benefits for the diversity of the population of MA. Experiment results show that compared with several state-of-the-art methods, our algorithm is very efficient and competitive.This work was supported by the National Natural Science Foundation of China(No. 61003199) and the Fundamental Research Funds for the Central Universities(Nos. JB140216 and K5051202019).