Font Size: a A A

Research On Community Structure Detection Algorithm In Complex Network

Posted on:2016-01-21Degree:MasterType:Thesis
Country:ChinaCandidate:T XiaFull Text:PDF
GTID:2180330464972456Subject:Software engineering
Abstract/Summary:PDF Full Text Request
In recent years, complex network community detection has become one hot issue of many fields, including computer science, biology, sociology, etc. Detecting community structure accurately and efficiently is a good field worthy of further study. There are some problems on existing algorithms, such as too many parameters, complicated process, high time complexity and so on. In order to detect the community structure of large-scale network quickly and accurately, this paper proposes a detection algorithm based on central nodes communities and entropy loss, inspired by the heuristic strategies,the compute methods of merging communities and the assess measures of the network dividing of some classic detection algorithm. The algorithm iteratively choices the node that has most neighbors (namely has the highest degree) and assembles it with its neighbors into an initial community, then find out the least initial communities that cover the whole nodes of the network successively and compute the merged entropy loss of every pair of neighboring initial community. Each time two communities that get minimal entropy loss will be merged and other communities’entropy will be updated, then take modularity Q as the evaluate function for the merge sequence, the one which achieve maximum Q is the optimal community structure partition of the network.To check the performance of above method, firstly the time complex analysis of the algorithm is made and the result indicates that the algorithm is linear time relates with the number of initial neighboring community pairs. Then the algorithm is applied on some random networks and real networks. Compared with several classic algorithms at present, the algorithm is proved to be high accuracy and approximately linear time complexity.
Keywords/Search Tags:Community Detect, Central Nodes, Entropy loss, Communities merge
PDF Full Text Request
Related items