Similarity-based Community Detection Algorithm

In many real networks，community structure is a natural feature. The communitydetection in social networks has become an important problem in the study of the socialnetwork. It can enhance the insight into the intrinsic structure of networks, and is of greatsignificance to many related fields of social networks.Traditional community detection algorithm based on similarity algorithm, such as theGN algorithm, whose time complexity is very high, can not be applied to complexnetworks. The result of the community detection algorithm based on similarity measuredepends on the choice of similarity. May be some similarity selection makes the resultmore accurate, but for larger networks, the time complexity also have to be one of themain factors to consider, so the network can choose the different requirements of differentsimilarity metrics.The article first describes the current classical algorithm based on similarity measure,AP algorithm and GN algorithm. Then, the feature propose a similarity measure algorithmbased on diffusion kernel feature matrix and another similarity measure algorithm basedon a kind of matrix named DSD. These two algorithms, which improve the efficiency ofthe community detection algorithm, avoid the weakness of high complexity of GNalgorithm.This feature using the combination of Newman greedy algorithm and similaritymeasure based DSD by comparing these two algorithms the above-mentioned, whichcombines the advantages of CNM algorithm, to a certain extent, to avoid the situation ofthe uneven distribution of community size of the CNM algorithm.