Research On Community Detection In Complex Networks

In recent years, along with the high-speed development of information technique, complex network has become a growing research field partly as a result of the increas-ing availability of a huge number of networks in the real world. Besides small world effect found by Watts and Strogatz in 1998 and scale-free effect found by Barabasi and Albert in 1999, community(module) structure has been considered to be one of the most important characteristics in complex networks. Until now, there isn't a pre-cise definition of community. Generally speaking, community refers to such subgraph within which vertex-vertex connections are dense, but outside which connections are relatively sparse. The investigations show that this kind of community structure has close relationship with some functionality such as robustness and fast diffusion, etc. So characterizing and detecting such community structure has very important practical significance and has become a research hot spot.The related problems on community detection in complex networks are studied in this paper, and the main results are as follows:1. A novel community detection algorithm is presented which is called JEOMD. It uses improved modularity density D with penalty term as the objective function and optimizes this objective through jumping extremal optimization technique. As a result, hierarchical partition of the given network can be obtained. Exper-imental results on several real-world networks show that, compared with those methods based on optimizing modularity Q, JEOMD can detect out hidden com-munity structure with different hierarchies and different scales more efficiently; comparative experiments on those real-world networks and their random counter-parts show that D with penalty term is more efficient than modularity function Q in some aspects.2. A novel local quantitative measure called normalized modularity density N M D is proposed. The advantage that NMD can improve the resolution limit of Q is proved. The close connection between NMD and normalized-cut is derived; that is to say if the number of communities m is predetermined, maximizing the measure NMD equals to minimizing normalized-cut. Simulated annealing algorithm is designed to optimize the indexes NMD. Experiments on a suit of computer-generated networks show that, compared with Q-based optimization methods, optimizing NMD can obtained the higher accuracy; comparative ex-periment on several real-world networks show that optimizing NMD can detect out finer community structure, which provides further evidence that NMD can improve the resolution limit of Q;NMD and D are generalized to their weighted versions. The similar resolu-tion limit problem of Qw and the new emerging negative community problem of Dw is analyzed, and then the related certifications on the advantages of N M Dw to Qw and Dw in these two aspects are derived. In order to compare the perfor-mances of the three indexes, simulated annealing algorithm is used to optimize them. Experiments on a suit of weighted computer-generated networks show that, compared with Qw-based methods, optimizing the index NMDw can ob-tained the higher accuracy; experiments on several real-world networks show that optimizing the index NMDw not only can detect out the community structure with different scales, especially some small and dense communities that optimiz-ing Qw can not detect, but also can avoid the negative community problem in Dw.3. A method called adaptive kernel affinity propagation (AKAP) is proposed to de-tect communities in networks, in which the normalized Markov diffusion kernel is used to implicitly measure the dissimilarities between different nodes and then adaptive affinity propagation is applied to optimize the obtained dissimilarity matrix. Comparative experiments on computer-generated networks show that AKAP can obtained the higher accuracy than Newman fast algorithm; experi- ments on several real-world networks demonstrate that adaptive kernel affinity propagation can detect the optimal number of communities and the meaningful communities.4. An efficient visualization method to nodes in complex networks is proposed. A new distance between nodes is defined. The obtained distance matrix is used as the geodesic distance of Isomap and as a result all nodes are projected into a two dimensional plane. The experiments on computer-generated networks show that, compared with energy-based models, the proposed method can keep local and global similarity better in original networks. When the given networks have clear community structure, the projected nodes also have compact clustering property. So whether the original network has community structure or not can be judged by the visualization results, and the detailed community memberships can be obtained by clustering the projected coordinates.