Research And Implementation Of Community Discovery Algorithm For Dynamic Social Networks

The discovery of community structure is very essential to complex networks, and can be used in various fields, such as biology, computer science, sociology and so on. In this paper, we introduce the background and significance of the study of complex network at first, and then introduce the current progress about it. At the same time, basic theoretical knowledge about complex network is introduced in detail and some typical community discovery algorithms are described and analysized as well.For the current shortcomings of most existing community discovery algorithms, we propose a heuristic algorithm for community discovery (HCDA). First, a heuristic principle is proposed basing on the fundamental nature of community structure. Then, a measure function is derived as a criterion according to the module density function D. No priori condition is required in HCDA algorithm, and it gives competitive accuracy with previous modularity optimization methods, while it is computationally less expensive.Most complex systems in natural and social sciences are constantly changing, so the study of community discovery algorithm which could be applied to the dynamic social networks is very significant for analyzing and solving many practical problems in real world. By combining HCDA algorithm and the popular nature of most dynamic social networks, we propose a community discovery algorithm for dynamic social networks (DHCDA).Finally, we build a model for dynamic social network which is based on the novel of The Romance of the Three Kingdoms, describing the relationships of characters in four continuous periods. These networks all have a clear community structure based on experiments, so it can be used as a standard for accuracy testing on community discovery algorithms. Further validation for our algorithms which are proposed in this paper is conducted by applying them to the model of Three Kingdoms.