Complex Network Community Mining Based On Genetic Algorithm

With the rapid development of information technology, human society hasentered the Internet era, from the transport network to power network, from thecitation network to the social network, complex network has been extended to everyaspect of people’s life. So after the arrival of the small world network model and theBA scale-free network model in complex network, complex network has become oneof the research hot spots in various fields. Community structure is one of thesignificant features of complex network, how to mining community efficiently hasbecome the research object for many scholars.A lot of community mining algorithms were put forward in succession, such asthe algorithm FN、GN、SA etc., but they have one kind shortcoming or another, withthe network modularity proposed in2004, complex network community miningproblem becomes an optimization problem, however, this kind optimization is acomplete NP problem, which is hard to resolve. Genetic algorithm (GA), which hasthe property of solving NP problem effectively and does not depend on the specificproblems, has been widely used in various areas. So it is a good method to deal withthis problem. However, the existing complex network community mining algorithmsbased on genetic algorithm exist some drawbacks, for instance, optimization ability isnot strong, slow convergence speed and the amount of calculation. So in this article,we propose a genetic algorithm based on local modularity for community detecting.Afterwards, a genetic algorithm based on clustering for community detecting isproposed, and on this basis, by introducing an idea of dual-population, an improvedgenetic algorithm based on clustering and double-population for community detectingis proposed. The paper’s main researches are as follows:(1) A concept of local modularity is introduced, on the basis, we design a newmore efficient mutation operator based on local modularity and propose a geneticalgorithm based on local modularity mutation to divide the community structure ofcomplex networks (LMCD). The mutation operator selects the neighbor node that canbest embody the definition of weak community structures as mutated result, whichmakes the mutated candidate solution closer to the optimal solution.The rouletteselection is integrated into a uniform crossover operator. Finally we apply thealgorithm to six typical real-world complex networks, and make a comparison with other typical algorithms, and validate the feasibility and effectiveness of thealgorithm.(2) We introduce the idea of clustering so as to solve the problem of prematureconvergence and increase the diversity of population, and put forward an improvedgenetic algorithm for community detecting based on minimum spanning treeclustering (CGACD). The method produces population division through the minimumspanning tree clustering on the population, then chooses the individuals from differentdivisions do genetic operations, which restrains the phenomenon of prematureconvergence. However, the general Euclidean distance or Hamming distance is notsuitable to complex networks, we define a similarity distance based on the normalizedmutual information to measure the distance between individuals in a population. Andthen we test the algorithm on the computer generated complex network and four realcomplex networks, proving and validating the effectiveness of the algorithm CGACD.(3) Based on the clustering genetic algorithm, inspired by the thought ofdual-population, this paper proposes a genetic algorithm based on clustering anddual-population for complex network community mining. The new methoddetermines main class and reserve class for individuals of partitioning of thepopulation, which produced by (2), the main class search optimal solution in thesolution space, at the same time, the individuals in reserve class provide diversity forthe evolution of main class. When the population is caught in local optimum, thealgorithm produces a part of random solutions for injectiing diversity. In order toanalyse the method more clearly, firstly we test the algorithm on the five functionsoptimization benchmark problems, afterwards, the algorithm is applied in two realcomplex networks. Experimental result has shown the algorithm is efficient.