Community Structure Detection In Complex Networks

Complex networks have recently received extensive attention from physics and other disciplines. A lot of experimental findings have uncovered that complex networks in various fields share many common structural properties such as small-world property, scale-free feature, community structure etc. In the thesis, we studied the detection and characterization of the community structure in networks. The emergence of community structure in complex networks means that networks often consist of groups of vertices within which connections are dense while between which they are sparser. Such a property of networks may play an important role in dynamics of networks, on the other hand, communities in networks often correspond such functional units as real social groupings in social networks, sets of pages on related topics on the WWW, or sets of related papers on a single topic in citation networks. Thus, detecting and analyzing these communities in networks will help us understand the structure and function of real complex networks more effectively. In order to detect communities in networks quickly and accurately, a variety of community detection algorithms have been proposed, but it is still an important problem how to deal with the conflict between the time-complexity and accuracy of algorithms. We analyzed the existing algorithms for detecting community structure in complex networks systematically. Then, we designed a scheme for improving the accuracy of community structure algorithms, and proposed a class of improved algorithm according to the scheme.The thesis consists of five chapters. In chapter one, we gave a brief review for complex networks, and then introduced the main content and organization of this thesis. In chapter two, we briefly presented some structural properties of real networks, and introduced community structure in complex networks in detail, including definitions of communities, community structure detection and evaluation of partitions of networks into communities. In chapter three, we investigated some community detection algorithms as well as their performance, and because of the need of our studies we analyzed the extension of these algorithms to weighted networks as well as the change of these algorithms'performance after considering intrinsic edge weight of networks. In chapter four, we firstly designed a scheme for improving the accuracy of community detection algorithms in networks based on the analysis in previous chapter, and then proposed a class of improved Girvan-Newman algorithms according to the scheme. Testing these algorithms on both artificial and real-world networks, we find that our improved algorithms can discover communities of networks better than the original algorithm. In addition, our improved algorithms were also extended to weighted case in order to make use of the information contained in intrinsic edge weight; our test results shown that the weighted versions of our improved algorithms also outperform that of the original algorithm, as the intrinsic edge weight in networks is considered. These results indicated that we really improve the performance of the Girvan-Newman algorithm successfully, and it is also proved that our scheme for improving detection algorithms is also applicable. In chapter five, we presented a conclusion for our work and some prospects for future work in this field.