摘要：大数据环境下如何有效地、准确地识别复杂网络的重叠社区是近年来学者关注的重点.本文提出一种基于多标签传播方式MLPS（Multiple Label Propagation Strategy）的重叠社区识别算法,该算法首先利用影响力最大化模型选取初始种子集合并赋予它们唯一的标签,然后采用结点间的相似性和影响传播特性共同作用于标签的传播迭代过程,迭代停止后将具有相同标签的结点划分为同一社区.通过合成网络和真实网络的实验验证了MLPS算法具有较高的准确度和模块度,且具有接近线性的时间复杂度.另外,在对MLPS算法输出的重叠结构进行分析的基础上,本文提出社区间的结构洞识别算法SHCDA（Structural Holes Between Communities Detection Algorithm）,该算法通过分析重叠结构和重叠结点的位置特征,计算重叠结点作为结构洞的得分,最后输出top-k结构洞.本文在不同特性的数据集上进行实验,结果证明了SHCDA算法具有最好的准确度.

关键词：复杂网络 重叠社区 多标签传播 结构洞识别 

单位：武汉大学计算机学院; 湖北武汉430072