Research On Community Detection Algorithms Based On Label Propagation

In recent years, with the rapid development of Internet and computer technology,complex networks grew rapidly, such as social networks, biological informationnetwork, semantic Web network, and the related research of complex networks alsoreceived extensive attention of academia and industry.Community is a significantcharacteristic of complex networks, which represents the network having a certainrelationship between the set of objects. The internal nodes in the community connectclosely, but nodes between different community connect relatively sparsely. Throughthe study of community structures in complex networks, we can draw a large amountof information about complex networks and it plays an increasingly important role inthe understanding of network structure. Therefore the discovery of the networkcommunity structure is conducive to our better understanding and using the potentialof specific groups in the Internet, then mining the value of specific groups.Most of the current community detection algorithms are based on the networktopology, these algorithms generally are short of the low accuracy, the high timecomplexity and the single factor clustering. The label propagation algorithm is acommon community detection algorithm based on the network topology, which ownsthe fast, simple and efficient characteristic, however, it is also lack of randomness,accuracy and robustness. To solve the above problems, this paper considers the nodeattribute information and the topology information of the graph, and proposes twokinds of the new improved community detection algorithms based on labelpropagation.The label propagation community detection algorithm based on node degree ofbelonging firstly chooses one node whose degree is the largest and clusteringcoefficient is larger and its neighbors as the initial community. Then the initialcommunity attracts its neighbor nodes to join the community according to the nodebelonging degree math, so circulates, until all qualified nodes are added to thecorresponding community. At this time the rough community structure is built.Finally using label propagation algorithm improves the rough community structure,so circulates, until all node labels are same with the label accounted for most of theirneighbor nodes.The algorithm is over. The label propagation community detectionalgorithm based on node degree of belonging is suitable for small and medium-sizednetworks, has good time complexity, and can more accurately detect the communitystructure of complex networks.When the complex network includes a large number of vertexes and the degreeof most vertexes are large, the accuracy of the above method is not good. So wepropose a new method called the label propagation community detection algorithmbased on node difference.The method firstly constructs a candidate core node setthrough the node degree, clustering coefficient and node difference. Then accordingto the similarity between nodes join the neighbor nodes who meet the conditions tothe community. Finally using label propagation algorithm improves the roughcommunity structure, so circulates, until all node labels are same with the labelaccounted for most of their neighbor nodes.The algorithm is over. The labelpropagation community detection algorithm based on node difference fully considerthe direct and the indirect contraction between each node, so the effect of communitydetection is more perfect and the accuracy has been further improved.Finally, according to the above community detection methods, this paper testsand verifies by lots of experiments. By testing the effectiveness of communitystructure and the community detection efficiency which are detected, it fully verifiesthe feasibility and superiority of this community detection method.