Application Of Genetic Algorithm Based On Complex Network Community Detection

In recent years, with the rise of complex network theory and related applied research, people begin to try to apply these new theoretical tools to study a variety of complex systems of real world. Therefore, the community detection of complex networks gradually becomes a hot research. Community is one of the most important social network topology property, which reveals the hidden laws of social networks. Mathematical model of community structure refers to a set of nodes whose internal connection is tight and external connection is sparse. The traditional methods require pre-set weight parameters to control the objectives. But they are not able to automatically identify the number of communities in the optimization, and it processes the problem of “premature” and inefficiency.In this thesis, the fast adaptive genetic algorithm is a evolution of genetic algorithm for detecting community structure in complex networks. First, this algorithm transforms the detecting problem into a multi-objective optimization problem. We build two objective functions, named community fitness and community score. Second, we construct a external elite gene pool for storing solutions which have high fitness value. For those individuals which already exist in external elite gene pool, we needn't to decode and calculate individual fitness value. Meanwhile, we perform adaptive genetic operator, which returns a set of non-dominated solutions of a pair of objective functions. Finally, we select a Pareto optimal solutions of the highest modularity, decodes and generates a set of independent sub-networks. We use NMI and modularity to evaluate performance of the algorithm. Simulation shows this algorithm greatly improves the accuracy of detection of complex networks and it can be better to find a hierarchy of complex networks.