Study And Implementation Of Community Detection Technology

In recent years, with the development of the complex networks, there have been numerous and various complex networks with the development of science, technology and human society, such as the Internet, the World Wide Web, the network of air lines, large-scale electric power networks, the structure of a piece of very large scale integration, the human social relationships, etc. Empirical studies and theoretical modeling of networks have been the subject of a large body of recent research in statistical physics and applied mathematics. And people find a property that seems to be common to many networks is community structure. Community detection in large networks is potentially very useful. Detecting communities in networks lead us to more efficiently understand and develop these networks.Especially, with the rapid development of Internet, it has increasingly large amounts of information, and it has become the world's largest reservoir of information dissemination. Currently numerous information is on the Internet, but the method of analyzing the content of information yet to be resolved. Community detection technology can solve this problem to some extent; by using it, users will not only save time but can also greatly improve efficiency. Consequently, community detection technology which is used in information mining has importantly meaning of theory and value of practicality. This thesis aims to discuss the theory, algorithms and implementation of community detection technology.However, we often have no idea how many communities we wish to discover in networks, the problem of community detection is quite challenging. First we describe the basic concept of the community detection technology and analyze the existing models, such as the Belief Propagation algorithm, k-means (k-centers) algorithm, Kernighan-Lin algorithm, spectral algorithm, W-H algorithm, GN algorithm, Clique Percolation Method and so on. And as for these algorithms, we study their core idea, thecomplexity, the scope of application and so on.We implement the typical algorithm in community detection: GN algorithm anddetect by using data set. Further, we also program Affinity Propagation (AP) algorithm which is proposed by Frey. By implementing and analyzing, we have deeply understanding of the idea, the complexity of AP algorithm. We also improve the AP algorithm by doing a little change on the original algorithm. And we design a new method of community detection by make use of communication relation in social networks, which it is called communication relation algorithm. By comparing the experimental results of these algorithms, we analyze and study these algorithms, and get ready for further study in the future.