Research And Implementation Of Overlapping Community Detection Based On Maximal Cliques

With the continuous development of complex system science, and by the promotion of social networks and mobile communication networks, the research on complex networks has become more concern. Many researches have shown that complex network are of obvious community structures, community structure is a crucial role for understanding the structure and function of complex networks, and a large number of scientists have spent huge effort on community detection in the past decade. At the same time, overlapping community detection has become one of the popular topics in complex networks. But the problem is still not satisfactorily solved.By studying the representative papers in this area appeared in recent years, this thesis summarizes some representative community detection algorithms and analyzes their advantages and weaknesses, and finally proposes an overlapping community detection algorithm based on maximal cliques, and implement it in parallel environment.Firstly, maximal clique is the basis of the overlapping community in this thesis. Combined with the characteristics of maximal clique, we propose four pruning tactics in search process of maximal cliques. Filter out some unnecessary search and improve the efficiency.Secondly, for the three steps of overlapping community detection, we propose the methods of selection seed based on overlapping maximal cliques, expansion communities based on mutant sequence, and inspection communities based on topology structure. These methods improve the accuracy and efficiency of the overlapping community detection.Finally, we analysis the feasibility of the parallelization of our algorithms, and implement them in parallel environmentIn conclusion, this thesis studies the problem of overlapping community detection based on maximal cliques, and then proposes efficient solutions to the weaknesses of recent algorithms. Extensive experiments validate the efficiency and accuracy of our methods.