Research On Evaluation Method Of Community Detection Algorithms In Large-scale Social Networks

Complex networks can describe many complex systems well.Through researching and analyzing of complex networks,we can reveal and master their statistical characteristics,functional characteristics,evolution rules and so on,so that we can understand the complex system more deeply and solve the practical problems easily.In the study,it was found that there are community structures in complex networks,and the community structures are very important to understand the structure and function of complex networks,so many researchers were involved in the study of community detection algorithms and its evaluation methods.In this paper,we first introduced three community detection algorithms—CPM algorithm,CoDA algorithm and BLMPA algorithm.CPM algorithm is the first community detection algorithm which can identify overlapping communities.CoDA algorithm can not only recognize traditional communities but also identify 2-model communities.BLMPA algorithm has the advantages of fast speed and good stability.Secondly,we used F-measure evaluation method to evaluate the three algorithms under generated networks,and used Qa evaluation method to evaluate the three algorithms under real networks.At last,we proposed an overlapping community evaluation method based on node-pairs’ sequence(EOCNS).In this evaluation method,we gave the concepts of rag community and node-pairs’ sequence.When community detection algorithms are evaluating,the rag community ensures that single-node communities are not ignored and the node-pairs’ sequence ensures that duplicate node-pairs are not ignored,so as to ensure the completeness of communities.By the lights of the harmonic mean F1 in the F-measure criterion,we proposed the metric harmonic mean based on node-pairs’ sequence(FS)which describes the differences of overall community structures between predicted communities and real communities and the metric difference of overlap degree(DOD)which describes the differences of overlapping community structures between predicted communities and real communities.And then we used the EOCNS method to evaluate CPM algorithm,CoDA algorithm and BLMPA algorithm in detail under generated networks.And the result shows that the proposed evaluation method is valid for the evaluation of overlapping community detection algorithms.