Application Of Decompostion Based Multi-objective Evolutionary Algorithmin Dynamic Overlapping Community Detection

Community detection is an important issue of complex network research, and its main purpose is to find a collection of modules that are composed of closely linked nodes in the network. Community detection has been widely applied in the fields of recommendation system, risk warning, analysis of public opinion and so on. There exist numerous researches on traditional community detection based on static network,and it has been accumulated a lot of excellent ideas and parameters.However, with the rapid development of complex networks, the new complex network usually has many characteristics, such as the large number of users, the complex structure of the group, the wide range of users and the rapid development of user community. Traditional static network community detection research has been difficult to satisfy the requirement of community detection. The research of dynamic overlapping community detection can further explore the complexity and dynamics of community in complex network, which is one of the most important research directions of community detection.In this paper, a decomposition-based multi-objective evolutionary algorithm (MOEA/D) is used to solve the problem of dynamic overlapping community detection. This algorithm based on the dynamic community detection algorithm(MOEAD-DCD)of MOEA/D and optimizes both snapshot score(SC) and the temporal cost (TC).SC uses the classic measure of indicators in community detection research to ensure the accuracy of the community detection result at every moment.TC computes the similarity of community detection results between neighboring times to ensure the stability of dynamic network community detection. For the overlapping community detection problems of complex network, traditional community detection algorithms often have high algorithm complexity. A large number of classical strategies are proposed to improve the efficiency of MOEAD-DCD. MOEAD-DCD uses a roulette mode for the initialization operator and mutation operator of MOEA/D. And MOEAD-DCD uses the results of the previous community detection to initialize the individuals of the next time.MOEAD-DCD uses an improved coding method based on locus-based adjacency representation, so that a node in a network can belong to several different community structures at the same time. MOEAD-DCD ensured the diversity of community discoveries by preserving multiple non-dominated solutions, and avoids the problem of weight selection by human.Based on a large number of literatures, this paper firstly applies MOEA/D to solve the problem of dynamic overlapping community detection problems. MOEA/D has low computational complexity and can guarantee the diversity of the final non-dominated solutions. Compared with the traditional community discovery algorithm, MOEAD-DCD can guarantee the stability of dynamic community while guaranteeing the accuracy. Subsequent experimental comparisons also demonstrated the effectiveness of MOEAD-DCD.