| This paper based on the evolutionary algor ithm has studied the problem of blockmodel based on graph partitioning and problem of multi-objective evolutionary with decomposition applied to community detection. This paper mainly studies the following three works:1. Apply evolutionary algorithm to b lockmodel problem.The process of this algorithm includes the use of extracting complete subgraph to initialize population,conflict partition crossover(CPX)to produce offspring and repair operation to optimize child. At last, algorithm convergences gradually and the value of objective function reaches the maximum after repeated iteration. Through making blockmodel partition experiments on the four groups of network from different origins by using evolutionary algorithm(EA) and grouping genetic algorithm(GGA) respectively, it shows that the blockmodel method based on EA proposed in this chapter is very efficient and more superior in solving large-scale networks especially the network with more nodes or higher edge density.2. Multi-objective evolution algorithm based on modularity applied to signed network. According to the characteristics of signed network, this paper defines two objective functions and uses decomposition method to evolve the population. The process of genetic includes the use of extraction subgraph to initialize population, single crossover operator to produce offspring and mutation operator based on positive neighbor to make individual convergence gradually. Analysis of the Pareto Front presented by signed network proves the feasible of the two objective functions in detecting signed network. Through comparing with other algorithms and analysis of results, it shows that MOEA/D algorithm based on modularity is more superior at revealing different level of community structure and extracting small communities.3. Multi-objective community detection algorithm based on density is proposed. This algorithm based on the second work redefines the two objective functions, which make it can not only detect the community structure of the singed network b ut also detect unsigned network. This paper describes specific objective function definition and its source of motivation in detail. Genetic operation also includes the method of extracting subgraph, single crossover operator and the mutation based on neighbor. Through detecting the signed and unsigned network, it proves that the two objective functions are feasible at detecting community structure. Through comparing with the MOEA/D based on modularity and other algorithm, it shows that MOEA/D based on dens ity proposed in this chapter is a more comprehensive and more efficient method at presenting community structure. |
