Semi-supervised Community Detection Algorithm Based On Local Label Information

In the real world,many complex systems can be described as complex networks.Community structure,which is one of the important characteristics of complex networks,plays an important role in people's life.The timely and accurate discovery of the community structure hidden in the network and the analysis of the internal characteristics of the complex system can not only guide people's production activities,but also greatly help in understanding and controlling complex systems.Traditional community detection algorithms cannot be widely used due to their high time complexity,low accuracy of the classification results,and the need to specify community size in advance and so on.Based on this,we proposes a semi-supervised community detection algorithm based on local label information,in order to have a better performance in terms of time complexity and community detection accuracy.The network can be divided into the network structure of non-overlapped communities and the network structure of overlapping communities according to the number of their node's attribution categories.We starts from the two aspects and improves the traditional community detection algorithm.In the field of non-overlapping community detection,we improves the traditional LPA algorithm with faster running speed.Firstly,we proposes a LPA_S algorithm that combines Pearson's similarity.It uses the similarity information between nodes in the network to assist the label propagation process to reduce the randomness of label selection.Then,we proposes a semi-supervised community detection algorithm LPA_SI based on positive label prior information as Must-link and Must-in information,makes full use of positive label prior information in the network,and guides the label propagation process,which greatly improves the accuracy of community detection.Finally,we proposes a semi-supervised community detection algorithm LPA_SNI based on the prior knowledge of positive and negative labels as Cannot-link and Cannot-in information.It combines the positive label prior information and negative label prior information in the network to jointly guide the community detection process and make the accuracy of the community detection further improved.Through experiments on real networks and artificially generated networks,which use modularity Q and normalized mutual information NMI as the measurement standards for community detection accuracy,the results effectively prove that the improved algorithm is superior to the traditional LPA algorithm.In addition,the experiment also shows that the appropriate increase in the network of positive and negative labels,can significantly improve the accuracy of non-overlapping community detection.In the area of overlapping community detection,we improves the traditional COPRA algorithm.The COPRA algorithm has low time complexity,but it only considers the neighbor node information of the network in label propagation,so its community detection accuracy is not high.Therefore,we first proposes the COPRA_S algorithm based on Pearson similarity,combined with nodes in the network.The COPRA_S algorithm can effectively improve the accuracy of community detection.Then,we combine a small amount of positive label prior information in the network as Must-link and Must-in information,and improve the traditional COPRA algorithm,and propose a COPRA_SI algorithm based on positive label prior information,which improves the accuracy of community detection.Finally,we make full use of a few positive label information and negative label information as Cannot-link and Cannot-in information,propose the COPRA_SNI algorithm based on the positive and negative label prior information,and greatly improves the accuracy of community detection.Through experiments on real networks and artificially generated networks,and with the extension module degree EQ and normalized mutual information ONMI as the measurement standard of community detection accuracy,the accuracy of the proposed algorithm is effectively proved.In addition,experiments have also shown that by appropriately adding prior knowledge such as positive and negative labels in the network,the detection of community in overlapping communities can also improve the accuracy.The semi-supervised community detection algorithm based on local label information can effectively improve the accuracy of community detection.It lays a solid foundation for the semi-supervised learning research in the field of community detection and provides a theoretical basis for the application.