重叠社区发现算法评价指标综述
Overview on Evaluation Indicators for Overlapping Community Discovery Algorithms
韩红旗 1徐紫燕 1李琳娜 1周则旭1
作者信息
- 1. 中国科学技术信息研究所,北京 100038;富媒体数字出版内容组织与知识服务重点实验室(国家新闻出版署),北京 100038
- 折叠
摘要
重叠社区发现算法对于理解复杂系统、发现复杂网络中隐藏的规律等具有很强的应用价值,而评价指标是算法发现高质量重叠社区的一个关键要素,算法的进步常常依赖于评价指标的进步.现有研究对非重叠社区发现算法的评价指标有较多的总结,而没有对重叠社区发现算法的评价指标进行总结.对重叠社区发现算法的评价指标进行了系统的总结和回顾,将指标分为事先知道社区结构、事先不知道社区结构和其它三大类.事先知道社区结构的评价指标包括基于混淆矩阵、基于ARI、基于NMI三个子类评价指标,事先不知道社区结构的评价指标包括基于模块度、基于密度、基于元数据三个子类评价指标,其它类主要介绍算法可扩展性评价指标.深入理解各种评价指标对于开发和优化重叠社区发现算法、在实际应用中发现高质量社区具有重要价值.
Abstract
Overlapping community discovery has a strong application value for understanding complex systems and discovering hidden laws in complex networks.Evaluation indicator is a key factor to find high-quality overlapping communities,and the progress of algorithms often depends on the progress of evaluation indicator.Existing studies have summarized the evaluation indicator of non-over-lapping community discovery algorithms,but have not summarized the evaluation indicator of overlapping community discovery algorithms.The evaluation indicators of overlapping community discovery algorithms are systematically summarized and reviewed.The indicators are divided into three categories:community structure known in advance,community structure unknown in advance and others.The evaluation indicators that the community structure is known in advance include three subcategories:confusion matrix-based,ARI-based and NMI-based.The evaluation indicators that the community structure is unknown in advance include three subcategories:modularity-based,density-based and metadata-based.The other categories mainly introduce the scalability indicator for large networks of millions of nodes and edges.A thorough understanding of various evaluation indicators is of great value to the development and opti-mization of overlapping community discovery algorithms and the discovery of high-quality communities in practical applications.
关键词
重叠社区/评价指标/社区发现/社区结构/复杂网络Key words
overlapping community/evaluation indicators/community discovery/community structure/complex network引用本文复制引用
基金项目
国家重点研发计划项目(2019YFA0707201)
中信所重点工作项目(ZD2023-11)
出版年
2024
国家科技期刊平台
NSTL
万方数据