复杂网络的重叠社区及社区间的结构洞识别  

Identifying Overlapping Communities and Structural Holes Between Communities in Complex Networks

作　　者：刘世超[1] 朱福喜[1] 冯曦[1] 

机构地区：[1]武汉大学计算机学院,湖北武汉430072

出　　处：《电子学报》2016年第11期2600-2606,共7页Acta Electronica Sinica

基　　金：国家自然科学基金(No.61272277);中央高校基本科研业务费专项基金(No.274742)

摘　　要：大数据环境下如何有效地、准确地识别复杂网络的重叠社区是近年来学者关注的重点.本文提出一种基于多标签传播方式MLPS(Multiple Label Propagation Strategy)的重叠社区识别算法,该算法首先利用影响力最大化模型选取初始种子集合并赋予它们唯一的标签,然后采用结点间的相似性和影响传播特性共同作用于标签的传播迭代过程,迭代停止后将具有相同标签的结点划分为同一社区.通过合成网络和真实网络的实验验证了MLPS算法具有较高的准确度和模块度,且具有接近线性的时间复杂度.另外,在对MLPS算法输出的重叠结构进行分析的基础上,本文提出社区间的结构洞识别算法SHCDA(Structural Holes Between Communities Detection Algorithm),该算法通过分析重叠结构和重叠结点的位置特征,计算重叠结点作为结构洞的得分,最后输出top-k结构洞.本文在不同特性的数据集上进行实验,结果证明了SHCDA算法具有最好的准确度.Many researchers focus on how to detect overlapping communities effectively and accuratel.y when coping with large-scale networks in recent years. This paper proposes a novel overlapping community detection algorithm based on a multiple label propagation strategy, called MLPS algorithm. Firstly, MLPS selects a set of nodes as initial seeds by using In- fluence Maximization Model, each of which is assigned a unique label;Inspired by strategy based on similarity and influence diffusion, MLPS incorporates with these two strategies to guide the process of label propagation; Finally, nodes with the same tag are divided into one community after propagation. Experimental results on synthetic datasets and real networks illustrate that MLPS has both high accuracy and modularity at the same time. In addition, another algorithm named Structural Holes between Communities Detection Algorithm （SHCDA） is presented on the basis of the output of MLPS. SHCDA computes the scores of overlapping nodes who serve as structural holes by analyzing the overlapping structure and position feature of overlapping nodes, and then selects top-k structural holes as the output. Experimental results on different datasets show that SHCDA gets the best accuracy.

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]