电子学报 ›› 2016, Vol. 44 ›› Issue (11): 2600-2606.DOI: 10.3969/j.issn.0372-2112.2016.11.006

• 学术论文 • 上一篇    下一篇

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

刘世超, 朱福喜, 冯曦   

  1. 武汉大学计算机学院, 湖北武汉 430072
  • 收稿日期:2015-05-12 修回日期:2015-11-09 出版日期:2016-11-25 发布日期:2016-11-25
  • 通讯作者: 朱福喜
  • 作者简介:刘世超,男,1989年2月出生,河南周口人.武汉大学计算机学院博士生,研究方向为社会网络分析和Web数据挖掘.E-mail:nani@whu.edu.cn;冯曦,女,1991年11月出生,陕西西安人.武汉大学计算机学院硕士生,研究方向为社会网络分析和数据挖掘.E-mail:fengxiwhu@outlook.com
  • 基金资助:

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

Identifying Overlapping Communities and Structural Holes Between Communities in Complex Networks

LIU Shi-chao, ZHU Fu-xi, FENG Xi   

  1. Computer School of Wuhan University, Wuhan, Hubei 430072, China
  • Received:2015-05-12 Revised:2015-11-09 Online:2016-11-25 Published:2016-11-25

摘要:

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

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

Abstract:

Many researchers focus on how to detect overlapping communities effectively and accurately 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 Influence 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.

Key words: complex networks, overlapping community, multiple label propagation, structural holes detection

中图分类号: