Research On Community Detection Algorithms In Complex Networks

With the prevalence of the research in the complex network, more and more researchers study the complex system from the point of the complex network. Many complex systems can be depicted by the complex network in the real world. As one of the most important characteristics in the complex network, the community structure has attracted more and more attention. So detecting the community structure is very important for us to understand the function of the complex network, discover the latent rule of the complex network and forecast the action of the complex network. However, both the increasing expansion of the network scale and the more complex network structure make it more difficult to detect the community structure in the complex network. At present, there are still following problems in the existing community detection algorithms:(1) The current community detection algorithms are difficult to detect the stable overlapping community structure accurately;(2) The community detection algorithms based on the node clustering are difficult to detect the high overlapping community structure;(3) The traditional community detection algorithms only take attention on the modular construction, but do not identify the hierarchy community structure in the future. In order to solve the above problems, this paper launches the research. The main work and research results are as follows:1. An improved Label Propagation Algorithm using non-overlapping maximal cliques(LPAc) is proposed. The proposed algorithm has made the improvement of three aspects on the basis of Label Propagation Algorithm(LPA). The proposed algorithm assigns every non-overlapping maximal clique with a unique label after detecting all the non-overlapping maximal cliques in the label initialization stage; then in the label propagation stage, each node adopts the label which has the maximal label propagation ratio; finally in the community adjusting stage, some highly similar communities are merged to improve the quality of the community detection. Experiments on both artificial networks and real networks show that the proposed algorithm not only enhances the robustness of LPA vastly, but also detects the overlapping community structures accurately in the networks.2. A core link-based overlapping community detection algorithm(CLCD) is proposed. Compared with conventional algorithms based on node clustering, the proposed algorithm starts from the perspective of the link. First, a core link is detected. Then we utilize it to attract links in the outer space to join the community which contains the core link. In the end, we transform link communities to node communities. After adjusting the node communities, we can get the global optimal overlapping community structures. The proposed algorithm is an unsupervised algorithm, without inputting additional parameters. Experiments on both artificial networks and real networks show that the proposed algorithm can achieve better efficiency on detecting high overlapping community structures.3. A hierarchical community detection algorithm based on the node seed set(HSS) is proposed. The proposed algorithm selects the seed node and its nearest neighbor node which is acquired according to the cosine similarity as the seed node set. By starting from the seed node set to detect the hierarchical community structures based on the resolution formula, the degree proportion of the node adds to the community is defined to judge whether the boundary of the hierarchical community structures is arrived. Finally, the proposed algorithm selects new seed node sets out of the detected communities in the network and starts from them until all the hierarchical community structures in the network are detected over. Experiments on both artificial networks and real networks show that the proposed algorithm can detect all the hierarchical community structures in the networks accurately.