第11卷第3期 智能系统学报 Vol.11 No.3 2016年6月 CAAI Transactions on Intelligent Systems Jun.2016 D0I:10.11992/is.201603048 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20160513.0910.002.html 基于社团结构的多粒度结构洞占据者发现及分析 赵姝12，赵晖12，陈洁2，陈喜12，张燕平12 (1.安徽大学计算机科学与技术学院，安徽合肥230601：2.安徽大学信息保障技术协同创新中心，安徽合肥 230601) 摘要：目前研究者已提出一些基于社团结构的结构洞发现方法，然而不同粒度下社团划分结果使网络呈现层次化 结构，影响社团结构中节点跨越结构洞的程度。本文基于网络社团划分思想提出一种分层网络的结构洞发现方法 MG_MxD。首先，使用分层递阶社团划分算法（本文使用EAGLE算法），得到不同粒度的社团结构：然后，使用结构 洞发现算法MG_MaxD得到不同粒度下的结构洞占据者：最后，使用结构洞跨越程度指标分析不同粒度下的社团结 构对节点跨越结构洞程度的影响。在公用和真实数据集上的实验结果表明节点跨越结构洞的程度即结构洞节点的 优势将随着粒度的变细而增大。 关键词：结构洞；社团结构：多粒度；层次结构；社团划分；分层网络；网络结构：社会网络分析 中图分类号：TP393文献标志码：A文章编号：1673-4785(2016)03-0343-09 中文引用格式：赵姝，赵晖，陈洁，等.基于社团结构的多粒度结构洞占据者发现及分析[J].智能系统学报，2016,11(3)：343-351. 英文引用格式：ZHAO Shu,ZHAO Hui,.CHEN Jie,etal.Recognition and analysis of structural hole spanner in multi-granularity based on community structure[J].CAAI transactions on intelligent systems,2016,11(3):343-351. Recognition and analysis of structural hole spanner in multi-granularity based on community structure ZHAO Shu'2,ZHAO Hui'2,CHEN Jie'2,CHEN Xi2,ZHANG Yanping'2 (1.School of Computer Science and Technology,Anhui University,Hefei 230601,China;2.Center of Information Support and Assur- ance Technology,Anhui University,Hefei 230601,China) Abstract:Recently,more and more attentions have been paid to research of structural holes,and some methods have been proposed to identify the structural holes based on the community structure.However,the network indi- cates a hierarchical structure after dividing into communities in different granularity,and influences the nodes'ex- tent to span structural holes in community structure.A structural hole spanners mining algorithm,named MG_ MaxD,is proposed which is in a hierarchical network based on the idea of network community division.First,differ- ent granular communities are partitioned by using hierarchical community dividing algorithm such as EAGLE in this paper).Then,structural hole spanners mining algorithm MG_MaxD is used to identifying the structural hole spanners in each granularity.Finally,using the measurement of the extent of node spanning structural holes to anal- ysis the effect of community structure under different granularity that influence the node's extent to span structural holes.Experimental results on public data and real data indicate that the extent of nodes to span structural holes namely the node's advantages will increase with the granularity get thinner. Keywords:tructural hole;community structure;multi-granularity;hierarchical structure;community division;hi- erarchical networks;network structure;social network analysis 在信息化技术迅猛发展的今天，社会网络在工 作生活中发挥着越来越重要的作用。网络中的信息 交流、资源交换已成为社会生活中不可缺少的重要 收稿日期：2016-03-20.网络出版日期：2016-05-13. 基金项目：国家高技术研究发展计划项目(2015AA124102):国家自然 途径。随着参与社会网络的个体增加，社会网络对 科学基金项目(61402006、61175046)：安徽省高等学校省级 于人们的重要性也随之增加，使得对社会网络的研 自然科学研究项目(KJ2013A016):安徽省自然科学基金项目 (1508085MF113):教育部留学回国人员科研启动基金项目. 究具有更深远的意义。近年来，对于社会网络的性 通信作者：赵蛛.E-mail:g0ngs7@163.com 质分析，逐渐从对网络整体结构分析，如发现网络的第 １１ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．３ ２０１６ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０３０４８ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１６０５１３．０９１０．００２．ｈｔｍｌ 基于社团结构的多粒度结构洞占据者发现及分析 赵姝１，２ ，赵晖１，２ ，陈洁１，２ ，陈喜１，２ ，张燕平１，２ （１．安徽大学 计算机科学与技术学院，安徽 合肥 ２３０６０１；２．安徽大学 信息保障技术协同创新中心，安徽 合肥 ２３０６０１） 摘 要：目前研究者已提出一些基于社团结构的结构洞发现方法，然而不同粒度下社团划分结果使网络呈现层次化 结构，影响社团结构中节点跨越结构洞的程度。 本文基于网络社团划分思想提出一种分层网络的结构洞发现方法 ＭＧ＿ＭａｘＤ。 首先，使用分层递阶社团划分算法（本文使用 ＥＡＧＬＥ 算法），得到不同粒度的社团结构；然后，使用结构 洞发现算法 ＭＧ＿ＭａｘＤ 得到不同粒度下的结构洞占据者；最后，使用结构洞跨越程度指标分析不同粒度下的社团结 构对节点跨越结构洞程度的影响。 在公用和真实数据集上的实验结果表明节点跨越结构洞的程度即结构洞节点的 优势将随着粒度的变细而增大。 关键词：结构洞；社团结构；多粒度；层次结构；社团划分；分层网络；网络结构；社会网络分析 中图分类号：ＴＰ３９３ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０３⁃０３４３⁃０９ 中文引用格式：赵姝，赵晖，陈洁，等．基于社团结构的多粒度结构洞占据者发现及分析［Ｊ］． 智能系统学报， ２０１６， １１（３）： ３４３⁃３５１． 英文引用格式：ＺＨＡＯ Ｓｈｕ，ＺＨＡＯ Ｈｕｉ，ＣＨＥＮ Ｊｉｅ，ｅｔ ａｌ．Ｒｅｃｏｇｎｉｔｉｏｎ ａｎｄ ａｎａｌｙｓｉｓ ｏｆ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅ ｓｐａｎｎｅｒ ｉｎ ｍｕｌｔｉ⁃ｇｒａｎｕｌａｒｉｔｙ ｂａｓｅｄ ｏｎ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１６，１１（３）： ３４３⁃３５１． Ｒｅｃｏｇｎｉｔｉｏｎ ａｎｄ ａｎａｌｙｓｉｓ ｏｆ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅ ｓｐａｎｎｅｒ ｉｎ ｍｕｌｔｉ⁃ｇｒａｎｕｌａｒｉｔｙ ｂａｓｅｄ ｏｎ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ＺＨＡＯ Ｓｈｕ １，２ ， ＺＨＡＯ Ｈｕｉ １，２ ， ＣＨＥＮ Ｊｉｅ １，２ ， ＣＨＥＮ Ｘｉ １，２ ， ＺＨＡＮＧ Ｙａｎｐｉｎｇ １，２ （１．Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ａｎｈｕｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｈｅｆｅｉ ２３０６０１， Ｃｈｉｎａ； ２．Ｃｅｎｔｅｒ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｕｐｐｏｒｔ ａｎｄ Ａｓｓｕｒ⁃ ａｎｃｅ Ｔｅｃｈｎｏｌｏｇｙ， Ａｎｈｕｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｈｅｆｅｉ ２３０６０１， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｒｅｃｅｎｔｌｙ， ｍｏｒｅ ａｎｄ ｍｏｒｅ ａｔｔｅｎｔｉｏｎｓ ｈａｖｅ ｂｅｅｎ ｐａｉｄ ｔｏ ｒｅｓｅａｒｃｈ ｏｆ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ， ａｎｄ ｓｏｍｅ ｍｅｔｈｏｄｓ ｈａｖｅ ｂｅｅｎ ｐｒｏｐｏｓｅｄ ｔｏ ｉｄｅｎｔｉｆｙ ｔｈｅ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ ｂａｓｅｄ ｏｎ ｔｈｅ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ． Ｈｏｗｅｖｅｒ， ｔｈｅ ｎｅｔｗｏｒｋ ｉｎｄｉ⁃ ｃａｔｅｓ ａ ｈｉｅｒａｒｃｈｉｃａｌ ｓｔｒｕｃｔｕｒｅ ａｆｔｅｒ ｄｉｖｉｄｉｎｇ ｉｎｔｏ ｃｏｍｍｕｎｉｔｉｅｓ ｉｎ ｄｉｆｆｅｒｅｎｔ ｇｒａｎｕｌａｒｉｔｙ， ａｎｄ ｉｎｆｌｕｅｎｃｅｓ ｔｈｅ ｎｏｄｅｓ’ ｅｘ⁃ ｔｅｎｔ ｔｏ ｓｐａｎ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ ｉｎ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ． Ａ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅ ｓｐａｎｎｅｒｓ ｍｉｎｉｎｇ ａｌｇｏｒｉｔｈｍ， ｎａｍｅｄ ＭＧ＿ ＭａｘＤ， ｉｓ ｐｒｏｐｏｓｅｄ ｗｈｉｃｈ ｉｓ ｉｎ ａ ｈｉｅｒａｒｃｈｉｃａｌ ｎｅｔｗｏｒｋ ｂａｓｅｄ ｏｎ ｔｈｅ ｉｄｅａ ｏｆ ｎｅｔｗｏｒｋ ｃｏｍｍｕｎｉｔｙ ｄｉｖｉｓｉｏｎ． Ｆｉｒｓｔ，ｄｉｆｆｅｒ⁃ ｅｎｔ ｇｒａｎｕｌａｒ ｃｏｍｍｕｎｉｔｉｅｓ ａｒｅ ｐａｒｔｉｔｉｏｎｅｄ ｂｙ ｕｓｉｎｇ ｈｉｅｒａｒｃｈｉｃａｌ ｃｏｍｍｕｎｉｔｙ ｄｉｖｉｄｉｎｇ ａｌｇｏｒｉｔｈｍ （ ｓｕｃｈ ａｓ ＥＡＧＬＥ ｉｎ ｔｈｉｓ ｐａｐｅｒ）． Ｔｈｅｎ， ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅ ｓｐａｎｎｅｒｓ ｍｉｎｉｎｇ ａｌｇｏｒｉｔｈｍ ＭＧ＿ＭａｘＤ ｉｓ ｕｓｅｄ ｔｏ ｉｄｅｎｔｉｆｙｉｎｇ ｔｈｅ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅ ｓｐａｎｎｅｒｓ ｉｎ ｅａｃｈ ｇｒａｎｕｌａｒｉｔｙ． Ｆｉｎａｌｌｙ， ｕｓｉｎｇ ｔｈｅ ｍｅａｓｕｒｅｍｅｎｔ ｏｆ ｔｈｅ ｅｘｔｅｎｔ ｏｆ ｎｏｄｅ ｓｐａｎｎｉｎｇ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ ｔｏ ａｎａｌ⁃ ｙｓｉｓ ｔｈｅ ｅｆｆｅｃｔ ｏｆ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｕｎｄｅｒ ｄｉｆｆｅｒｅｎｔ ｇｒａｎｕｌａｒｉｔｙ ｔｈａｔ ｉｎｆｌｕｅｎｃｅ ｔｈｅ ｎｏｄｅ’ｓ ｅｘｔｅｎｔ ｔｏ ｓｐａｎ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ． Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｏｎ ｐｕｂｌｉｃ ｄａｔａ ａｎｄ ｒｅａｌ ｄａｔａ ｉｎｄｉｃａｔｅ ｔｈａｔ ｔｈｅ ｅｘｔｅｎｔ ｏｆ ｎｏｄｅｓ ｔｏ ｓｐａｎ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ ｎａｍｅｌｙ ｔｈｅ ｎｏｄｅ’ｓ ａｄｖａｎｔａｇｅｓ ｗｉｌｌ ｉｎｃｒｅａｓｅ ｗｉｔｈ ｔｈｅ ｇｒａｎｕｌａｒｉｔｙ ｇｅｔ ｔｈｉｎｎｅｒ． Ｋｅｙｗｏｒｄｓ：ｔｒｕｃｔｕｒａｌ ｈｏｌｅ； ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ；ｍｕｌｔｉ⁃ｇｒａｎｕｌａｒｉｔｙ； ｈｉｅｒａｒｃｈｉｃａｌ ｓｔｒｕｃｔｕｒｅ； ｃｏｍｍｕｎｉｔｙ ｄｉｖｉｓｉｏｎ； ｈｉ⁃ ｅｒａｒｃｈｉｃａｌ ｎｅｔｗｏｒｋｓ； ｎｅｔｗｏｒｋ ｓｔｒｕｃｔｕｒｅ； ｓｏｃｉａｌ ｎｅｔｗｏｒｋ ａｎａｌｙｓｉｓ 收稿日期：２０１６⁃０３⁃２０． 网络出版日期：２０１６⁃０５⁃１３． 基金项目：国家高技术研究发展计划项目（２０１５ＡＡ１２４１０２）；国家自然 科学基金项目（ ６１４０２００６、６１１７５０４６）；安徽省高等学校省级 自然科学研究项目（ＫＪ２０１３Ａ０１６）；安徽省自然科学基金项目 （１５０８０８５ＭＦ１１３）；教育部留学回国人员科研启动基金项目． 通信作者：赵姝．Ｅ⁃ｍａｉｌ：ｇｏｎｇｘｓ７＠ １６３．ｃｏｍ． 在信息化技术迅猛发展的今天，社会网络在工 作生活中发挥着越来越重要的作用。 网络中的信息 交流、资源交换已成为社会生活中不可缺少的重要 途径。 随着参与社会网络的个体增加，社会网络对 于人们的重要性也随之增加，使得对社会网络的研 究具有更深远的意义。 近年来，对于社会网络的性 质分析，逐渐从对网络整体结构分析，如发现网络的