Research Of Community Detection Algorithm Based On Node Degree Difference And Node Similarity

With the development of the society, more and more complex systems and social networking sites are becoming popular. The complex systems and social networking sites can be regarded as complex networks, such as:the friendly relationship social network, scientist cooperation network, movie actors’cooperation network, the transport network and so on. At the same time, the community structure which is the key structure of complex networks is researched by more and more researchers. So how to find the community structure exactly from the complex networks becoming an important topic.This paper is focus on the community detection problem. Because of the shortage of the some community detection algorithms which can’t achieve better results when the community structure of network is not obviously. Two new community detection algorithms DDSCDA and SPDDA proposed in this paper are to solve this problem. DDSCDA is abbreviation for Node Degree Difference and Similarity based Community Detection Algorithm. In this algorithm, firstly, we select a node with larger degree from the unclassified nodes as a kernel node which attracts its neighbors to join in the community the kernel node founded. Repeat this procedure until all the nodes are classified into the corresponding community. Then we get the coarse-grained community structure. Then taking the coarse-grained community as a starting point, we use the strategy of LPA to propagate labels through the network until every node’s label is the same with the most of its neighbors have. This algorithm can get the community structure correctly for the networks which not have the obvious community structure and the number of community is not known.SPDDA is abbreviation for Shortest Path and Node Degree Difference based Community Detection Algorithm. It uses the concept of the shortest path and the node degree difference to select the candidate kernel nodes, from which we select the unclassified node and attract its neighbors to form the community, repeat this procedure until all the nodes in the candidate kernel set are traversed. After this, the initial community structure is formed, and then we use the major voting principle to modify the initial community structure forming the finally community structure. This algorithm can detect the community structure of the network correctly.In this paper we test our algorithms on three real and one artificial synthetic social networks, the results we get can be visualization. Then we compared with several classical detection algorithms such as LPA, LPAm and FastQ, the experiment results have manifested that two algorithms can get better result for the networks which the number of community is not known whether the community structure is obvious or not.