Researches Of Community Partition Algorithms In Complex Network

Any complex system which contains a large number of individual units can be regarded as complex network to study. The complex network shows a great deal of characteristics such as small-world, scale-free and community structure and so on. The community structure mainly depicts the relationship among nodes in the network. The salient feature of community structure is that the nodes in the same community linked more closely, while the nodes in the different communities linked more sparsely. The deeper understanding of the community structure in complex network is helpful to find the rules hidden in the network and predict the behavior of the network.In the paper, the common community detection algorithms are classified according to the different strategies such as optimization, heuristic, similarity and so on and the typical algorithms are studied and analyzed in detail. Aiming at the problems existing in community partitioning algorithms based on similarity, the paper proposed a ternary community merging algorithm based on similarity(STCMA). Then the paper applied the concept of ternary community to traditional label propagation algorithm, and further proposed a label propagation algorithm based on ternary community(TCLPA).(1) Ternary Community Merging Algorithm based on Similarity.In order to solve the conflict problems that may occur with using similarity to judge which nodes should be placed in the same community, the algorithm constructed the ternary community as the basic element to merge the communities. The algorithm can effectively enhance the close degree among the nodes in the same community through the introduction of ternary community, which highlights the community structure in the network. The time complexity of the algorithm is ? ?2O tm n, which n represents the number of nodes in the network, m represents the number of edges in the network and t represents the number of time of updating the node similarity threshold. The algorithm can preferably balance the relationship between time complexity and correct division rate.(2) Label Propagation Algorithm based on Ternary Community.Aiming at the two uncertain problems in traditional label propagation algorithm, one is the uncertain problem of the nodes update sequence when changing the label information of the nodes. The two is the uncertain problem of selecting the label information when the label information type of the nodes with the most same label information in the neighbor set is not unique. The algorithm constructed the initial core communities of the network based on the ternary community, and then computed the label dependence of the remaining nodes in the network combined with local optimal rules and depth calculation rules. Finally, the label information of these nodes was marked according to the label dependence.In the paper, the two algorithms proposed are verified by the artificial synthetic networks and real world networks. The experimental results are analyzed by using the standard mutual information, the correct classification rate and the modularity. At the same time, the two algorithms proposed in this paper are compared with the common community detection algorithms. The experimental results show that the two algorithms proposed in the paper not only have the higher partition accuracy, but also have the better performance in terms of operational efficiency.