基于三级邻居影响力分析的重叠社区发现算法

林 穗，陈仕双，姜文超,+，熊 梦，贺忠堂

(1.广东工业大学 计算机学院，广东 广州 510006； 2.东莞中国科学院云计算产业技术创新与育成中心 技术预研部，广东 东莞 523808)

0 引 言

复杂网络[1,2]是对现实世界各类实体及其彼此之间关联的抽象。现实世界中复杂关联实体构成的社区实体之间往往存在着重叠和交集，由许多个社区网络构成一个复杂网络。

重叠社区发现有多种方法，例如基于派系过滤CPM[3,4]的重叠社区发现算法，该算法将社区看作整个复杂网络中的一个全连通子图；Lancichinetti等[5]提出了基于拓展函数和局部优化的重叠社区发现算法LFM，该算法给每个节点设定一个F值列表，并每次迭代删除F值小于0的节点；王斌等[6]提出基于边图的重叠社区发现算法，该算法根据计算各边的相似度实现社区划分和发现重叠社区。基于标签传播的社区发现算法有Gregory等[7]提出的COPRA，该算法分配给每个节点一个初始标签，不断通过标签传播迭代直至节点标签稳定；Xie等[8]提出SLPA算法，该算法为每个节点每次迭代增加一个标签，再通过阈值r进行筛选标签；Lu等[9]提出LPANNI算法，该算法在标签传播基础上根据邻居节点影响力计算新的标签隶属度。

然而，目前重叠社区发现算法仍然存在准确度不高和效率低下等问题，例如CPM算法的时间复杂度较高；COPRA算法划分的社区质量不高且不稳定；SLPA算法的空间复杂度较高。针对以上问题，本文提出一种基于三级邻居节点影响力度量TIM[10]的重叠社区发现算法OCDITN(overlapping community discovery algorithm based on three-level neighbor node influence analysis)，并分别使用基于人工模拟生成的大规模网络图数据集和来自真实世界的网络数据集对OCDITN算法进行测试，与SLPA、LPANNI、COPRA算法相比，OCDITN算法划分的社区更稳定，质量更好，效率也更高。……