Analysis Of Community Structure In Complex Networks

The modern science of networks has brought significant advances to our understanding of complex systems. One of the most relevant features of complex networks is community structure. A community structure is a densely connected subset of nodes that is only sparsely linked to the remaining networks. Detecting communities in complex networks is of great importance in sociology, biology and computer science and so on.In recent years, a lot of community discovery algorithms have been proposed aiming at different kinds of large scale complex networks. In this paper, we have summarized some latest representative algorithms and have pointed out the important progress in this research area. By which order of degree distribution of networks, the community structure in complex networks can be remarkably maintained is always one problem up in the air in the network science. Then, we have studied the problem with the aid of random rewiring algorithm and community structure detection algorithm. Finally, we have constructed a new algorithm which can detect the hierarchical and overlapping communities in weighted networks. We have analyzed the characteristics of Wealink, especially the dynamic evolutions of communities in the network.The main contributions of the dissertation are summarized as follows.1 We have reviewed some latest representative algorithms, focusing on the improved methods based on the modularity function, algorithms which can detect overlapping and hierarchical community structure in networks, benchmark in detecting communities. We have pointed out some promising directions in this area.2 We have compared the community structures of real networks with computer-generated network models on which the random rewiring process took place and have found that community structure is well maintained after third-order random rewiring. We have established a path towards construction of random graphs matching the community structure property of real networks after the third-order random rewiring.3 We have designed a new community detection algorithm which can detect the hierarchical and overlapping communities of networks in a reasonably short time. We have proposed another new algorithm which can detect the dynamic evolution of communities when the evolution of networks is not so significant when compared to the whole size of networks. We have also used the benchmark graphs to compare the advantages and disadvantages of three main algorithms.4 We have studied characteristics and structural evolutions of a large online social network-Wealink (http://www.wealink.com), including network size, community structure, overlapping nodes, clustering coefficient and the distributions of degree and so on, especially the dynamic evolutions of community structure in the network.