Community Detection Of Complex Network

With the continuous improvement of complex network theory and the deep exploration of application research, network science has gradually developed into a current hot topic. As a common property of various kinds of complex network,community structure has important theoretical significance and application value for understanding the structure and function of the network system, and it is also an important part of the network research. Theoretically, community detection is an NP problem, and its effective algorithm cannot avoid the contradiction between time complexity and calculating accuracy. The contradiction is becoming acute with the arrival of big data era. The development of a rapid and accurate community detection algorithm is a current focus on community structure research.The thesis firstly reviews the topological properties of complex networks and the characteristics of community structure. Secondly, based on the classic GN algorithm,we propose an improved GN algorithm to detect network without(intrinsic) edge weight and then extend to those with intrinsic edge weight. We test the improved algorithm on both artificial and real network, and the result shows that in the network with or without intrinsic edge weight, the algorithm can detect community structure more effectively. In addition, the edge weighting scheme based on edge betweenness can be directly applied to other detection algorithms.The modularity-based detecting method is a effective and widely used one for community detection of complex network. Considering the relation between the similarity of node in network theory and community structure, we proposed the community detection algorithm by combining modularity optimization detection algorithm with the local topological similarity. The key technology of the algorithm is to weight the network by using the local similarity of nodes, or to re-weight network with intrinsic edge weights. Then we detected the community structure of the weighted network based on the modularity-based method. In order to analyze the efficiency of the scheme, the three traditional community structure detection algorithms are employed and both the homogeneous and heterogeneous network models are adopted. The results indicate that the local similarity can enhance detecting precision without increasing the computing complex of traditional modularity-based methods.Finally, we presented a conclusion for our work and some prospects for futurework in this field.