The Research Of Hierarchical Agglomeration Algorithm And Active Learning Semi Super-Vised Algorithm For Community Detection

In recent years, as emerging research aspect, research of complex networks has become a hot topic in the field of computer sciences, statistical physics, sociology and bioinformatics. Complex networks have certain features such as small-world, scale-free and modularity. Usually, a complex network contains a number of communities. The nodes in the same community are closely connected and nodes in different communities may be loosely connected. One of the vital tasks of understanding and analyzing complex networks is to find community structure of complex networks. Effective community detection methods can clearly identify the community structures and hence reduce the difficulties of studies in complex networks. Finding community structures of complex networks is an important topic in complex networks research and has important application value.In this thesis, we present two new community detection methods. One is CDACSM, another is ASCD. CDACSM is a new hierarchical agglomeration community detection algorithm. It is designed to solve the following two problems existing in hierarchical agglomeration community detection algorithms:1) They may generate single-node communities and large communities2) Once a node is assigned with a wrong community label which can not be changed. CDACSM algorithm which defines the single-node community similarity measure, community similarity measures and merging rules could avoid these two problems to some extent. ASCD is a new active learning semi-supervised community detection algorithm. It is designed to improve the community detection results in the following three situations in which some community detection algorithms have bad community detection results:1) the quality of labeled data is not ideal in semi-supervised algorithms2) the structure of complex networks is more complex and blurred3) the sizes of communities are equivalent in complex networks. ASCD algorithm defines the relevance, the most relevant nodes, cohesion metrics and proposes the labeled data selection method and semi-supervised learning strategy. It improves the community detection results in the aforementioned situations. This thesis tests CDACSM and ASCD on some real complex networks data sets and benchmark graph data sets. We evaluate our CDACSM and ASCD algorithms on modularity, accuracy, and run-time efficiency. Experiments show that CDACSM and ASCD both have a good community detection results and a good operating efficiency.