Dissertation > Mathematical sciences and chemical > Mathematics > Algebra,number theory, portfolio theory > Combinatorics ( combinatorics ) > Graph Theory

Research on Overlapping Community Detection in Complex Networks

Author WangYanPeng
Tutor WangLi
School Taiyuan University of Technology
Course Applied Computer Technology
Keywords Complex networks Overlapping communities Fitness Community discovery A total of close neighbors.
CLC O157.5
Type Master's thesis
Year 2011
Downloads 336
Quotes 1
Download Dissertation

Complex network research community finding algorithm has a very important theoretical and practical significance, so it has been widespread concern of researchers in various fields, including computer science, mathematics, physics, biology, sociology, and economics. Their research has made some important outcomes, such as non-overlapping communities GN algorithm discovery methods and factions filtering methods allow nodes overlap overlapping communities discovery algorithm. How to evaluate the merits of community discovery algorithm results, Newman et al proposed the concept of modularity, scholars extend the concept of modularity to the various networks including overlapping community network, and the different expressions. This paper first introduces a complex network of overlapping the community discovery research background and significance, as well as complex network community discovery algorithm Research. Second of basic knowledge of the theory of complex networks, including the historical progress of complex networks, network diagram model representation methods, many of the complex network structure characteristics, as well as networks of complex network topology model. Once again, this article discusses the concept of community, evaluation criteria - modularity and the community by the in-depth study. And found that the algorithm of this community, especially overlapping communities discovery algorithm to more in-depth discussion, found that current algorithm there are still many inadequacies, such as overlapping the LFK algorithm to be able to cover the entire network of community found, but can not guarantee the stability of the multiple runs and can easily lead to overlap spend a large problem. For the shortcomings of the current algorithm, we learn from the natural community to the formation of thinking, and to modify the criteria of natural communities, has been the formation of natural communities of this article algorithm. This article we examine the overlap between the community, the community neighbors overlapping communities overlap judgment account for a large proportion of affected communities overlap factors This article summarizes the standard of community metrics premise Community The overlap of the criteria for judging the degree of overlap the concept of the COD. Overlap much features a lot of natural communities exist in natural communities divided, taking into account the actual situation, these natural communities may be errors divided into multiple communities, this article the natural communities merger process, the use of COD as judged by the natural The Community merger standards of adjustable fitness and close neighbors of overlapping community finding algorithm OCNF. Experimental results show that the algorithm can get a better division results by adjusting the different parameters. In this paper, overlapping community partitioning algorithm OCNF able to successfully detect overlapping nodes in the network, however there are still some areas for improvement, and also need to further improve the complexity of how to reduce the time to run the algorithm runs results and graphical display. .

Related Dissertations
More Dissertations