Evaluating community quality based on ground-truth

• Published in: Information sciences 2022-06, Vol.599, p.104-126
• Main Authors: Wang, Chunnan, Wang, Hongzhi, Mu, Tianyu, Qi, Zhixin
• Format: Article
• Language: English
• Subjects: Community quality; Community scoring functions; Ground-truth communities; Local community detection
• ISSN: 0020-0255; 1872-6291
• DOI: 10.1016/j.ins.2022.03.066

An effective Community Scoring Function (CSF) is very important since it can properly quantify the community quality of the node groups and help us to effectively discover valuable network communities. Currently, researchers have proposed many types of CSFs. However, none of them are based on an experimental and theoretical analysis of the node groups with different scales and community qualities. This may significantly weaken their effectiveness. Besides, there are few experiments to comprehensively analyze the effectiveness of the existing CSFs. In this paper, we try to make up for these shortcomings. We analyze the node groups with different scales and community qualities in real-world networks, and find effective functions to measure internal and external connection densities of the groups. We then obtain a novel and robust CSF called ECOQUG by effectively combining two kinds of functions that we determined. We design extensive experiments to contrast the performance of ECOQUG with 13 commonly used CSFs. The final experiments show that ECOQUG performs best among them, which demonstrates its reliability. Furthermore, in order to further demonstrate the necessity and significance of an effective CSF, we optimize the TCE algorithm by applying ECOQUG and an improved expansion method, and produce a new Local Community Detection (LCD) algorithm called Max-ECOQUG. We compare Max-ECOQUG with TCE and other better designed LCD algorithms with different CSFs. The results show that the CSF has a greater impact on the performance of LCD algorithms than the design method, and an effective CSF is necessary and significant.