Research On The Community Detection Methods In Complex Networks

Complex systems can always be abstracted as complex networks, and community structure is the most significant structural characteristic of complex networks. Communities in networks are always corresponding to the functional modules, and to some extent, the functional characteristics of networks are determined by the interactions of the communities. Community detection has been used to explore the network properties from the perspective of mesoscale level(community level), rather than from the perspective of microscale level(individual vertex level) or macroscale level(entire network level). Many interesting network features can be captured through detecting community structures from networks. Furthermore, community structure can have a great influence on network dynamics. Therefore, community detection is of great importance not only in theoretical studies, but also in practical applications. In recent years, community detection has attracted significant interests from researchers in many fields, such as computer science, physics, biology, etc. Community detection has been one of the hot spots in the domain of complex network analysis. This dissertation focuses on the problem of community detection, in which 5 community-detection methods are proposed,and these methods can be categorized as two types.The first type is comprised of 3 community-detection methods, namely DBSCD,HBSCD, and ASSCD. All of them focuses on how to extract high-quality community structures from networks accurately.(1) DBSCD. This method utilizes a sparsification algorithm to remove some betweencommunity edges from the network, to make the community boundaries clearer and sharper. Then the sparsified network is divided into two subnetworks according to the signs of the elements of the network transition matrix’ second eigenvector. Next the subnetworks are bisected iteratively using the same spectral method under the constraint of the modularity. In each iteration, one subnetwork is selected and bisected into two subnetworks, and the selected subnetwork is the one whose bisection division can lead to the largest modularity increment. Finally,the community structure is obtained via the iterative spectral bisection divisions.(2) HBSCD. This method also utilizes the network-sparisification algorithm to re-move firstly some edges from the network. Next the network is divided into several indivisible subnetworks iteratively according to the signs of the elements of the network/subnetwork transition matrix’ second eigenvector. Then each of the subnetwork is taken as a community, and the final community structure is acquired by merging some of the initial communities.(3) ASSCD. This method introduces an active learning strategy into the problem of community detection. It extracts community structure from the network by combining the active learning strategy with a semi-supervised community-detection algorithm. The active learning strategy selects some vertices with the maximum utilities to the semi-supervised community-detection algorithm actively to generate the high-quality must-link and cannot-link pair-wise constraints. The semisupervised community-detection algorithm makes full utilization of those semisupervised components to construct the initial community structure framework,and then to expand the communities by attracting some vertices to join them greedily to get the final community structure.To testify and evaluate these community-detection methods, we conduct expements on some real-world networks, and the experimental results show that the qualiof the community structures extracted by them are better than the counterparts of tcomparison algorithms.The second type contains two community-detection methods, i.e., VSAHCD and LPAd. Both of them aim at discovering the effective and deterministic community structures from networks quickly.(1) VSAHCD. Inspired by the voting behavior in social systems, this method obtains a series of small vertex groups by simulating the voting procedure. Each of the vertex groups is taken as an initial community, and then some of them are merged to form larger communities. We consider two kinds of merging strategies, both of them merge communities iteratively according to the combination of modularity and similarity. One strategy merges the two communities which can lead to the largest modularity increment, but ensuring the similarity between the two communities are larger than 0; the other one merges the two communities with the largest similarity, but ensuring the modularity gain of this merging is positive.The final community structure is acquired by these iterations.(2) LPAd. This is an improvement and enhancement of LPA. It calculates a better vertex sequence, then this algorithm iteratively updates the labels of vertices by theorder of that sequence constantly. In each iteration, every vertex updates its label to the one which occurs most frequently in the neighbors of that vertex. At the same time, we also propose a strategy to solve the problem of ties, which means that more than one label occurs equally and most frequently among the neighbors of that vertex. Owing to these improvements, this algorithm can extract deterministic result from the network. However, in same cases, some vertex groups in that result are too small to be taken as communities, therefore we merge such vertex groups to obtain the final community structure then.According to the theoretical analyses, both of them are high-efficient communitydetection methods. In addition, we also carry out experiments on five real-world networks and two LFR synthesized benchmark networks to evaluate the performance of these two methods. Experimental results show that both of them can effectively extract more reasonable and deterministic community structures from networks.