The Genetic Algorithm For Solving The Maximum Clique Problem And Applying On The Social Network

Maximum clique problem in graph theory is a typical combination optimal problem w hich has been proven to be NP-complete. This problem is widely used in many fields, such as artificial intelligence, cluster analysis, signal transmission, subgraph isomorphism problem, vertex cover problem, etc. The study of MPC has important significance for both in theory and real life. But with the increasing size of the problem, it increased exponentially about the solution time and complexity, the certainty method for finding of the past is no longer applicable. So people began to shift attention to the use of heuristic algorithms for solving the MPC, which has made some research results.As a commonly used heuristic algorithm to solve the combination optimization problems, genetic algorithms has made some achievements on solving the MPC.But there still have some problems about the poor general and time-consuming. The purpose of this paper is to solve this problem. At the same time the research results will be applied to the social network problems. In this respect, proposed this text about how to solve the MPC by the genetic algorithms and its application in social networks.Firstly made a brief introduction about the significance of the MPC, Genetic Algorithms and Social Network. Secondly, presented a detailed description of the research status of the MPC and Genetic Algorithms, aiming at the defects of Genetic Algorithm(GA) for solving the Maximum Clique Problem(MCP) in more complicated, long-running and poor generality, three genetic algorithms is proposed in this paper. In order to short the time running, a new chromosome repair method on the degree are adopted in the new algorithm. A fast genetic algorithm(FGA) is proposed in this paper. In order to improve the efficiency of the algorithm and the versatility of the algorithm, a hybrid chromosome repair method is introduced in this paper, and through a lot of experiments to determine reasonable configuration of genetic operators and parameter.Proposed the use of hybrid repair genetic algorithms to solve the MPC(MGA). Finally, in order to further improve the solution accuracy of the algorithm,through analyzing the characteristics of different types legend in the DIMACS, it proposes a probabilistic Hybrid repair method and diversification method to increase the diversity of the population during the genetic process.And presents a diverse genetic algorithm(MDGA)which based on Hybrid repair to solve the MPC.With the rapidly development of network and information technology, the community detection of the social network has an important research significance. The Maximum Clique Problem(MCP) is one of the significant method to analyze the struc ture of network. Therefore, the research of MCP has practical value and broad application prospects.The improve genetic algorithms was tested on DIMACS benchmark graphs. Experimental results show that algorithms have better performance and high generality than the others which has been improved. At the same time, the algorithms is applied to the typical examples of social network and compared with the existing algorithms which solving social networks better. Experimental results show that the algorithms proposed in this paper have higher accuracy.