Social network analysis is a hot spot in data mining and it also has a very close contact with us in social life. The structure of the maximum clique, a typical social network substructure analysis method, is the most compact cohesive subgroup, so research on the maximum clique problem (MCP) has great significance in social network analysis. Aiming at the defects of the genetic algorithm (GA) for the MCP, such as longrunning, poor generality and low precision in some benchmark graphs, we propose a new genetic algorithm based on mixed repair, called MGA. A new mixed method based on degree and random chromosome repair, combing with the elitist selection based on randomly paire, uniform block crossover and inversion mutation operator, is adopted in the MGA, which can accelerate search speed, increase population diversity, and effectively prevent the algorithm from trapping into local optimum. We test the proposed algorithm on DIMACS benchmark graphs and typical social network instances. Experimental results show that the MGA has better performance and high generality, can more effectively resolve the MCP in social network analysis.

 

social network analysis, the maximum clique, genetic algorithm, mixed repair strategy, elitist selection, uniform block crossover, inversion mutation

 ,