Research On Overlapping Community Detection Algorithms In Complex Networks

With the continuous development of complex system science, and by the promotion of mobile communication networks and social networks, the research on complex networks has become more in-depth. Since many complex systems can be described as complex networks very well, we hope that, through the analysis and research on complex networks, its statistical characteristics, function features and evolution laws can be revealed. Thus we can understand the complex systems more deeply, and solve the problems in practice. Many researches have shown that complex networks are of obvious community structures, and a large number of scientists have spent huge effort on community detection in the past decade, which made community detection a popular topic 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 which can be parallelized to resolve the problem that currently most algorithms can not process large networks due to their efficiency.Firstly, by referring to the thought that clique can be treated as the initial community core, this thesis proposes a new idea which uses cliques as label owners in label propagation. And based on this idea this thesis proposes a new overlapping community detection algorithm. The experimental results on both synthetic networks and real networks show that the proposed algorithm is effective, and on many networks it can give better results than other algorithms. Also its time efficiency is good.In addition, this thesis proposes a new idea that combines MapReduce with overlapping community detection. The proposed algorithm can be parallelized, and with the help of MapReduce programming model, it is possible for us to detect overlapping communities in existing huge real-world networks, and that is very significant in practice.