Community Detection In Complex Networks Based On Evolutionary Computation

Many real-world complex systems can be represented as networks. Collaboration networks, the World-Wide-Web, power grids, biological networks, and social networks are some examples. Networks could be modeled as graphs, where nodes (or vertices) represent the objects and edges represent the interactions among these objects. The area of complex networks has atrracted many researchers from different fields such as physics, mathematics, biology, and sociology. Besides the properties such as small world effect and the right-skewed dgree distributions, community structure is another important property in a complex network. Qualitatively, a community is defined as a subset of the graph nodes which have a pattern of interconnections which is denser than that observed with the rest of the network nodes not in that community. Community detection in complex networks is potentially very useful. Nodes belonging to the same community are more likely to have properties in common. In recent years, many algorithms have been developed to solve this problem. These algorithms can be divided into three major categories:graph partitioning, hierarchical clustering, and modularity-based optimization method, which is by far the most popular class of methods to detect communities in graphs. Modularity, originally introduced to define a stopping criterion for the algorithm of Girvan and Newman, has rapidly become an essential element of many community detection methods and by far the best known quality function. By assumption, high values of modularity indicate good partitions. So, the partition corresponding to its maximum value on a given graph should be the best, or at least a very good one.In artificial intelligence, evolutionary algorithms is population-based metaheuristic optimization algorithms inspired by biological evolution. The use of a population of solutions helps the evolutionary algorithms avoid becoming trapped at a local optimum, which is a prominent advantage compared with other optimization methods. Evolutionary algorithms that interspersed the recombination of high quality solutions with periods of intensive individual optimization were named memetic algorithms. From an optimization point of view, memetic algorithms have been shown to be more efficient and more effective than traditional genetic algorithms for some problem domains. This paper is mainly about the application of evolutionary algorithms to community detection. The main works are as follows: (1) A community detection method by using multi-objective evolutionary algorithm based on decomposition is proposed. In this proposed method, community detection is considered as a multi-objective optimization problem and is formulated with two different objectives. Multi-objective evolutionary algorithm based on decomposition (MOEA/D) is employed to optimize the two objectives.(2) The resolution limit of modularity optimization is studied. In order to avoid resolution limit problem, we tested another quality function:the general modularity density, which is a combination of the ratio association and the ratio cut. By tuning the parameter, we can use this general function to analyze the topological structure and uncover more detailed and hierarchical organization of a complex network. A memetic algorithm for community detection in networks is proposed. The proposed algorithm combines genetic algorithm and a hill-climbing strategy as the local search procedure so that it is more efficient than traditional genetic algorithms. Meanwhile, we choose the general modularity density as the objective function, which allows the proposed memetic algorithm to discover the community structure in networks at different resolutions.This work was supported by the National High Technology Research and Development Program (863Program) of China (Grant No.2009AA12Z210), the Program for New Century Excellent Talents in University (Grant No. NCET-08-0811), the Program for New Scientific and Technological Star of Shaanxi Province (Grant No.2010KJXX-03), and the Fundamental Research Funds for the Central Universities (Grant No. K50510020001).