Research Of Neighbor Similarity Based And Semi-Supervised Community Detection Algo-rithms

Community detection is a major part of social network analysis and data mining, scholars over the world are researching it. In the last years, many classic community detection algorithms were proposed. All of these algorithms are based on Agglomerative Hierarchical Model or Divisive Hierarchical Model. The most famous are LPA, FastQ, GN, etc. However, there is no one algorithm can perform well on all datasets.In this paper we designed two community detection algorithms, they are NSA(Neighbor Similarity based Algorithm) and SSCDAWSP(Semi-Supervised Community Detection Algorithm With Selected-Point).(1).NSA:NSA algorithm is consist of two steps, the main task of the first step is to get the early form of community structure, than optimize it in the second step. During detecting the community structure, NSA algorithm only calculates the similarities between a node and its neighbors, without considering the other nodes. This is somehow like LPA(Label Propagation Algorithm), the only difference is that LPA cares about is the label relation between a node and its’ neighbors. So, NSA has a near liner time complexity just like LPA. What’s more, the experiment results showed that NSA can get better community structure than some algorithms on some datasets.(2).SSCDAWSP:this algorithm is based on semi-supervised learning. In this algorithm we designed BV(Boundary Value), KV(Kernel Value) and SV(Subjection Value) for nodes in a graph. We use these definitions to choose nodes and query their labels before community detection, than the labeled nodes will provide supervised information during the community detection process. Compare to most algorithms, SSCDAWSP has advantages in complexity and precision, this is shown in experiments at chapter four.