一种加权稠密子图社区发现算法

来源：软件学报杂志2017年第11期北京时间：

作者：杨贵,郑文萍,王文剑,张浩杰

单位：杨贵，山西大学 计算机与信息技术学院, 山西 太原 03000611,郑文萍，山西大学 计算机与信息技术学院, 山西 太原 030006;计算智能与中文信息处理教育部重点实验室(山西大学), 山西 太原 03000602,王文剑，山西大学 计算机与信息技术学院, 山西 太原 030006;计算智能与中文信息处理教育部重点实验室(山西大学), 山西 太原 03000603,张浩杰，计算智能与中文信息处理教育部重点实验室(山西大学), 山西 太原 03000604

摘要：目前，针对复杂网络的社区发现算法大多仅根据网络的拓扑结构来确定社区，然而现实复杂网络中的边可能带有表示连接紧密程度或者可信度意义的权重，这些先验信息对社区发现的准确性至关重要.针对该问题，提出了基于加权稠密子图的重叠聚类算法（overlap community detection on weighted networks，简称OCDW）.首先，综合考虑网络拓扑结构及真实网络中边权重的影响，给出了一种网络中边的权重定义方法；进而给出种子节点选取方式和权重更新策略；最终得到聚类结果.OCDW算法在无权网络和加权网络都适用.通过与一些经典的社区发现算法在9个真实网络数据集上进行分析比较，结果表明算法OCDW在F度量、准确度、分离度、标准互信息、调整兰德系数、模块性及运行时间等方面均表现出较好的性能.

关键词：复杂网络;社区发现;图聚类;重叠聚类;稠密子图

基金资助：国家自然科学基金（61673249，61572005）；山西省回国留学人员科研基金（2016-004，2017-014）