Semi-supervised Algorithm Research For Community Structure Detection

The in-depth research of social networks and complex networks in real life indicates that the analysis of the relationship between communities can help us better understand the topological structure and functional characteristics. The problem of community detection becomes a fundamental issue of complex network.The traditional methods of community detection have high requirement of the accuracy about the related information of network structure because they solely rely on the topology of the network. Thus, the performance of these methods will be significantly decreased when the networks contain noises (i.e. the wrong connections between nodes). However, the interference caused by noise can be resisted by priori information, such as individual labels or pairwise constraints. In this paper, we improve the accuracy and robustness of the algorithm by incorporating the prior information into the process of community detection. The main contribution is follows:(1) The proposed SEO-SS algorithm uses the priori information to modify the local and global variables in the form of punishment or reward to guide the process of community detection. So we can get the best community partition by optimizing the objective function. In addition, SEO-SS algorithm also takes the advantage of the network’s topology to initialize the partition instead of the traditional random partition in EO algorithm, which improves the time efficiency. Experiments on the related networks show that, compared with existing approaches, the proposed SEO-SS algorithm not only improves the accuracy of community detection, but also shows good performance with noise of connections in the network.(2) To improve the community detection performance by using the prior information, the accuracy of prior information is demanding. If the priori information has errors or conflicts, the community detection process will neither be guided to the right direction, nor bring positive affect. Therefore, we propose PCSEO-SS algorithm to process the wrong or conflicting constraints in semi-supervised community detection method. The priori information will properly guide the community detection process by using the dissimilarity index to correct the type of pairwise constraints. The experimental results on networks show that, compared with other semi-supervised community detection algorithms, PCSEO-SS algorithm can effectively identify the conflict constraints in network and improve the accuracy of community detection.