Research on semi-supervised community discovery algorithm based on new annealing

Abstract

Based on the similarity of the community detection methods, the Givern-Newman (GN) algorithm is fast and accurate but has a higher running time. In order to improve the efficiency of GN Algorithm, this study presents a semi-supervised GN algorithm based on node similarity. By making full use of the constraint set of the prior knowledge must-link and cannot-link, the prior information is extended by the derived rules, and the extended information is verified by the method of distance measurement. Using new annealing maximisation algorithm to calculate node similarity iteratively, and validated using artificial and real networks. It proves that the proposed algorithm reduces the GN algorithm's running time and improves efficiency.

Keywords

• network theory (graphs)
• iterative methods
• complex networks
• graph theory
• social network theory
• optimisation
• must-link constraints
• new annealing maximisation algorithm
• semisupervised gn algorithm
• community detection methods
• semisupervised community discovery algorithm
• node similarity
• similarity information
• cannot-link constraints