Research On Algorithms For Detecting Community Structure In Complex Networks

As theoretical and practical value of complex networks are being developed in different fields, more and more people have paid their attention to community structure, which is one of important characteristics of complex networks. Detecting community structure is helpful to understand the composition and the function of complex network. For this reason, a number of algorithms for detecting community structure have been proposed. In this thesis, we focus on detecting the individual community structure in complex networks and propose two algorithms. One algorithm is based on spectral method and affinity propagation, and another one is based on a local method. Besides, we implement a visual experiment platform.We research the original spectral method based on the Normal matrix and the affinity propagation clustering algorithm. The original spectral method based on the Normal matrix uses distribution of elements in the 2nd eigenvector to divide vertices. However, in some networks with fuzzy community structure, these elements assemble curve, so it's hard to get good division. In order to solve this problem, we propose an algorithm that combines spectral method with affinity propagation. This algorithm uses the affinity propagation to cluster the elements in several eigenvectors of the Normal matrix, and determines the community structure on the basis of clustering result. On the premise of unknowing the number of communities, this algorithm works well on some networks with fuzzy community structure.In order to solve the problem that some algorithms for detecting community structure have high time complexity, we propose a fast algorithm based on finding local communities. In this thesis, we describe a local method for determining the membership of a single vertex. Then we use this local method iteratively on the network and its subnets to detect global community structure. The algorithm has low time cost under the condition of unknowing the number of communities.We design and implement a visual experiment platform. This platform could visualize the detecting results and compute relevant data. We compare our algorithms with GN algorithm and CNM algorithm. The experimental data show that the algorithm based on spectral method and affinity propagation has good performance on networks even without obvious community structure. The algorithm based on a local method has low time cost and works well. Both algorithms needn't to know the number of communities before detection.