第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 质分析，逐渐从对网络整体结构分析，如发现网络的
第 １１ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．３ ２０１６ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０３０４８ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１６０５１３．０９１０．００２．ｈｔｍｌ 基于社团结构的多粒度结构洞占据者发现及分析 赵姝１，２ ，赵晖１，２ ，陈洁１，２ ，陈喜１，２ ，张燕平１，２ （１．安徽大学 计算机科学与技术学院，安徽 合肥 ２３０６０１；２．安徽大学 信息保障技术协同创新中心，安徽 合肥 ２３０６０１） 摘 要：目前研究者已提出一些基于社团结构的结构洞发现方法，然而不同粒度下社团划分结果使网络呈现层次化 结构，影响社团结构中节点跨越结构洞的程度。 本文基于网络社团划分思想提出一种分层网络的结构洞发现方法 ＭＧ＿ＭａｘＤ。 首先，使用分层递阶社团划分算法（本文使用 ＥＡＧＬＥ 算法），得到不同粒度的社团结构；然后，使用结构 洞发现算法 ＭＧ＿ＭａｘＤ 得到不同粒度下的结构洞占据者；最后，使用结构洞跨越程度指标分析不同粒度下的社团结 构对节点跨越结构洞程度的影响。 在公用和真实数据集上的实验结果表明节点跨越结构洞的程度即结构洞节点的 优势将随着粒度的变细而增大。 关键词：结构洞；社团结构；多粒度；层次结构；社团划分；分层网络；网络结构；社会网络分析 中图分类号：ＴＰ３９３ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０３⁃０３４３⁃０９ 中文引用格式：赵姝，赵晖，陈洁，等．基于社团结构的多粒度结构洞占据者发现及分析［Ｊ］． 智能系统学报， ２０１６， １１（３）： ３４３⁃３５１． 英文引用格式：ＺＨＡＯ Ｓｈｕ，ＺＨＡＯ Ｈｕｉ，ＣＨＥＮ Ｊｉｅ，ｅｔ ａｌ．Ｒｅｃｏｇｎｉｔｉｏｎ ａｎｄ ａｎａｌｙｓｉｓ ｏｆ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅ ｓｐａｎｎｅｒ ｉｎ ｍｕｌｔｉ⁃ｇｒａｎｕｌａｒｉｔｙ ｂａｓｅｄ ｏｎ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１６，１１（３）： ３４３⁃３５１． Ｒｅｃｏｇｎｉｔｉｏｎ ａｎｄ ａｎａｌｙｓｉｓ ｏｆ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅ ｓｐａｎｎｅｒ ｉｎ ｍｕｌｔｉ⁃ｇｒａｎｕｌａｒｉｔｙ ｂａｓｅｄ ｏｎ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ＺＨＡＯ Ｓｈｕ １，２ ， ＺＨＡＯ Ｈｕｉ １，２ ， ＣＨＥＮ Ｊｉｅ １，２ ， ＣＨＥＮ Ｘｉ １，２ ， ＺＨＡＮＧ Ｙａｎｐｉｎｇ １，２ （１．Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ａｎｈｕｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｈｅｆｅｉ ２３０６０１， Ｃｈｉｎａ； ２．Ｃｅｎｔｅｒ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｕｐｐｏｒｔ ａｎｄ Ａｓｓｕｒ⁃ ａｎｃｅ Ｔｅｃｈｎｏｌｏｇｙ， Ａｎｈｕｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｈｅｆｅｉ ２３０６０１， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｒｅｃｅｎｔｌｙ， ｍｏｒｅ ａｎｄ ｍｏｒｅ ａｔｔｅｎｔｉｏｎｓ ｈａｖｅ ｂｅｅｎ ｐａｉｄ ｔｏ ｒｅｓｅａｒｃｈ ｏｆ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ， ａｎｄ ｓｏｍｅ ｍｅｔｈｏｄｓ ｈａｖｅ ｂｅｅｎ ｐｒｏｐｏｓｅｄ ｔｏ ｉｄｅｎｔｉｆｙ ｔｈｅ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ ｂａｓｅｄ ｏｎ ｔｈｅ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ． Ｈｏｗｅｖｅｒ， ｔｈｅ ｎｅｔｗｏｒｋ ｉｎｄｉ⁃ ｃａｔｅｓ ａ ｈｉｅｒａｒｃｈｉｃａｌ ｓｔｒｕｃｔｕｒｅ ａｆｔｅｒ ｄｉｖｉｄｉｎｇ ｉｎｔｏ ｃｏｍｍｕｎｉｔｉｅｓ ｉｎ ｄｉｆｆｅｒｅｎｔ ｇｒａｎｕｌａｒｉｔｙ， ａｎｄ ｉｎｆｌｕｅｎｃｅｓ ｔｈｅ ｎｏｄｅｓ’ ｅｘ⁃ ｔｅｎｔ ｔｏ ｓｐａｎ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ ｉｎ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ． Ａ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅ ｓｐａｎｎｅｒｓ ｍｉｎｉｎｇ ａｌｇｏｒｉｔｈｍ， ｎａｍｅｄ ＭＧ＿ ＭａｘＤ， ｉｓ ｐｒｏｐｏｓｅｄ ｗｈｉｃｈ ｉｓ ｉｎ ａ ｈｉｅｒａｒｃｈｉｃａｌ ｎｅｔｗｏｒｋ ｂａｓｅｄ ｏｎ ｔｈｅ ｉｄｅａ ｏｆ ｎｅｔｗｏｒｋ ｃｏｍｍｕｎｉｔｙ ｄｉｖｉｓｉｏｎ． Ｆｉｒｓｔ，ｄｉｆｆｅｒ⁃ ｅｎｔ ｇｒａｎｕｌａｒ ｃｏｍｍｕｎｉｔｉｅｓ ａｒｅ ｐａｒｔｉｔｉｏｎｅｄ ｂｙ ｕｓｉｎｇ ｈｉｅｒａｒｃｈｉｃａｌ ｃｏｍｍｕｎｉｔｙ ｄｉｖｉｄｉｎｇ ａｌｇｏｒｉｔｈｍ （ ｓｕｃｈ ａｓ ＥＡＧＬＥ ｉｎ ｔｈｉｓ ｐａｐｅｒ）． Ｔｈｅｎ， ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅ ｓｐａｎｎｅｒｓ ｍｉｎｉｎｇ ａｌｇｏｒｉｔｈｍ ＭＧ＿ＭａｘＤ ｉｓ ｕｓｅｄ ｔｏ ｉｄｅｎｔｉｆｙｉｎｇ ｔｈｅ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅ ｓｐａｎｎｅｒｓ ｉｎ ｅａｃｈ ｇｒａｎｕｌａｒｉｔｙ． Ｆｉｎａｌｌｙ， ｕｓｉｎｇ ｔｈｅ ｍｅａｓｕｒｅｍｅｎｔ ｏｆ ｔｈｅ ｅｘｔｅｎｔ ｏｆ ｎｏｄｅ ｓｐａｎｎｉｎｇ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ ｔｏ ａｎａｌ⁃ ｙｓｉｓ ｔｈｅ ｅｆｆｅｃｔ ｏｆ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｕｎｄｅｒ ｄｉｆｆｅｒｅｎｔ ｇｒａｎｕｌａｒｉｔｙ ｔｈａｔ ｉｎｆｌｕｅｎｃｅ ｔｈｅ ｎｏｄｅ’ｓ ｅｘｔｅｎｔ ｔｏ ｓｐａｎ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ． Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｏｎ ｐｕｂｌｉｃ ｄａｔａ ａｎｄ ｒｅａｌ ｄａｔａ ｉｎｄｉｃａｔｅ ｔｈａｔ ｔｈｅ ｅｘｔｅｎｔ ｏｆ ｎｏｄｅｓ ｔｏ ｓｐａｎ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ ｎａｍｅｌｙ ｔｈｅ ｎｏｄｅ’ｓ ａｄｖａｎｔａｇｅｓ ｗｉｌｌ ｉｎｃｒｅａｓｅ ｗｉｔｈ ｔｈｅ ｇｒａｎｕｌａｒｉｔｙ ｇｅｔ ｔｈｉｎｎｅｒ． Ｋｅｙｗｏｒｄｓ：ｔｒｕｃｔｕｒａｌ ｈｏｌｅ； ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ；ｍｕｌｔｉ⁃ｇｒａｎｕｌａｒｉｔｙ； ｈｉｅｒａｒｃｈｉｃａｌ ｓｔｒｕｃｔｕｒｅ； ｃｏｍｍｕｎｉｔｙ ｄｉｖｉｓｉｏｎ； ｈｉ⁃ ｅｒａｒｃｈｉｃａｌ ｎｅｔｗｏｒｋｓ； ｎｅｔｗｏｒｋ ｓｔｒｕｃｔｕｒｅ； ｓｏｃｉａｌ ｎｅｔｗｏｒｋ ａｎａｌｙｓｉｓ 收稿日期：２０１６⁃０３⁃２０． 网络出版日期：２０１６⁃０５⁃１３． 基金项目：国家高技术研究发展计划项目（２０１５ＡＡ１２４１０２）；国家自然 科学基金项目（ ６１４０２００６、６１１７５０４６）；安徽省高等学校省级 自然科学研究项目（ＫＪ２０１３Ａ０１６）；安徽省自然科学基金项目 （１５０８０８５ＭＦ１１３）；教育部留学回国人员科研启动基金项目． 通信作者：赵姝．Ｅ⁃ｍａｉｌ：ｇｏｎｇｘｓ７＠ １６３．ｃｏｍ． 在信息化技术迅猛发展的今天，社会网络在工 作生活中发挥着越来越重要的作用。 网络中的信息 交流、资源交换已成为社会生活中不可缺少的重要 途径。 随着参与社会网络的个体增加，社会网络对 于人们的重要性也随之增加，使得对社会网络的研 究具有更深远的意义。 近年来，对于社会网络的性 质分析，逐渐从对网络整体结构分析，如发现网络的
·344 智能系统学报 第11卷 拓扑性质含有无标度、小世界特性和社团结构等，转 结构洞理论的基础上提出“广义结构洞”概念，并给 移到对网络中重要节点的分析，如结构洞)、意见 出基于谱图理论的启发式“广义结构洞”发现算法 领袖2]等。结构洞是网络中普遍存在的现象，在网 DGSH。Hu等[9]将结构洞理论扩展到有向模糊社 络中占据何种位置能够获益的想法已经得到了许多 交网络并提出单向模糊结构洞和双向模糊结构洞的 人的关注。个体或者团体中的中间人可以获得丰富 算法，分别计算行动者占据的单向和双向模糊结构 的信息并控制他们的网络关系，在网络中占据中心 洞个数。Lou和Tang2o)在假设网络社团结构已知 位置的主体可以获得丰厚的利益。结构洞在获 的情况下，基于两级信息流理论和最小割分别提出 取网络有效信息方面起着关键的作用，且发现网络 两个结构洞占据者的挖掘算法HIS和MaxD。 中的结构洞可以对网络结构进行优化和增强鲁棒 目前对于结构洞[21]的研究中，研究者发现社 性。结构洞理论作为网络结构分析的重要方法，在 团结构与结构洞的属性存在很大关系，并提出相应 不同领域和学科的研究中都获得了丰富的成 算法。如Lou和Tang20]假设社团结构已知的情况 果[3 下，提出两个结构洞挖掘算法HIS和MaxD。研究者 在结构洞研究的推进过程中，研究者发现结构 主要考虑单一粒度下的结构洞，然而网络的社团结 洞占据者在网络中可以获得竞争优势和网络收益， 构在不同粒度下的划分具有很大差异，且层次结 并提出不同的结构洞模型。Kleinberg等s)从战略 构)具有嵌套关系。社团划分粒度由粗到细时，社 和动态方面研究了结构洞理论，进一步扩充了伯特 团结构的规模和数量也随之变化，在粗粒度下的某 等研究者的工作。他们模拟了这样的过程，即当所 个社团，粒度变细时可能划分为多个社团。如中国 有个体都在竞争桥节点位置的时候，社会网络随着 的行政区划，将全国看作一个大网络，可从省、市、 时间是如何改变的。Buskens和Van9]使用博弈论 县、乡等不同大小的区域描述网络。省、市、县、乡等 方法来模拟具有结构洞的网络形成过程，认为节点 分别代表不同粒度下划分的社团，从不同粒度描述， A只有处在节点B和C中间时才能获益。Goyal和 则网络社团结构也会不同。网络的层次结构特性对 Vegatio提出网络形成的模型来研究社会网络中结 节点属性如重要性、中心性等具有重要影响。细粒 构洞的形成，并认为当节点A位于任意长的B-C路 度下的结构洞占据者在粗粒度下可能不再跨越结构 径上，且作为节点B和C的中介时，都将获得潜在 洞，或结构洞程度降低甚至丧失。 利益。这种模型将导致形成星形网络，然而，现实中 综上所述，本文在单粒度基础上，研究多粒度对 的大部分网络并不一定是星形拓扑结构。Brugge- 网络中结构洞占据者跨越结构洞程度的影响。本文 man等)考虑了生态位重叠导致的分散竞争对网 提出一种基于社团结构的多粒度结构洞发现方法 络中个体的结构自主性的影响，修正了伯特的模型。 MG_MaxD,首先使用分层社团划分算法得到不同粒 研究者通过对结构洞的性质进行分析，提出许 度下的社团结构：然后用结构洞发现方法获得不同 多基于网络结构和社团结构的结构洞度量指标。基 粒度下的结构洞占据者集合：最后，对结构洞占据者 于网络结构的度量主要考虑结构洞的优势，伯特提 的跨越结构洞程度的变化规律进行分析，发现结构 出了4个定量描述结构洞的度量指标1,21]，即网 洞占据者的结构洞程度即结构洞节点在社团间的优 络约束系数、网络有效规模、效率和等级度；Freeman 势会随着粒度的变细而增大。本文使用不同数据 提出介数中心性指标14；Newman等[提出局部聚 集，并进行多组对比实验，验证实验结果。 类系数：邓世果等16]提出一种基于基尼系数的结构 1结构洞理论及相关算法 洞测量方法，并讨论贡献度和结构洞程度之间的关 系：基于社团结构的度量主要考虑结构洞跨越不同 1.1结构洞理论 社团的属性，Rezvani等[)根据伯特定义中个体连 结构洞理论由美国社会学家罗纳德·博特于 接的社团数和个体的邻居节点数提出一种结构洞度 1992年在其撰写的《结构洞：竞争的社会结构》【川一 量指标。 书中首次提出的。所谓结构洞，即“社交网络中某 随着对结构洞的价值和意义继续深入研究，研 个或某些个体和有些个体发生直接联系，但与其他 究者提出多种结构洞发现算法，在不同结构和类型 个体不发生直接联系。无直接或关系间断的现象， 的复杂网络中准确发现结构洞占据者。Zhang等 从网络整体看好像网络结构中出现了洞穴。”简单 认为网络中很难存在单节点形成的结构洞，他们在 地说，结构洞是指两个关系人之间的非重复关系
拓扑性质含有无标度、小世界特性和社团结构等，转 移到对网络中重要节点的分析，如结构洞［１］ 、意见 领袖［２］等。 结构洞是网络中普遍存在的现象，在网 络中占据何种位置能够获益的想法已经得到了许多 人的关注。 个体或者团体中的中间人可以获得丰富 的信息并控制他们的网络关系，在网络中占据中心 位置的主体可以获得丰厚的利益［１］ 。 结构洞在获 取网络有效信息方面起着关键的作用，且发现网络 中的结构洞可以对网络结构进行优化和增强鲁棒 性。 结构洞理论作为网络结构分析的重要方法，在 不同 领 域 和 学 科 的 研 究 中 都 获 得 了 丰 富 的 成 果［３⁃７］ 。 在结构洞研究的推进过程中，研究者发现结构 洞占据者在网络中可以获得竞争优势和网络收益， 并提出不同的结构洞模型。 Ｋｌｅｉｎｂｅｒｇ 等［８］ 从战略 和动态方面研究了结构洞理论，进一步扩充了伯特 等研究者的工作。 他们模拟了这样的过程，即当所 有个体都在竞争桥节点位置的时候，社会网络随着 时间是如何改变的。 Ｂｕｓｋｅｎｓ 和 Ｖａｎ ［９］ 使用博弈论 方法来模拟具有结构洞的网络形成过程，认为节点 Ａ 只有处在节点 Ｂ 和 Ｃ 中间时才能获益。 Ｇｏｙａｌ 和 Ｖｅｇａ ［１０］ 提出网络形成的模型来研究社会网络中结 构洞的形成，并认为当节点 Ａ 位于任意长的 Ｂ⁃Ｃ 路 径上，且作为节点 Ｂ 和 Ｃ 的中介时，都将获得潜在 利益。 这种模型将导致形成星形网络，然而，现实中 的大部分网络并不一定是星形拓扑结构。 Ｂｒｕｇｇｅ⁃ ｍａｎ 等［１１］考虑了生态位重叠导致的分散竞争对网 络中个体的结构自主性的影响，修正了伯特的模型。 研究者通过对结构洞的性质进行分析，提出许 多基于网络结构和社团结构的结构洞度量指标。 基 于网络结构的度量主要考虑结构洞的优势，伯特提 出了 ４ 个定量描述结构洞的度量指标［１，１２⁃１３］ ，即网 络约束系数、网络有效规模、效率和等级度；Ｆｒｅｅｍａｎ 提出介数中心性指标［１４］ ；Ｎｅｗｍａｎ 等［１５］ 提出局部聚 类系数；邓世果等［１６］提出一种基于基尼系数的结构 洞测量方法，并讨论贡献度和结构洞程度之间的关 系；基于社团结构的度量主要考虑结构洞跨越不同 社团的属性，Ｒｅｚｖａｎｉ 等［１７］ 根据伯特定义中个体连 接的社团数和个体的邻居节点数提出一种结构洞度 量指标。 随着对结构洞的价值和意义继续深入研究，研 究者提出多种结构洞发现算法，在不同结构和类型 的复杂网络中准确发现结构洞占据者。 Ｚｈａｎｇ 等［１８］ 认为网络中很难存在单节点形成的结构洞，他们在 结构洞理论的基础上提出“广义结构洞”概念，并给 出基于谱图理论的启发式“广义结构洞”发现算法 ＤＧＳＨ。 Ｈｕ 等［１９］将结构洞理论扩展到有向模糊社 交网络并提出单向模糊结构洞和双向模糊结构洞的 算法，分别计算行动者占据的单向和双向模糊结构 洞个数。 Ｌｏｕ 和 Ｔａｎｇ ［２０］ 在假设网络社团结构已知 的情况下，基于两级信息流理论和最小割分别提出 两个结构洞占据者的挖掘算法 ＨＩＳ 和 ＭａｘＤ。 目前对于结构洞［２１⁃２２］ 的研究中，研究者发现社 团结构与结构洞的属性存在很大关系，并提出相应 算法。 如 Ｌｏｕ 和 Ｔａｎｇ ［２０］ 假设社团结构已知的情况 下，提出两个结构洞挖掘算法 ＨＩＳ 和 ＭａｘＤ。 研究者 主要考虑单一粒度下的结构洞，然而网络的社团结 构在不同粒度下的划分具有很大差异，且层次结 构［２３］具有嵌套关系。 社团划分粒度由粗到细时，社 团结构的规模和数量也随之变化，在粗粒度下的某 个社团，粒度变细时可能划分为多个社团。 如中国 的行政区划，将全国看作一个大网络，可从省、市、 县、乡等不同大小的区域描述网络。 省、市、县、乡等 分别代表不同粒度下划分的社团，从不同粒度描述， 则网络社团结构也会不同。 网络的层次结构特性对 节点属性如重要性、中心性等具有重要影响。 细粒 度下的结构洞占据者在粗粒度下可能不再跨越结构 洞，或结构洞程度降低甚至丧失。 综上所述，本文在单粒度基础上，研究多粒度对 网络中结构洞占据者跨越结构洞程度的影响。 本文 提出一种基于社团结构的多粒度结构洞发现方法 ＭＧ＿ＭａｘＤ，首先使用分层社团划分算法得到不同粒 度下的社团结构；然后用结构洞发现方法获得不同 粒度下的结构洞占据者集合；最后，对结构洞占据者 的跨越结构洞程度的变化规律进行分析，发现结构 洞占据者的结构洞程度即结构洞节点在社团间的优 势会随着粒度的变细而增大。 本文使用不同数据 集，并进行多组对比实验，验证实验结果。 １ 结构洞理论及相关算法 １．１ 结构洞理论 结构洞理论由美国社会学家罗纳德·博特于 １９９２ 年在其撰写的《结构洞：竞争的社会结构》 ［１］一 书中首次提出的。 所谓结构洞，即“社交网络中某 个或某些个体和有些个体发生直接联系，但与其他 个体不发生直接联系。 无直接或关系间断的现象， 从网络整体看好像网络结构中出现了洞穴。” 简单 地说，结构洞是指两个关系人之间的非重复关系。 ·３４４· 智 能 系 统 学 报 第 １１ 卷
第3期 赵姝，等：基于社团结构的多粒度结构洞占据者发现及分析 .345. 由于社交网络中存在着不直接或间接连接的关系， U:esC,和汇点E,=UsC:在诱导后的图G1V上 从而使拥有互补资源或信息的个体之间出现了空 计算最大流； 位，也可看做网络中的洞穴。结构洞是信息流动的 对每个节点v∈V添加通过其的流f(v): 缺口，跨越结构洞的个体可以获得不同个体之间存 3)选O(k)个具有最大f值的节点作候选者D: 在的异质性信息。如图1所示，网络由9个节点构 4)计算p”=arg min,eoMC(G\(VU{p}),C); 成，除了节点5以外，其他节点被分为两个社团，而 5)更新Vsa=VsHU{p°} 这两个社团内的节点只能通过节点5产生联系，若 MaxD算法的输入为网络G=(V,E)和社团结 没有节点5，则两侧社团之间就产生了间隙，形成了 构C={C},依据社团结构并结合最小割理论，最后 结构洞。显然，节点5占据了结构洞的位置。因此， 得到结构洞解集V。但现实网络中的社团结构存 可以通过找到类似节点5的结构洞占据者，获得网 在多粒度，本文主要研究多粒度对结构洞占据者跨 络中的异质性信息和资源。 越结构洞程度的影响。 1.3社团划分算法 本文所使用的社团划分方法为Shen等[2]提出 的能够同时探测出社团层次性和重叠性的算法EA GLE。通过凝聚的方法划分社团，研究对象为网络 中的极大团，通过极大团之间的不断凝聚来实现社 团划分。EAGLE算法分为2个步骤：1)生成网络 的树状图：2)在生成树上选择合适位置断开，得到 图1结构洞示例 相应的社团划分。为了评判社团划分结果的质量， Fig.1 Illustration of structural holes 该算法提出一种新的模块度指标如式(2)所示： 1.2基于社团结构的结构洞占据者发现算法 无权网络可以表示为G=(V,E),含有n个节 0六￡a] (2 Trec.ec00 点，m条边。其中V表示网络中节点的集合，E表示 式中O,是节点v所属社团的数目。通常选择在EQ 网络中边的集合。V={v1,2,…,n},E={e1,e2,…, 值最大的位置对生成树进行切割，进而得到最合理 em},社团结构为C={C1,C2,…,C}。 的社团结构。在EAGLE中，将算法应用于已找到 Lou和Tang20]认为跨越结构洞的个体在不同 的社团中去，得到一些规模更小、联系更紧密的子社 社团间的信息传播中发挥重要作用，结构洞占据者 团，就可得到在不同粒度下的社团结构，即层次化社 在社团间起到桥接作用，去除这些结构洞节点后，社 团结构。不同粒度下会影响网络的社团划分结果， 团间的联系将会最小化，他们根据这个思想并使用 如粗粒度下的某个社团在细粒度下可能被划分为多 最小割提出结构洞发现方法MaxD。结合最小割定 个社团，社团结构变化如图2和图3所示。 义，他们提出在去除结构洞结点后，网络G中C的 最小割将显著减小，即最小割的减少量在删除结点 后将会最大，目标函数如式(1)所示： Q(VsH,C)=MC(G,C)-MC(G\VsH,C),I VsH I=k 5 8 (1) 3 MaxD算法的具体流程如下所示。 12 算法1MaxD 输入网络G=(V,E),结构洞个数k,社团数 10) ⑩ 1,社团结构C={C:}。 输出Topk个结构洞占据者集合VH 14 1)初始化V知为空集； 2)当1Vs|<k时，循环给每个节点v∈V初始化 图2粗粒度下的社团结构 流量f()=0; Fig.2 Community structure in rough granularity 对每个非空SC{1,2,…,},利用源点Es=
由于社交网络中存在着不直接或间接连接的关系， 从而使拥有互补资源或信息的个体之间出现了空 位，也可看做网络中的洞穴。 结构洞是信息流动的 缺口，跨越结构洞的个体可以获得不同个体之间存 在的异质性信息。 如图 １ 所示，网络由 ９ 个节点构 成，除了节点 ５ 以外，其他节点被分为两个社团，而 这两个社团内的节点只能通过节点 ５ 产生联系，若 没有节点 ５，则两侧社团之间就产生了间隙，形成了 结构洞。 显然，节点 ５ 占据了结构洞的位置。 因此， 可以通过找到类似节点 ５ 的结构洞占据者，获得网 络中的异质性信息和资源。 图 １ 结构洞示例 Ｆｉｇ．１ Ｉｌｌｕｓｔｒａｔｉｏｎ ｏｆ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ １．２ 基于社团结构的结构洞占据者发现算法 无权网络可以表示为 Ｇ ＝ （Ｖ，Ｅ），含有 ｎ 个节 点，ｍ 条边。 其中 Ｖ 表示网络中节点的集合，Ｅ 表示 网络中边的集合。 Ｖ ＝ ｛ｖ１ ，ｖ２ ，…，ｖｎ ｝，Ｅ ＝ ｛ｅ１ ，ｅ２ ，…， ｅｍ ｝，社团结构为 Ｃ ＝ ｛Ｃ１ ，Ｃ２ ，…，Ｃｌ｝。 Ｌｏｕ 和 Ｔａｎｇ ［２０］ 认为跨越结构洞的个体在不同 社团间的信息传播中发挥重要作用，结构洞占据者 在社团间起到桥接作用，去除这些结构洞节点后，社 团间的联系将会最小化，他们根据这个思想并使用 最小割提出结构洞发现方法 ＭａｘＤ。 结合最小割定 义，他们提出在去除结构洞结点后，网络 Ｇ 中 Ｃ 的 最小割将显著减小，即最小割的减少量在删除结点 后将会最大，目标函数如式（１）所示： Ｑ（ＶＳＨ，Ｃ） ＝ ＭＣ（Ｇ，Ｃ） － ＭＣ（Ｇ＼ＶＳＨ，Ｃ）， ｜ ＶＳＨ ｜ ＝ ｋ （１） ＭａｘＤ 算法的具体流程如下所示。 算法 １ ＭａｘＤ 输入 网络 Ｇ ＝ （Ｖ，Ｅ），结构洞个数 ｋ，社团数 ｌ，社团结构 Ｃ ＝ ｛Ｃｉ｝。 输出 Ｔｏｐ ｋ 个结构洞占据者集合 ＶＳＨ 。 １）初始化 ＶＳＨ为空集； ２）当｜ ＶＳＨ ｜ ＜ｋ 时，循环给每个节点 ｖ∈Ｖ 初始化 流量 ｆ（ｖ）＝ ０； 对每个非空 Ｓ⊂｛１，２，…，ｌ｝，利用源点 ＥＳ ＝ ∪ｉ∈ＳＣｉ 和汇点 ＥＴ ＝ ∪ｉ∉ＳＣｉ 在诱导后的图 Ｇ ＼ ＶＳＨ上 计算最大流； 对每个节点 ｖ∈Ｖ 添加通过其的流 ｆ（ｖ）； ３） 选 Ｏ（ｋ）个具有最大 ｆ 值的节点作候选者 Ｄ； ４） 计算 ｐ ∗ ＝ａｒｇ ｍｉｎｐ∈ＤＭＣ（Ｇ＼（ＶＳＨ∪｛ｐ｝），Ｃ）； ５） 更新 ＶＳＨ ＝ ＶＳＨ∪｛ｐ ∗ ｝ ＭａｘＤ 算法的输入为网络 Ｇ ＝ （Ｖ，Ｅ） 和社团结 构 Ｃ ＝ ｛Ｃｉ｝，依据社团结构并结合最小割理论，最后 得到结构洞解集 ＶＳＨ 。 但现实网络中的社团结构存 在多粒度，本文主要研究多粒度对结构洞占据者跨 越结构洞程度的影响。 １．３ 社团划分算法 本文所使用的社团划分方法为 Ｓｈｅｎ 等［２４］ 提出 的能够同时探测出社团层次性和重叠性的算法 ＥＡ⁃ ＧＬＥ。 通过凝聚的方法划分社团，研究对象为网络 中的极大团，通过极大团之间的不断凝聚来实现社 团划分。 ＥＡＧＬＥ 算法分为 ２ 个步骤：１） 生成网络 的树状图；２） 在生成树上选择合适位置断开，得到 相应的社团划分。 为了评判社团划分结果的质量， 该算法提出一种新的模块度指标如式（２）所示： ＥＱ ＝ １ ２ｍ∑ｉ ｖ∈∑Ｃ，ｗ∈Ｃ １ ＯｖＯｗ Ａｖｗ － ｋｖ ｋｗ ２ｍ é ë ê ê ù û ú ú （２） 式中 Ｏｖ 是节点 ｖ 所属社团的数目。 通常选择在 ＥＱ 值最大的位置对生成树进行切割，进而得到最合理 的社团结构。 在 ＥＡＧＬＥ 中，将算法应用于已找到 的社团中去，得到一些规模更小、联系更紧密的子社 团，就可得到在不同粒度下的社团结构，即层次化社 团结构。 不同粒度下会影响网络的社团划分结果， 如粗粒度下的某个社团在细粒度下可能被划分为多 个社团，社团结构变化如图 ２ 和图 ３ 所示。 图 ２ 粗粒度下的社团结构 Ｆｉｇ．２ Ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｉｎ ｒｏｕｇｈ ｇｒａｎｕｌａｒｉｔｙ 第 ３ 期 赵姝，等：基于社团结构的多粒度结构洞占据者发现及分析 ·３４５·
.346. 智能系统学报 第11卷 (6 图G\上计算最大流： 7 对每个节点v∈V,对节点v添加通过其的 流f()。 2 (8 9 3)选择O(k)个具有最大f值的节点作为候选 ③ 者D。 4)对p∈D,即第h层网络的结构洞占据者候 4 2 10 选节点，计算：P%=arg min,enMC(G\(aU{p}), ⑩ C)。 ③ 14 5)更新H=U{P%}。 6)重复2)~5)，直到11=k。 7)重复2)~6)，直到求出前x层的结构洞占 图3细粒度下的社团结构 据者集合VH。 Fig.3 Community structure in fine granularity 社团结构是复杂网络最重要和最普遍的拓扑性 2 多粒度结构洞发现方法 质之一。在信息传播网中，同一社团内的信息传播 较为迅速，而社团间的信息传播较为缓慢。在分层 本文算法基于社团结构，主要思想为将多粒 网络中，社团划分粒度的变化将改变整个网络的社 度[5与社团划分结合，得到不同粒度下的社团结 团结构，跨越社团的结构洞占据者属性也会随之变 构，最后再根据不同粒度下的社团结构求出网络中 化。对分层网络中的结构洞占据者进行发现及分析 的结构洞占据者。为有效挖掘层次网络中的结构 可以帮助揭露多粒度网络中节点跨越结构洞程度， 洞，我们将MaxD模型[20]中的最小割思想引入到层 即不同粒度下结构洞节点在社团间信息传播和异质 次网络中，作为分层网络结构洞挖掘的理论依据。 性资源获取方面优势的变化，以及结构洞位置的变 在不同粒度的社团结构中，使用最大流算法，分析节 化情况。 点的最大流变化情况并根据最小割求出结构洞占据 在MG_MaxD方法中，使用EAGLE算法首先获 者。多粒度结构洞发现方法MG_MaxD的主要步 得最优模块度下的社团结构，然后在此社团结构下， 骤：1)使用分层社团发现算法对网络进行多粒度划 将网络细化得到较细粒度下的社团结构，重复此步 分，并得到不同粒度的社团划分结果：2)根据当前 骤直到获得前τ层的社团结构。根据获得的多粒度 层网络的社团结构，使用MaxD算法中的最大流和 社团结构，使用MG_MaxD算法获得网络G在不同 最小割求出结构洞占据者：3)重复第2)步，直到求 粒度下的前k个结构洞占据者。社团划分粒度越 出前r层的结构洞占据者集合。实验最后将分 细，则网络中的社团个数越多，且社团规模可能减 析不同粒度下结构洞占据者的结构洞程度变化。 小，即粗粒度下的社团在细粒度下可能被划分为多 MG_MaxD算法的输入为网络G、结构洞个数k、分层 个社团，使社团结构产生很大变化。 数r;输出为前r层结构洞占据者集合V出。 MG_MaxD算法具体步骤如下。 3实验设置与结果分析 算法2层次结构网络结构洞发现方法MG_ 3.1数据及衡量指标 MaxD 本文所使用的数据包括公用数据和实例数据。 输入网络G=(V,E),结构洞个数k,分层数r 公用数据为在清华大学ArnetMiner(研究者社会网 输出前r层结构洞占据者集合V' 络分析与挖掘系统)系统下载的数据Topic 131和 1)使用分层社团发现算法将网络G分层，并获 Topic145,是公用的合著网络数据集。以论文中的 得前r层的网络社团结构C={C}(1≤h≤r,1≤i≤ 作者作为网络的节点，作者间的合著关系作为边。 nw},式中C表示第h层的第i个社团，n4表示第h 实例数据为CCF推荐国际学术会议A类的ICML 层的社团个数，h越大，表示社团划分粒度越细。 会议从2005年到2014年共10年出版的论文，统计 2)对C(1≤h≤r)层网络 论文标题和文章作者信息，对数据进行处理，若两个 给每个节点v∈V初始化流量f()=0; 作者出现在同一个文章里，则这两个作者之间有一 对每个非空SC{1,2,…,},1为当前层网络 条边，依据这些信息最后构建为一个合著网络，将数 社团个数： 据集表示为ICML_10。 利用源点Es=U:e4C和汇点Er=U:.4C,在 实验数据具体信息如表1所示
图 ３ 细粒度下的社团结构 Ｆｉｇ．３ Ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｉｎ ｆｉｎｅ ｇｒａｎｕｌａｒｉｔｙ ２ 多粒度结构洞发现方法 本文算法基于社团结构，主要思想为将多粒 度［２５⁃２６］与社团划分结合，得到不同粒度下的社团结 构，最后再根据不同粒度下的社团结构求出网络中 的结构洞占据者。 为有效挖掘层次网络中的结构 洞，我们将 ＭａｘＤ 模型［２０］ 中的最小割思想引入到层 次网络中，作为分层网络结构洞挖掘的理论依据。 在不同粒度的社团结构中，使用最大流算法，分析节 点的最大流变化情况并根据最小割求出结构洞占据 者。 多粒度结构洞发现方法 ＭＧ＿ＭａｘＤ 的主要步 骤：１）使用分层社团发现算法对网络进行多粒度划 分，并得到不同粒度的社团划分结果；２） 根据当前 层网络的社团结构，使用 ＭａｘＤ 算法中的最大流和 最小割求出结构洞占据者；３）重复第 ２）步，直到求 出前 ｒ 层的结构洞占据者集合 Ｖ ｒ ＳＨ 。 实验最后将分 析不同粒度下结构洞占据者的结构洞程度变化。 ＭＧ＿ＭａｘＤ 算法的输入为网络 Ｇ、结构洞个数 ｋ、分层 数 ｒ； 输 出 为 前 ｒ 层 结 构 洞 占 据 者 集 合 Ｖ ｒ ＳＨ 。 ＭＧ＿ＭａｘＤ算法具体步骤如下。 算法 ２ 层次结构网络结构洞发现方法 ＭＧ＿ ＭａｘＤ 输入 网络 Ｇ ＝ （Ｖ，Ｅ），结构洞个数 ｋ，分层数 ｒ 输出 前 ｒ 层结构洞占据者集合 Ｖ ｒ ＳＨ １）使用分层社团发现算法将网络 Ｇ 分层，并获 得前 ｒ 层的网络社团结构 Ｃ ＝ ｛Ｃ ｈ ｉ ｝（１≤ｈ≤ｒ，１≤ｉ≤ ｎｈ ｝，式中 Ｃ ｈ ｉ 表示第 ｈ 层的第 ｉ 个社团，ｎｈ 表示第 ｈ 层的社团个数，ｈ 越大，表示社团划分粒度越细。 ２） 对 Ｃ ｈ （１≤ｈ≤ｒ）层网络 给每个节点 ｖ∈Ｖ 初始化流量 ｆ（ｖ）＝ ０； 对每个非空 Ｓ ｈ⊂｛１，２，…，ｌ｝，ｌ 为当前层网络 社团个数； 利用源点 ＥＳ ＝∪ｉ∈Ｓ ｈＣ ｈ ｉ 和汇点 ＥＴ ＝ ∪ｉ∉Ｓ ｈＣ ｈ ｉ ，在 图 Ｇ ＼Ｖ ｈ ＳＨ上计算最大流； 对每个节点 ｖ ∈ Ｖ， 对节点 ｖ 添加通过其的 流 ｆ（ｖ）。 ３） 选择 Ｏ（ｋ）个具有最大 ｆ 值的节点作为候选 者 Ｄ。 ４） 对 ｐ ｈ∈Ｄ，即第 ｈ 层网络的结构洞占据者候 选节点，计算：ｐ ∗ ｈ ＝ ａｒｇ ｍｉｎｐ ｈ∈ＤＭＣ（Ｇ ＼ （Ｖ ｈ ＳＨ∪｛ｐ ｈ ｝）， Ｃ ｈ ）。 ５） 更新 Ｖ ｈ ＳＨ ＝ Ｖ ｈ ＳＨ∪｛ｐ ∗ ｈ ｝。 ６） 重复 ２） ～ ５），直到｜ Ｖ ｈ ＳＨ ｜ ＝ ｋ。 ７） 重复 ２） ～ ６），直到求出前 ｒ 层的结构洞占 据者集合 Ｖ ｒ ＳＨ 。 社团结构是复杂网络最重要和最普遍的拓扑性 质之一。 在信息传播网中，同一社团内的信息传播 较为迅速，而社团间的信息传播较为缓慢。 在分层 网络中，社团划分粒度的变化将改变整个网络的社 团结构，跨越社团的结构洞占据者属性也会随之变 化。 对分层网络中的结构洞占据者进行发现及分析 可以帮助揭露多粒度网络中节点跨越结构洞程度， 即不同粒度下结构洞节点在社团间信息传播和异质 性资源获取方面优势的变化，以及结构洞位置的变 化情况。 在 ＭＧ＿ＭａｘＤ 方法中，使用 ＥＡＧＬＥ 算法首先获 得最优模块度下的社团结构，然后在此社团结构下， 将网络细化得到较细粒度下的社团结构，重复此步 骤直到获得前 ｒ 层的社团结构。 根据获得的多粒度 社团结构，使用 ＭＧ＿ＭａｘＤ 算法获得网络 Ｇ 在不同 粒度下的前 ｋ 个结构洞占据者。 社团划分粒度越 细，则网络中的社团个数越多，且社团规模可能减 小，即粗粒度下的社团在细粒度下可能被划分为多 个社团，使社团结构产生很大变化。 ３ 实验设置与结果分析 ３．１ 数据及衡量指标 本文所使用的数据包括公用数据和实例数据。 公用数据为在清华大学 ＡｒｎｅｔＭｉｎｅｒ（研究者社会网 络分析与挖掘系统） 系统下载的数据 Ｔｏｐｉｃ １３１ 和 Ｔｏｐｉｃ １４５，是公用的合著网络数据集。 以论文中的 作者作为网络的节点，作者间的合著关系作为边。 实例数据为 ＣＣＦ 推荐国际学术会议 Ａ 类的 ＩＣＭＬ 会议从 ２００５ 年到 ２０１４ 年共 １０ 年出版的论文，统计 论文标题和文章作者信息，对数据进行处理，若两个 作者出现在同一个文章里，则这两个作者之间有一 条边，依据这些信息最后构建为一个合著网络，将数 据集表示为 ＩＣＭＬ＿１０。 实验数据具体信息如表 １ 所示。 ·３４６· 智 能 系 统 学 报 第 １１ 卷
第3期 赵蛛，等：基于社团结构的多粒度结构洞占据者发现及分析 ·347. 表1数据集信息 但细粒度下的解集质量总是保持最佳。Topic 131 Table 1 Dataset 数据集上结构洞解集的P(S)指标结果对比如图4 数据集 节点数 边数 所示。 Topic 131 554 1238 0.30 Topic 145 671 2237 0.25 ICML 10 2856 5809 0.20 下面对本文用到的结构洞的度量指标进行 C 0.15 介绍。 0.10 Rezvani等[叮根据伯特定义中的个体连接的社 0 团数和个体的邻居节点数，提出一种新度量指标。 0.0 2468101214161820 伯特提出，一个好的结构洞占据者应该连接许多社 top 团，但为了更有影响力，它连接的社团数和它的邻居 图4 Topic 131在MG_MaxD算法下不同粒度结构洞 节点数之比应该要大。Rezvani等在网络社团结构 解集的质量(top20) 已知的情况下，根据这个定义提出一个p(S)指标 Fig.4 Performance of structural holes for MG MaxD (本文中称为结构洞跨越程度指标)来衡量结构洞 on Topic 131 (top 20) 占据者。给定图G=(V,E),假设S为找到的结构洞 Topic145数据集在不同粒度下的社团划分个 占据者集合，那么这个解集的质量如式(3)所示： 数为1C,I=50、1C2I=130、IC31=251,分别发现不 com(v) 同粒度下的前20个结构洞占据者。Topic145数据 集上结构洞解集的p(S)指标结果对比如图5所示。 p(S)= 五deg() (3) s 0.40 6-C 式中：com(v)表示节点v连接的社团数，deg(v)代 0.35 表节点v的度，|S|代表解集S中节点的个数。 0.30 P(S)指标值越大，说明节点跨越结构洞的程度越 高，则结构洞节点可以更有效地进行社团间的信息 传播，获得不同社团间的异质性资源，更好地发挥结 0.15 构洞作用。这个指标可以在一定程度上定量地衡量 0.10 606—09 结构洞节点的重要性。将网络进行多粒度社团划分 0.05246810214161820 top 后，从社团角度看，网络结构不断改变，且社团规模 和社团数量将发生很大变化。由于p(S)指标将社 图5 Topic145在MG_MaxD算法下不同粒度结构洞 解集的质量(top20) 团因素考虑在内，所以选择p(S)作为结构洞解集的 Fig.5 Performance of structural holes for MGMaxD 度量指标。 on Topic 145 top 20) 3.2实验结果及分析 ICML10数据集在不同粒度下的社团划分个数 3.2.1MG_MaxD实验结果 为1C,1=342、1C21=565、1C31=806,分别发现不同 考虑到数据集的规模和网络结构的合理性，分 粒度下的前20个结构洞占据者，图6显示ICML10 别求得3种粒度的层次社团结构，由粗到细分别表 数据集在不同粒度下找到的结构洞占据者的结构洞 示为C,、C2和C,其中C,是模块度最优时的网络 程度变化情况，随着社团划分粒度的变细，结构洞占 划分，C2和C,是对C,进行逐次细化得到的社团结 据者解集的p(S)值变大。 构。使用MG_MaxD方法发现不同粒度下的前20 通过图4~6可以发现，细粒度下结构洞占据者 个结构洞占据者，根据ρ(S)指标计算不同粒度下的 解集的质量总是优于较粗粒度下的结构洞占据者。 节点跨越结构洞程度，最后分析不同粒度下结构洞 在Topic131、Topic145和ICML_10数据集上，当社 解集的质量。使用EAGLE算法在不同粒度下进行 团划分的粒度最粗时，由于此时的网络拓扑结构较 社团划分，得到Topic131数据集在不同粒度下的社 为简单，社团数较少，而发现的结构洞占据者解集的 团划分个数为1C,1=32,1C21=97,1C31=164。 效果并不好，说明此时个体的结构洞作用并不明显， 从图4可以看出，社团划分粒度越细，结构洞解 即结构洞程度较低：而当粒度变细时，网络拓扑较为 集中的节点跨越结构洞的程度越大，且随着个数的 复杂，社团数较多，此时个体跨越的社团相对较多， 增加，同一粒度下结构洞解集的质量也在不断下降， 可以更好得获得异质性信息和不同资源，且能更好
表 １ 数据集信息 Ｔａｂｌｅ １ Ｄａｔａｓｅｔ 数据集 节点数 边数 Ｔｏｐｉｃ １３１ ５５４ １ ２３８ Ｔｏｐｉｃ １４５ ６７１ ２ ２３７ ＩＣＭＬ＿１０ ２ ８５６ ５ ８０９ 下面对本文用到的结构洞的度量指标进行 介绍。 Ｒｅｚｖａｎｉ 等［１７］ 根据伯特定义中的个体连接的社 团数和个体的邻居节点数，提出一种新度量指标。 伯特提出，一个好的结构洞占据者应该连接许多社 团，但为了更有影响力，它连接的社团数和它的邻居 节点数之比应该要大。 Ｒｅｚｖａｎｉ 等在网络社团结构 已知的情况下，根据这个定义提出一个 ρ（ Ｓ） 指标 （本文中称为结构洞跨越程度指标）来衡量结构洞 占据者。 给定图 Ｇ ＝ （Ｖ，Ｅ），假设 Ｓ 为找到的结构洞 占据者集合，那么这个解集的质量如式（３）所示： ρ（Ｓ） ＝ ∑ｖ∈Ｓ ｃｏｍ（ｖ） ｄｅｇ（ｖ） Ｓ （３） 式中：ｃｏｍ（ｖ）表示节点 ｖ 连接的社团数，ｄｅｇ（ ｖ） 代 表节点 ｖ 的度， Ｓ 代 表 解 集 Ｓ 中 节 点 的 个 数。 ρ（Ｓ）指标值越大，说明节点跨越结构洞的程度越 高，则结构洞节点可以更有效地进行社团间的信息 传播，获得不同社团间的异质性资源，更好地发挥结 构洞作用。 这个指标可以在一定程度上定量地衡量 结构洞节点的重要性。 将网络进行多粒度社团划分 后，从社团角度看，网络结构不断改变，且社团规模 和社团数量将发生很大变化。 由于 ρ（ Ｓ）指标将社 团因素考虑在内，所以选择 ρ（Ｓ）作为结构洞解集的 度量指标。 ３．２ 实验结果及分析 ３．２．１ ＭＧ＿ＭａｘＤ 实验结果 考虑到数据集的规模和网络结构的合理性，分 别求得 ３ 种粒度的层次社团结构，由粗到细分别表 示为 Ｃ１ 、Ｃ２ 和 Ｃ３ ，其中 Ｃ１ 是模块度最优时的网络 划分，Ｃ２ 和 Ｃ３ 是对 Ｃ１ 进行逐次细化得到的社团结 构。 使用 ＭＧ＿ＭａｘＤ 方法发现不同粒度下的前 ２０ 个结构洞占据者，根据 ρ（Ｓ）指标计算不同粒度下的 节点跨越结构洞程度，最后分析不同粒度下结构洞 解集的质量。 使用 ＥＡＧＬＥ 算法在不同粒度下进行 社团划分，得到 Ｔｏｐｉｃ １３１ 数据集在不同粒度下的社 团划分个数为｜ Ｃ１ ｜ ＝ ３２， ｜ Ｃ２ ｜ ＝ ９７， ｜ Ｃ３ ｜ ＝ １６４。 从图 ４ 可以看出，社团划分粒度越细，结构洞解 集中的节点跨越结构洞的程度越大，且随着个数的 增加，同一粒度下结构洞解集的质量也在不断下降， 但细粒度下的解集质量总是保持最佳。 Ｔｏｐｉｃ １３１ 数据集上结构洞解集的 ρ（ Ｓ）指标结果对比如图 ４ 所示。 图 ４ Ｔｏｐｉｃ １３１ 在 ＭＧ＿ＭａｘＤ 算法下不同粒度结构洞 解集的质量（ｔｏｐ ２０） Ｆｉｇ．４ Ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ ｆｏｒ ＭＧ＿ＭａｘＤ ｏｎ Ｔｏｐｉｃ １３１ （ｔｏｐ ２０） Ｔｏｐｉｃ １４５ 数据集在不同粒度下的社团划分个 数为｜ Ｃ１ ｜ ＝ ５０ 、 ｜ Ｃ２ ｜ ＝ １３０、 ｜ Ｃ３ ｜ ＝ ２５１，分别发现不 同粒度下的前 ２０ 个结构洞占据者。 Ｔｏｐｉｃ １４５ 数据 集上结构洞解集的 ρ（Ｓ）指标结果对比如图 ５ 所示。 图 ５ Ｔｏｐｉｃ １４５ 在 ＭＧ＿ＭａｘＤ 算法下不同粒度结构洞 解集的质量（ｔｏｐ ２０） Ｆｉｇ．５ Ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ ｆｏｒ ＭＧ＿ＭａｘＤ ｏｎ Ｔｏｐｉｃ １４５ （ｔｏｐ ２０） ＩＣＭＬ＿１０ 数据集在不同粒度下的社团划分个数 为｜ Ｃ１ ｜ ＝ ３４２、 ｜ Ｃ２ ｜ ＝ ５６５、 ｜ Ｃ３ ｜ ＝ ８０６，分别发现不同 粒度下的前 ２０ 个结构洞占据者，图 ６ 显示 ＩＣＭＬ＿１０ 数据集在不同粒度下找到的结构洞占据者的结构洞 程度变化情况，随着社团划分粒度的变细，结构洞占 据者解集的 ρ（Ｓ）值变大。 通过图 ４～６ 可以发现，细粒度下结构洞占据者 解集的质量总是优于较粗粒度下的结构洞占据者。 在 Ｔｏｐｉｃ １３１、Ｔｏｐｉｃ １４５ 和 ＩＣＭＬ＿１０ 数据集上，当社 团划分的粒度最粗时，由于此时的网络拓扑结构较 为简单，社团数较少，而发现的结构洞占据者解集的 效果并不好，说明此时个体的结构洞作用并不明显， 即结构洞程度较低；而当粒度变细时，网络拓扑较为 复杂，社团数较多，此时个体跨越的社团相对较多， 可以更好得获得异质性信息和不同资源，且能更好 第 ３ 期 赵姝，等：基于社团结构的多粒度结构洞占据者发现及分析 ·３４７·
.348. 智能系统学报 第11卷 的发挥结构洞作用，即细粒度下的结构洞占据者跨 解集的ρ(S)越低，则节点跨越的结构洞的可能性越 越结构洞的程度较大。对应于实际情况，将公司看 低。说明不同粒度下的网络层次结构对节点的结构 作网络，而公司里还有许多不同部门，部门分为许多 洞程度会产生重要影响。 工作小组等等。粗粒度下将公司的部门作为节点， 0.50 细粒度下可能将个体作为节点，这对应于不同粒度 0.45 的层次结构，而个体在网络中的属性关系和结构洞 0.401 程度会不断变化。 0.50 令0351 0.45 0.30 0.40 0.25 0.35 三0.30 0.20 0.25 2468101214161820 0.20 top 0.15 0 图8 Topic145在HS算法下不同粒度结构洞解集的 0.10 0.05246810214161820 质量(top20) Fig.8 Performance of structural holes for HIS on Top- top k ic 145 top 20) 图6ICML10在MG_MaxD算法下不同粒度结构洞 解集的质量(top20) 0.45 0.40t Fig.6 Performance of structural holes for MG_MaxD 0.35 on ICML_10 (top 20) 0.30 3.2.2HS对比实验结果 2025 为了验证上面结论的可靠性，本文使用文献 0.20 [20]中的HIS算法进行对比试验，分别在Topic131、 0.15 0—00 Topic145和ICML_10数据集上进行实验。当网络划 0.10 0.05 分粒度变化时，网络社团结构也会发生变化，由于 2468101214161820 HS算法中节点的重要性初始化是相对于社团的，所 topk 以HS算法对社团结构的变化会更加敏感。使用 图9ICML10在HⅡS算法下不同粒度结构洞解集的 HS算法进行对比可以有效地验证上面结论。统计 质量(top20) HIS算法在不同粒度下发现的结构洞，并使用p(S)指 Fig.9 Performance of structural holes for HIS on IC- 标对结构洞解集进行衡量，实验结果如图7~9所示。 ML 10 (top 20) 0.70 3.2.3模块度及社团数对结构洞的影响 0.60 0.50 -C 本文在T131、T145数据集上，考虑多粒度下社 团划分质量和结构洞解集质量之间的关系，即网络 0.40 模块度和p(S)变化情况。选取MG_MaxD和HIS 0.30 算法在两个数据集，和5种社团划分结果的模块度 0.20 0.10g 日8 下发现的前20个结构洞占据者，实验结果如图10 2468101214161820 和图11所示。从图10和图11可以看出，模块度越 大说明社团划分结果越好，但结构洞解集质量不断 图7 Topic131在HⅡS算法下不同粒度结构洞解集的 质量(top20) 降低。图10显示在T131数据集中，当模块度为 Fig.7 Performance of structural holes for HIS on Top- 0.468时，此时社团划分质量最差，但MG_MaxD和 ic131(top20)】 HS的结构洞解集的质量最佳，而随着模块度提高， 图7~9显示在不同数据集上，使用HS算法找 这两个算法的解集质量也随之下降；图11显示在 到的前20个结构洞解集的ρ(S)指标变化情况，可 T145数据集中也具有相同规律，且发现当模块度为 以发现随着社团划分粒度的变粗，HS算法找到的 0.324时，MG_MaxD和HIS的结构洞解集的质量最 结构洞解集的质量也随之下降。粒度越粗，结构洞 差。通过两组实验对比，可以发现模块度与结构洞
的发挥结构洞作用，即细粒度下的结构洞占据者跨 越结构洞的程度较大。 对应于实际情况，将公司看 作网络，而公司里还有许多不同部门，部门分为许多 工作小组等等。 粗粒度下将公司的部门作为节点， 细粒度下可能将个体作为节点，这对应于不同粒度 的层次结构，而个体在网络中的属性关系和结构洞 程度会不断变化。 图 ６ ＩＣＭＬ＿１０ 在 ＭＧ＿ＭａｘＤ 算法下不同粒度结构洞 解集的质量（ｔｏｐ ２０） Ｆｉｇ．６ Ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ ｆｏｒ ＭＧ＿ＭａｘＤ ｏｎ ＩＣＭＬ＿１０ （ｔｏｐ ２０） ３．２．２ ＨＩＳ 对比实验结果 为了验证上面结论的可靠性，本文使用文献 ［２０］中的 ＨＩＳ 算法进行对比试验，分别在 Ｔｏｐｉｃ １３１、 Ｔｏｐｉｃ １４５ 和 ＩＣＭＬ＿１０ 数据集上进行实验。 当网络划 分粒度变化时，网络社团结构也会发生变化，由于 ＨＩＳ 算法中节点的重要性初始化是相对于社团的，所 以 ＨＩＳ 算法对社团结构的变化会更加敏感。 使用 ＨＩＳ 算法进行对比可以有效地验证上面结论。 统计 ＨＩＳ 算法在不同粒度下发现的结构洞，并使用 ρ（Ｓ）指 标对结构洞解集进行衡量，实验结果如图７～９所示。 图 ７ Ｔｏｐｉｃ １３１ 在 ＨＩＳ 算法下不同粒度结构洞解集的 质量（ｔｏｐ ２０） Ｆｉｇ．７ Ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ ｆｏｒ ＨＩＳ ｏｎ Ｔｏｐ⁃ ｉｃ １３１ （ｔｏｐ ２０） 图 ７～９ 显示在不同数据集上，使用 ＨＩＳ 算法找 到的前 ２０ 个结构洞解集的 ρ（Ｓ）指标变化情况，可 以发现随着社团划分粒度的变粗，ＨＩＳ 算法找到的 结构洞解集的质量也随之下降。 粒度越粗，结构洞 解集的 ρ（Ｓ）越低，则节点跨越的结构洞的可能性越 低。 说明不同粒度下的网络层次结构对节点的结构 洞程度会产生重要影响。 图 ８ Ｔｏｐｉｃ １４５ 在 ＨＩＳ 算法下不同粒度结构洞解集的 质量（ｔｏｐ ２０） Ｆｉｇ．８ Ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ ｆｏｒ ＨＩＳ ｏｎ Ｔｏｐ⁃ ｉｃ １４５ （ｔｏｐ ２０） 图 ９ ＩＣＭＬ＿１０ 在 ＨＩＳ 算法下不同粒度结构洞解集的 质量（ｔｏｐ ２０） Ｆｉｇ．９ Ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ ｆｏｒ ＨＩＳ ｏｎ ＩＣ⁃ ＭＬ＿１０ （ｔｏｐ ２０） ３．２．３ 模块度及社团数对结构洞的影响 本文在 Ｔ１３１、Ｔ１４５ 数据集上，考虑多粒度下社 团划分质量和结构洞解集质量之间的关系，即网络 模块度和 ρ（ Ｓ） 变化情况。 选取 ＭＧ＿ＭａｘＤ 和 ＨＩＳ 算法在两个数据集，和 ５ 种社团划分结果的模块度 下发现的前 ２０ 个结构洞占据者，实验结果如图 １０ 和图 １１ 所示。 从图 １０ 和图 １１ 可以看出，模块度越 大说明社团划分结果越好，但结构洞解集质量不断 降低。 图 １０ 显示在 Ｔ１３１ 数据集中，当模块度为 ０．４６８时，此时社团划分质量最差，但 ＭＧ＿ＭａｘＤ 和 ＨＩＳ 的结构洞解集的质量最佳，而随着模块度提高， 这两个算法的解集质量也随之下降；图 １１ 显示在 Ｔ１４５ 数据集中也具有相同规律，且发现当模块度为 ０．３２４ 时，ＭＧ＿ＭａｘＤ 和 ＨＩＳ 的结构洞解集的质量最 差。 通过两组实验对比，可以发现模块度与结构洞 ·３４８· 智 能 系 统 学 报 第 １１ 卷
第3期 赵蛛，等：基于社团结构的多粒度结构洞占据者发现及分析 .349. 解集的质量存在一定关系，在寻找网络中的结构洞 洞的程度变大。 时应结合社团划分结果的模块度因素，并选择合适 的社团划分粒度。 0.20 0.191 子跳cwman 0.6℉ 0.18 -e-HIS 0.17 0.5 -MG MaxD 0.16 0.4 0.15 903 0.141 0.13 0.2 0.12246801214161820 0.1 topk 0.468 0.5670.5910.6000.657 模块度 图12T131数据集在单粒度下对比结果(top20) Fig.12 Comparison of results of T131 in single granu- 图10T131数据集多粒度下不同算法对比结果(top20) larity Fig.10 Comparison of results of different algorithms on T131 in multi-granularity top 20) 0.22 --Blondel 0.21 -Fast_Newman 0.20 0.8甲 -HIS 0.19 0.7 MG MaxD 令018 0.6 0.17 0.5 0.16 0.4 0.15 0.3 0.14 0.2 2468101214161820 top 0.1 0.260 0.3240.346 0.4880.514 图13T145数据集在单粒度下的对比结果(top20) 模块度 Fig.13 Comparison of results of T13lin single granu- larity top 20) 图11T145数据集多粒度下不同算法对比结果(top20) Fig.11 Comparison of results of different algorithms 通过对比MG_MaxD算法和HIS算法在不同数 on T145 in multi-granularity top 20) 据集上的实验结果，发现在同一网络下，不同的社团 为验证单一粒度下社团数对结构洞解集质量的 划分粒度会影响结构洞占据者的选取。所以在获取 影响，本文使用Fast-Newman算法[)和Blondel算 网络中的结构洞占据者时，由于不同社团划分粒度 法[28]分别对T131数据集和T145数据集的原网络 将影响节点跨越结构洞的程度，可以综合网络的多 进行社团划分，并获得单一粒度下相应的社团结构， 粒度社团划分结构，找到合适的粒度，发现更加准确 使用MG_MaxD算法获得单一粒度下的结构洞占据 的结构洞占据者。 者，最后对结构洞解集的质量进行分析。T131数据 4 结束语 集在Blondel和Fast-Newman算法下分别得到25和 30个社团，T145数据集在Blondel和Fast-Newman 本文主要研究了多粒度对结构洞占据者跨越结 算法下分别得到16和30个社团。实验结果如图 构洞程度的影响，从社交网络的结构洞理论出发，考 12和图13所示。 虑到不同社团划分粒度将影响结构洞占据者的选 图12和图13显示，由于单粒度下T131和 取，在多粒度社团划分的基础上，提出从多粒度角度 T145数据集在两种社团划分算法下得到的社团数 分析结构洞占据者的方法。在不同数据集上进行实 相差不大，得到的结构洞解集质量也很相近。可以 验，对结果进行分析，发现不同粒度的社团划分将影 发现在单一粒度下，社团数量对结构洞占据者跨越 响节点跨越结构洞的程度。通过多组对比实验发 结构洞程度存在一定影响，从整体上看，当社团数增 现，在细粒度上，结构洞解集中的节点的结构洞程度 加时，结构洞解集质量也随之提高，即节点跨越结构 较高，而在粗粒度上，由于将整个网络粗化，减弱了
解集的质量存在一定关系，在寻找网络中的结构洞 时应结合社团划分结果的模块度因素，并选择合适 的社团划分粒度。 图 １０ Ｔ１３１ 数据集多粒度下不同算法对比结果（ｔｏｐ ２０） Ｆｉｇ．１０ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｒｅｓｕｌｔｓ ｏｆ ｄｉｆｆｅｒｅｎｔ ａｌｇｏｒｉｔｈｍｓ ｏｎ Ｔ１３１ ｉｎ ｍｕｌｔｉ⁃ｇｒａｎｕｌａｒｉｔｙ （ｔｏｐ ２０） 图 １１ Ｔ１４５ 数据集多粒度下不同算法对比结果（ｔｏｐ ２０） Ｆｉｇ．１１ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｒｅｓｕｌｔｓ ｏｆ ｄｉｆｆｅｒｅｎｔ ａｌｇｏｒｉｔｈｍｓ ｏｎ Ｔ１４５ ｉｎ ｍｕｌｔｉ⁃ｇｒａｎｕｌａｒｉｔｙ （ｔｏｐ ２０） 为验证单一粒度下社团数对结构洞解集质量的 影响，本文使用 Ｆａｓｔ⁃Ｎｅｗｍａｎ 算法［２７］ 和 Ｂｌｏｎｄｅｌ 算 法［２８］分别对 Ｔ１３１ 数据集和 Ｔ１４５ 数据集的原网络 进行社团划分，并获得单一粒度下相应的社团结构， 使用 ＭＧ＿ＭａｘＤ 算法获得单一粒度下的结构洞占据 者，最后对结构洞解集的质量进行分析。 Ｔ１３１ 数据 集在 Ｂｌｏｎｄｅｌ 和 Ｆａｓｔ⁃Ｎｅｗｍａｎ 算法下分别得到 ２５ 和 ３０ 个社团，Ｔ１４５ 数据集在 Ｂｌｏｎｄｅｌ 和 Ｆａｓｔ－Ｎｅｗｍａｎ 算法下分别得到 １６ 和 ３０ 个社团。 实验结果如图 １２ 和图 １３ 所示。 图 １２ 和图 １３ 显示， 由于单粒度下 Ｔ１３１ 和 Ｔ１４５ 数据集在两种社团划分算法下得到的社团数 相差不大，得到的结构洞解集质量也很相近。 可以 发现在单一粒度下，社团数量对结构洞占据者跨越 结构洞程度存在一定影响，从整体上看，当社团数增 加时，结构洞解集质量也随之提高，即节点跨越结构 洞的程度变大。 图 １２ Ｔ１３１ 数据集在单粒度下对比结果（ｔｏｐ ２０） Ｆｉｇ．１２ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｒｅｓｕｌｔｓ ｏｆ Ｔ１３１ ｉｎ ｓｉｎｇｌｅ ｇｒａｎｕ⁃ ｌａｒｉｔｙ 图 １３ Ｔ１４５ 数据集在单粒度下的对比结果（ｔｏｐ ２０） Ｆｉｇ．１３ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｒｅｓｕｌｔｓ ｏｆ Ｔ１３１ｉｎ ｓｉｎｇｌｅ ｇｒａｎｕ⁃ ｌａｒｉｔｙ （ｔｏｐ ２０） 通过对比 ＭＧ＿ＭａｘＤ 算法和 ＨＩＳ 算法在不同数 据集上的实验结果，发现在同一网络下，不同的社团 划分粒度会影响结构洞占据者的选取。 所以在获取 网络中的结构洞占据者时，由于不同社团划分粒度 将影响节点跨越结构洞的程度，可以综合网络的多 粒度社团划分结构，找到合适的粒度，发现更加准确 的结构洞占据者。 ４ 结束语 本文主要研究了多粒度对结构洞占据者跨越结 构洞程度的影响，从社交网络的结构洞理论出发，考 虑到不同社团划分粒度将影响结构洞占据者的选 取，在多粒度社团划分的基础上，提出从多粒度角度 分析结构洞占据者的方法。 在不同数据集上进行实 验，对结果进行分析，发现不同粒度的社团划分将影 响节点跨越结构洞的程度。 通过多组对比实验发 现，在细粒度上，结构洞解集中的节点的结构洞程度 较高，而在粗粒度上，由于将整个网络粗化，减弱了 第 ３ 期 赵姝，等：基于社团结构的多粒度结构洞占据者发现及分析 ·３４９·
.350. 智能系统学报 第11卷 节点的结构洞效果。探讨多粒度下的结构洞占据者 ofs0 ciology,2008,114(2):371-407. 的结构洞程度的变化情况，可以帮助研究不同粒度 [10]GOYAL S,VEGA-REDONDO F.Structural holes in social 下网络结构的优化、网络资源的有效获取和网络信 networks[J].Journal of economic theory,2007,137(1): 460-492. 息传播的有效控制。本文在结构洞理论和商空间模 [11]BRUGGEMAN J,CARNABUCI G,VERMEULEN I.A 型的基础上，对多粒度网络社团的结构洞进行初步 note on structural holes theory and niche overlap[J].So- 研究，发现不同粒度对节点的结构洞程度具有重要 cial networks,2003,25(1):97-101. 影响，且分析了模块度与结构洞占据者跨越结构洞 [12]BURT R S.Structural holes and good ideas1[J].American 程度之间的关系。根据结构洞跨越程度指标，结构 journal of sociology,2004,110(2):349-399. 洞解集质量随着社团数的增加而提高，然而社团数 [13]BURT R S.Le capital social,les trous structuraux entre- 越多，社团结构却不一定最优，所以需要权衡社团划 preneur[J].Revue francaise de sociologie,1995,36(4): 分粒度和结构洞跨越程度指标找到最优的结构洞占 599-628 据者，这是未来研究的主要工作。 [14]FREEMAN L C.A set of measures of centrality based on betweenness[J].Sociometry,1977,40(1):35-41. 参考文献： [15]NEWMAN M E J,WATTS D J,STROGATZ S H.Random graph models of social networks[J].Proceedings of the na- [1]BURT R S.Structural holes:The social structure of compe- tional academy of sciences of the united states of America, tition[M]//SWEDBERG R.Explorations in economic soci- 2002,99(3 Suppl.1):2566-2572. ology.New York,USA:Russell Sage Foundations,1993. [16]邓世果，吴干华，杨会杰.基于基尼系数的网络结构洞 [2]MA Ning,LIU Yijun,RUYA Tian,et al.Recognition of 测量[J].上海理工大学学报，2011,33(5)：452-456. online opinion leaders based on social network analysis DENG Shiguo,WU Ganhua,YANG Huijie.Gini-coeffi- [M]//HUANG Runhe,GHORBANI AA,PASI G,et al. cient-based measurement of structural holes[J].Journal of Active media technology.Berlin Heidelberg:Springer, university of shanghai for science and technology,2011, 2012:483-492. 33(5)：452-456. [3]Y0O J,KIM W.The effect of structural holes on the corpo- [17]REZVANI M,LIANG Weifa,Xu Wenzheng,et al.Identi- rate performance and strategic alliances network in pharma- fying top-k structural hole spanners in large-scale social ceutical industry[].International proceedings of economics networks[C]//Proceedings of the 24th ACM international development and research,2013,67(5):20-24. on conference on information and knowledge management. [4]CAI Penghua,ZHAO Hai,LIU Hong,et al.Research and Melbourne,Australia,2015:263-272. analysis of structural hole and matching coefficient[J]. [18]ZHANG Ende,WANG Guoren,GAO Kening,et al.Gen- Journal of software engineering and applications,2010,3 eralized structural holes finding algorithm by bisection in (11):1080-1087. social communities [C]//Proceedings of the 2012 6th in- [5]TAN YONG,MOOKERJEE V S,SINGH P V.Social cap- ternational conference on genetic and evolutionary compu- ital,structural holes and team composition:collaborative ting.Washington,DC,USA,2012:276-279. networks of the open source software community[C]//Pro- [19]HU Renjie,ZHANG Guangyu.Structural holes in directed ceedings of the international conference on information sys- fuzzy social networks[J].Journal of applied mathematics, tems.Montreal,Quebec,Canada,2007:155. 2014,2014：452063. [6]SHIPILOV A V,LI S X.Can you have your cake and eat it [20]LOU Tiancheng,TANG Jie.Mining structural hole span- too?Structural holes'influence on status accumulation and ners through information diffusion in social networks[C]// market performance in collaborative networks J.Adminis- Proceedings of the 22nd international conference on World trative science quarterly,2008,53(1):73-108. Wide Web.New York,NY,USA,2013:825-836. [7]RODAN S.Structural holes and managerial performance:i- [21]韩忠明，吴杨，谭旭升，等.面向结构洞的复杂网络关 dentifying the underlying mechanisms[J].Social networks, 键节点排序[J].物理学报，2015,64(5)：058902. 2010,32(3):168-179. HAN Zhongming,WU Yang,TAN Xusheng,et al.Rank- [8]KLEINBERG J.Strategic network formation with structural ing key nodes in complex networks by considering structur- holes[C]//Proceedings of the 9th ACM conference on elec- al holes[J].Acta physica sinica,2015,64(5):058902. tronic commerce.New York,USA,2008:284-293. [22]苏晓萍，宋玉蓉.利用邻域“结构洞”寻找社会网络中 9]BUSKENS V.VAN DE RIJT A.Dynamics of networks if 最具影响力节点[J].物理学报，2015,64(2)：020101. everyone strives for structural holes1[J].American journal SU Xiaoping,SONG Yurong.Leveraging neighborhood
节点的结构洞效果。 探讨多粒度下的结构洞占据者 的结构洞程度的变化情况，可以帮助研究不同粒度 下网络结构的优化、网络资源的有效获取和网络信 息传播的有效控制。 本文在结构洞理论和商空间模 型的基础上，对多粒度网络社团的结构洞进行初步 研究，发现不同粒度对节点的结构洞程度具有重要 影响，且分析了模块度与结构洞占据者跨越结构洞 程度之间的关系。 根据结构洞跨越程度指标，结构 洞解集质量随着社团数的增加而提高，然而社团数 越多，社团结构却不一定最优，所以需要权衡社团划 分粒度和结构洞跨越程度指标找到最优的结构洞占 据者，这是未来研究的主要工作。 参考文献： ［１］ＢＵＲＴ Ｒ Ｓ． Ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ： Ｔｈｅ ｓｏｃｉａｌ ｓｔｒｕｃｔｕｒｅ ｏｆ ｃｏｍｐｅ⁃ ｔｉｔｉｏｎ［Ｍ］ ／ ／ ＳＷＥＤＢＥＲＧ Ｒ． Ｅｘｐｌｏｒａｔｉｏｎｓ ｉｎ ｅｃｏｎｏｍｉｃ ｓｏｃｉ⁃ ｏｌｏｇｙ． Ｎｅｗ Ｙｏｒｋ， ＵＳＡ： Ｒｕｓｓｅｌｌ Ｓａｇｅ Ｆｏｕｎｄａｔｉｏｎｓ， １９９３． ［２］ＭＡ Ｎｉｎｇ， ＬＩＵ Ｙｉｊｕｎ， ＲＵＹＡ Ｔｉａｎ， ｅｔ ａｌ． Ｒｅｃｏｇｎｉｔｉｏｎ ｏｆ ｏｎｌｉｎｅ ｏｐｉｎｉｏｎ ｌｅａｄｅｒｓ ｂａｓｅｄ ｏｎ ｓｏｃｉａｌ ｎｅｔｗｏｒｋ ａｎａｌｙｓｉｓ ［Ｍ］ ／ ／ ＨＵＡＮＧ Ｒｕｎｈｅ， ＧＨＯＲＢＡＮＩ Ａ Ａ， ＰＡＳＩ Ｇ， ｅｔ ａｌ． Ａｃｔｉｖｅ ｍｅｄｉａ ｔｅｃｈｎｏｌｏｇｙ． Ｂｅｒｌｉｎ Ｈｅｉｄｅｌｂｅｒｇ： Ｓｐｒｉｎｇｅｒ， ２０１２： ４８３⁃４９２． ［３］ＹＯＯ Ｊ， ＫＩＭ Ｗ． Ｔｈｅ ｅｆｆｅｃｔ ｏｆ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ ｏｎ ｔｈｅ ｃｏｒｐｏ⁃ ｒａｔｅ ｐｅｒｆｏｒｍａｎｃｅ ａｎｄ ｓｔｒａｔｅｇｉｃ ａｌｌｉａｎｃｅｓ ｎｅｔｗｏｒｋ ｉｎ ｐｈａｒｍａ⁃ ｃｅｕｔｉｃａｌ ｉｎｄｕｓｔｒｙ［Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｅｃｏｎｏｍｉｃｓ ｄｅｖｅｌｏｐｍｅｎｔ ａｎｄ ｒｅｓｅａｒｃｈ， ２０１３， ６７（５）： ２０⁃２４． ［４］ＣＡＩ Ｐｅｎｇｈｕａ， ＺＨＡＯ Ｈａｉ， ＬＩＵ Ｈｏｎｇ， ｅｔ ａｌ． Ｒｅｓｅａｒｃｈ ａｎｄ ａｎａｌｙｓｉｓ ｏｆ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅ ａｎｄ ｍａｔｃｈｉｎｇ ｃｏｅｆｆｉｃｉｅｎｔ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ ｓｏｆｔｗａｒｅ ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ， ２０１０， ３ （１１）： １０８０⁃１０８７． ［５］ＴＡＮ ＹＯＮＧ， ＭＯＯＫＥＲＪＥＥ Ｖ Ｓ， ＳＩＮＧＨ Ｐ Ｖ． Ｓｏｃｉａｌ ｃａｐ⁃ ｉｔａｌ， ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ ａｎｄ ｔｅａｍ ｃｏｍｐｏｓｉｔｉｏｎ： ｃｏｌｌａｂｏｒａｔｉｖｅ ｎｅｔｗｏｒｋｓ ｏｆ ｔｈｅ ｏｐｅｎ ｓｏｕｒｃｅ ｓｏｆｔｗａｒｅ ｃｏｍｍｕｎｉｔｙ［Ｃ］ ／ ／ Ｐｒｏ⁃ ｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ｉｎｔｅｒｎａｔｉｏｎａｌ ｃｏｎｆｅｒｅｎｃｅ ｏｎ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓ⁃ ｔｅｍｓ． Ｍｏｎｔｒｅａｌ， Ｑｕｅｂｅｃ， Ｃａｎａｄａ， ２００７： １５５． ［６］ＳＨＩＰＩＬＯＶ Ａ Ｖ， ＬＩ Ｓ Ｘ． Ｃａｎ ｙｏｕ ｈａｖｅ ｙｏｕｒ ｃａｋｅ ａｎｄ ｅａｔ ｉｔ ｔｏｏ？ Ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ＇ ｉｎｆｌｕｅｎｃｅ ｏｎ ｓｔａｔｕｓ ａｃｃｕｍｕｌａｔｉｏｎ ａｎｄ ｍａｒｋｅｔ ｐｅｒｆｏｒｍａｎｃｅ ｉｎ ｃｏｌｌａｂｏｒａｔｉｖｅ ｎｅｔｗｏｒｋｓ［ Ｊ］． Ａｄｍｉｎｉｓ⁃ ｔｒａｔｉｖｅ ｓｃｉｅｎｃｅ ｑｕａｒｔｅｒｌｙ， ２００８， ５３（１）： ７３⁃１０８． ［７］ＲＯＤＡＮ Ｓ． Ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ ａｎｄ ｍａｎａｇｅｒｉａｌ ｐｅｒｆｏｒｍａｎｃｅ： ｉ⁃ ｄｅｎｔｉｆｙｉｎｇ ｔｈｅ ｕｎｄｅｒｌｙｉｎｇ ｍｅｃｈａｎｉｓｍｓ［ Ｊ］． Ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ， ２０１０， ３２（３）： １６８⁃１７９． ［８］ ＫＬＥＩＮＢＥＲＧ Ｊ． Ｓｔｒａｔｅｇｉｃ ｎｅｔｗｏｒｋ ｆｏｒｍａｔｉｏｎ ｗｉｔｈ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ９ｔｈ ＡＣＭ ｃｏｎｆｅｒｅｎｃｅ ｏｎ ｅｌｅｃ⁃ ｔｒｏｎｉｃ ｃｏｍｍｅｒｃｅ． Ｎｅｗ Ｙｏｒｋ， ＵＳＡ， ２００８： ２８４⁃２９３． ［９］ ＢＵＳＫＥＮＳ Ｖ， ＶＡＮ ＤＥ ＲＩＪＴ Ａ． Ｄｙｎａｍｉｃｓ ｏｆ ｎｅｔｗｏｒｋｓ ｉｆ ｅｖｅｒｙｏｎｅ ｓｔｒｉｖｅｓ ｆｏｒ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ１［ Ｊ］． Ａｍｅｒｉｃａｎ ｊｏｕｒｎａｌ ｏｆ ｓｏｃｉｏｌｏｇｙ， ２００８， １１４（２）： ３７１⁃４０７． ［１０］ＧＯＹＡＬ Ｓ， ＶＥＧＡ⁃ＲＥＤＯＮＤＯ Ｆ． Ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ ｉｎ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｅｃｏｎｏｍｉｃ ｔｈｅｏｒｙ， ２００７， １３７（１）： ４６０⁃４９２． ［１１］ ＢＲＵＧＧＥＭＡＮ Ｊ， ＣＡＲＮＡＢＵＣＩ Ｇ， ＶＥＲＭＥＵＬＥＮ Ｉ． Ａ ｎｏｔｅ ｏｎ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ ｔｈｅｏｒｙ ａｎｄ ｎｉｃｈｅ ｏｖｅｒｌａｐ［ Ｊ］． Ｓｏ⁃ ｃｉａｌ ｎｅｔｗｏｒｋｓ， ２００３， ２５（１）： ９７⁃１０１． ［１２］ＢＵＲＴ Ｒ Ｓ． Ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ ａｎｄ ｇｏｏｄ ｉｄｅａｓ１［Ｊ］． Ａｍｅｒｉｃａｎ ｊｏｕｒｎａｌ ｏｆ ｓｏｃｉｏｌｏｇｙ， ２００４， １１０（２）： ３４９⁃３９９． ［１３］ＢＵＲＴ Ｒ Ｓ． Ｌｅ ｃａｐｉｔａｌ ｓｏｃｉａｌ， ｌｅｓ ｔｒｏｕｓ ｓｔｒｕｃｔｕｒａｕｘ ｅｎｔｒｅ⁃ ｐｒｅｎｅｕｒ［Ｊ］． Ｒｅｖｕｅ ｆｒａｎｃａｉｓｅ ｄｅ ｓｏｃｉｏｌｏｇｉｅ， １９９５， ３６（４）： ５９９⁃６２８． ［１４］ＦＲＥＥＭＡＮ Ｌ Ｃ． Ａ ｓｅｔ ｏｆ ｍｅａｓｕｒｅｓ ｏｆ ｃｅｎｔｒａｌｉｔｙ ｂａｓｅｄ ｏｎ ｂｅｔｗｅｅｎｎｅｓｓ［Ｊ］． Ｓｏｃｉｏｍｅｔｒｙ， １９７７， ４０（１）： ３５⁃４１． ［１５］ＮＥＷＭＡＮ Ｍ Ｅ Ｊ， ＷＡＴＴＳ Ｄ Ｊ， ＳＴＲＯＧＡＴＺ Ｓ Ｈ． Ｒａｎｄｏｍ ｇｒａｐｈ ｍｏｄｅｌｓ ｏｆ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ｎａ⁃ ｔｉｏｎａｌ ａｃａｄｅｍｙ ｏｆ ｓｃｉｅｎｃｅｓ ｏｆ ｔｈｅ ｕｎｉｔｅｄ ｓｔａｔｅｓ ｏｆ Ａｍｅｒｉｃａ， ２００２， ９９（３ Ｓｕｐｐｌ． １）： ２５６６⁃２５７２． ［１６］邓世果， 吴干华， 杨会杰． 基于基尼系数的网络结构洞 测量［Ｊ］． 上海理工大学学报， ２０１１， ３３（５）： ４５２⁃４５６． ＤＥＮＧ Ｓｈｉｇｕｏ， ＷＵ Ｇａｎｈｕａ， ＹＡＮＧ Ｈｕｉｊｉｅ． Ｇｉｎｉ⁃ｃｏｅｆｆｉ⁃ ｃｉｅｎｔ⁃ｂａｓｅｄ ｍｅａｓｕｒｅｍｅｎｔ ｏｆ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｕｎｉｖｅｒｓｉｔｙ ｏｆ ｓｈａｎｇｈａｉ ｆｏｒ ｓｃｉｅｎｃｅ ａｎｄ ｔｅｃｈｎｏｌｏｇｙ， ２０１１， ３３（５）： ４５２⁃４５６． ［１７］ＲＥＺＶＡＮＩ Ｍ， ＬＩＡＮＧ Ｗｅｉｆａ， Ｘｕ Ｗｅｎｚｈｅｎｇ， ｅｔ ａｌ． Ｉｄｅｎｔｉ⁃ ｆｙｉｎｇ ｔｏｐ⁃ｋ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅ ｓｐａｎｎｅｒｓ ｉｎ ｌａｒｇｅ⁃ｓｃａｌｅ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２４ｔｈ ＡＣＭ ｉｎｔｅｒｎａｔｉｏｎａｌ ｏｎ ｃｏｎｆｅｒｅｎｃｅ ｏｎ ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ ｋｎｏｗｌｅｄｇｅ ｍａｎａｇｅｍｅｎｔ． Ｍｅｌｂｏｕｒｎｅ， Ａｕｓｔｒａｌｉａ， ２０１５： ２６３⁃２７２． ［１８］ＺＨＡＮＧ Ｅｎｄｅ， ＷＡＮＧ Ｇｕｏｒｅｎ， ＧＡＯ Ｋｅｎｉｎｇ， ｅｔ ａｌ． Ｇｅｎ⁃ ｅｒａｌｉｚｅｄ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ ｆｉｎｄｉｎｇ ａｌｇｏｒｉｔｈｍ ｂｙ ｂｉｓｅｃｔｉｏｎ ｉｎ ｓｏｃｉａｌ ｃｏｍｍｕｎｉｔｉｅｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２０１２ ６ｔｈ ｉｎ⁃ ｔｅｒｎａｔｉｏｎａｌ ｃｏｎｆｅｒｅｎｃｅ ｏｎ ｇｅｎｅｔｉｃ ａｎｄ ｅｖｏｌｕｔｉｏｎａｒｙ ｃｏｍｐｕ⁃ ｔｉｎｇ． Ｗａｓｈｉｎｇｔｏｎ， ＤＣ， ＵＳＡ， ２０１２： ２７６⁃２７９． ［１９］ＨＵ Ｒｅｎｊｉｅ， ＺＨＡＮＧ Ｇｕａｎｇｙｕ． Ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ ｉｎ ｄｉｒｅｃｔｅｄ ｆｕｚｚｙ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ａｐｐｌｉｅｄ ｍａｔｈｅｍａｔｉｃｓ， ２０１４， ２０１４： ４５２０６３． ［２０］ＬＯＵ Ｔｉａｎｃｈｅｎｇ， ＴＡＮＧ Ｊｉｅ． Ｍｉｎｉｎｇ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅ ｓｐａｎ⁃ ｎｅｒｓ ｔｈｒｏｕｇｈ ｉｎｆｏｒｍａｔｉｏｎ ｄｉｆｆｕｓｉｏｎ ｉｎ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２２ｎｄ ｉｎｔｅｒｎａｔｉｏｎａｌ ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ． Ｎｅｗ Ｙｏｒｋ， ＮＹ， ＵＳＡ， ２０１３： ８２５⁃８３６． ［２１］韩忠明， 吴杨， 谭旭升， 等． 面向结构洞的复杂网络关 键节点排序［Ｊ］． 物理学报， ２０１５， ６４（５）： ０５８９０２． ＨＡＮ Ｚｈｏｎｇｍｉｎｇ， ＷＵ Ｙａｎｇ， ＴＡＮ Ｘｕｓｈｅｎｇ， ｅｔ ａｌ． Ｒａｎｋ⁃ ｉｎｇ ｋｅｙ ｎｏｄｅｓ ｉｎ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ ｂｙ ｃｏｎｓｉｄｅｒｉｎｇ ｓｔｒｕｃｔｕｒ⁃ ａｌ ｈｏｌｅｓ［Ｊ］． Ａｃｔａ ｐｈｙｓｉｃａ ｓｉｎｉｃａ， ２０１５， ６４（５）： ０５８９０２． ［２２］苏晓萍， 宋玉蓉． 利用邻域“结构洞”寻找社会网络中 最具影响力节点［Ｊ］． 物理学报， ２０１５， ６４（２）： ０２０１０１． ＳＵ Ｘｉａｏｐｉｎｇ， ＳＯＮＧ Ｙｕｒｏｎｇ． Ｌｅｖｅｒａｇｉｎｇ ｎｅｉｇｈｂｏｒｈｏｏｄ ·３５０· 智 能 系 统 学 报 第 １１ 卷
第3期 赵妹，等：基于社团结构的多粒度结构洞占据者发现及分析 ·351· "structural holes"to identifying key spreaders in social 2008,30(2):155-168 networks[J].Acta physica sinica,2015,64(2):020101. 作者简介： [23]CHEN Fengjiao,LI Kan.Detecting hierarchical structure 赵妹.女，1979年生，教授，主要研 of community members in social networks[J].Knowledge- 究方向为机器学习、社交网络、智能计 based systems,2015,87:3-15. 算。主持国家自然科学基金、省部级项 [24]SHEN Huawei,CHENG Xueqi,CAI Kai,et al.Detect o- 目等多项。已授权专利1项，获软件著 verlapping and hierarchical community structure in net- 作权3项，发表学术论文20余篇。 works[J.Physica a:statistical mechanics and its applica- 赵晖，男，1992年生，硕士研究生， tions,2009,388(24):5045-5056. 主要研究方向为社交网络。 [25]JIANG Feng,CHEN Yuming.Outlier detection based on granular computing and rough set theory[J].Applied intel- ligence,2015,42(2):303-322. [26]QIAN Jiangbo,ZHU Qiang,CHEN Huahui.Multi-granu- larity locality-sensitive bloom filter[J].IEEE transactions on computers,.2015,64(12):3500-3514. 陈洁，女，1982年生，博士研究生， [27]NEWMAN M E J.Fast algorithm for detecting community 主要研究方向为智能计算。 structure in networks J].Physical review E,2004,69 (6):066133. [28]BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al.Fast unfolding of communities in large networks[J]. Journal of statistical mechanics:theory and experiment, 2016年EEE协同建模与仿真国际会议 5th IEEE Track on Collaborative Modeling Simulation CoMetS16) Modeling and Simulation (M&S)is increasingly becoming a central activity in the design of new systems and in the analysis of exist- ing systems because it enables designers and researchers to investigate systems behaviour through virtual representations. For this reason,M&S is gaining a primary role in many industrial and research fields,such as space,critical infrastructures,manu- facturing,emergency management,biomedical systems and sustainable future.However,as the complexity of the investigated systems in- creases and the type of investigations widens,the cost of M&S activities increases because of the more complex models and of the commu- nications among a wider number and variety of M&S stakeholders (e.g.,sub-domain experts,simulator users,simulator engineers and fi- nal system users). To address the increasing costs of M&S activities,collaborative technologies must be introduced to support these activities by foste- ring the sharing and reuse of models,by facilitating the communications among M&S stakeholders,and more generally by integrating processes,tools and platforms. The CoMetS track aims to foster innovative research contributions that address collaboration issues in the field of M&S and vice ver- sa,i.e.,contributions that use M&S methodologies and tools to address the design of collaborative environments.A combination of both is- sues in the same venue will further contribute to the understanding of the underlying mechanisms that can affect the quality of the service delivered by collaborative environments for M&S. The CoMetS track is held under the aegis of the WETICE 2016 conference,the 25th IEEE International Conference on Enabling Technologies:Infrastructure for Collaborative Enterprises,which will be held in Paris (France)from June 13th to June 16th,2016. Website:http://www.sel.uniroma2.it/comets16/
“ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ” ｔｏ ｉｄｅｎｔｉｆｙｉｎｇ ｋｅｙ ｓｐｒｅａｄｅｒｓ ｉｎ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ［Ｊ］． Ａｃｔａ ｐｈｙｓｉｃａ ｓｉｎｉｃａ， ２０１５， ６４（２）： ０２０１０１． ［２３］ ＣＨＥＮ Ｆｅｎｇｊｉａｏ， ＬＩ Ｋａｎ． Ｄｅｔｅｃｔｉｎｇ ｈｉｅｒａｒｃｈｉｃａｌ ｓｔｒｕｃｔｕｒｅ ｏｆ ｃｏｍｍｕｎｉｔｙ ｍｅｍｂｅｒｓ ｉｎ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ［ Ｊ］． Ｋｎｏｗｌｅｄｇｅ⁃ ｂａｓｅｄ ｓｙｓｔｅｍｓ， ２０１５， ８７： ３⁃１５． ［２４］ＳＨＥＮ Ｈｕａｗｅｉ， ＣＨＥＮＧ Ｘｕｅｑｉ， ＣＡＩ Ｋａｉ， ｅｔ ａｌ． Ｄｅｔｅｃｔ ｏ⁃ ｖｅｒｌａｐｐｉｎｇ ａｎｄ ｈｉｅｒａｒｃｈｉｃａｌ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｉｎ ｎｅｔ⁃ ｗｏｒｋｓ［Ｊ］． Ｐｈｙｓｉｃａ ａ： ｓｔａｔｉｓｔｉｃａｌ ｍｅｃｈａｎｉｃｓ ａｎｄ ｉｔｓ ａｐｐｌｉｃａ⁃ ｔｉｏｎｓ， ２００９， ３８８（２４）： ５０４５⁃５０５６． ［２５］ ＪＩＡＮＧ Ｆｅｎｇ， ＣＨＥＮ Ｙｕｍｉｎｇ． Ｏｕｔｌｉｅｒ ｄｅｔｅｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｇｒａｎｕｌａｒ ｃｏｍｐｕｔｉｎｇ ａｎｄ ｒｏｕｇｈ ｓｅｔ ｔｈｅｏｒｙ［Ｊ］． Ａｐｐｌｉｅｄ ｉｎｔｅｌ⁃ ｌｉｇｅｎｃｅ， ２０１５， ４２（２）： ３０３⁃３２２． ［２６］ＱＩＡＮ Ｊｉａｎｇｂｏ， ＺＨＵ Ｑｉａｎｇ， ＣＨＥＮ Ｈｕａｈｕｉ． Ｍｕｌｔｉ⁃ｇｒａｎｕ⁃ ｌａｒｉｔｙ ｌｏｃａｌｉｔｙ⁃ｓｅｎｓｉｔｉｖｅ ｂｌｏｏｍ ｆｉｌｔｅｒ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｃｏｍｐｕｔｅｒｓ， ２０１５， ６４（１２）： ３５００⁃３５１４． ［２７］ＮＥＷＭＡＮ Ｍ Ｅ Ｊ． Ｆａｓｔ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｄｅｔｅｃｔｉｎｇ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｉｎ ｎｅｔｗｏｒｋｓ ［ Ｊ］． Ｐｈｙｓｉｃａｌ ｒｅｖｉｅｗ Ｅ， ２００４， ６９ （６）： ０６６１３３． ［２８］ＢＬＯＮＤＥＬ Ｖ Ｄ， ＧＵＩＬＬＡＵＭＥ Ｊ Ｌ， ＬＡＭＢＩＯＴＴＥ Ｒ， ｅｔ ａｌ． Ｆａｓｔ ｕｎｆｏｌｄｉｎｇ ｏｆ ｃｏｍｍｕｎｉｔｉｅｓ ｉｎ ｌａｒｇｅ ｎｅｔｗｏｒｋｓ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｓｔａｔｉｓｔｉｃａｌ ｍｅｃｈａｎｉｃｓ： ｔｈｅｏｒｙ ａｎｄ ｅｘｐｅｒｉｍｅｎｔ， ２００８， ３０（２）： １５５⁃１６８． 作者简介： 赵姝，女，１９７９ 年生，教授，主要研 究方向为机器学习、社交网络、智能计 算。 主持国家自然科学基金、省部级项 目等多项。 已授权专利 １ 项，获软件著 作权 ３ 项，发表学术论文 ２０ 余篇。 赵晖，男，１９９２ 年生，硕士研究生， 主要研究方向为社交网络。 陈洁，女，１９８２ 年生，博士研究生， 主要研究方向为智能计算。 ２０１６ 年 ＩＥＥＥ 协同建模与仿真国际会议 ５ｔｈ ＩＥＥＥ Ｔｒａｃｋ ｏｎ Ｃｏｌｌａｂｏｒａｔｉｖｅ Ｍｏｄｅｌｉｎｇ ＆ Ｓｉｍｕｌａｔｉｏｎ （ＣｏＭｅｔＳ＇１６） Ｍｏｄｅｌｉｎｇ ａｎｄ Ｓｉｍｕｌａｔｉｏｎ （Ｍ＆Ｓ） ｉｓ ｉｎｃｒｅａｓｉｎｇｌｙ ｂｅｃｏｍｉｎｇ ａ ｃｅｎｔｒａｌ ａｃｔｉｖｉｔｙ ｉｎ ｔｈｅ ｄｅｓｉｇｎ ｏｆ ｎｅｗ ｓｙｓｔｅｍｓ ａｎｄ ｉｎ ｔｈｅ ａｎａｌｙｓｉｓ ｏｆ ｅｘｉｓｔ⁃ ｉｎｇ ｓｙｓｔｅｍｓ ｂｅｃａｕｓｅ ｉｔ ｅｎａｂｌｅｓ ｄｅｓｉｇｎｅｒｓ ａｎｄ ｒｅｓｅａｒｃｈｅｒｓ ｔｏ ｉｎｖｅｓｔｉｇａｔｅ ｓｙｓｔｅｍｓ ｂｅｈａｖｉｏｕｒ ｔｈｒｏｕｇｈ ｖｉｒｔｕａｌ ｒｅｐｒｅｓｅｎｔａｔｉｏｎｓ． Ｆｏｒ ｔｈｉｓ ｒｅａｓｏｎ， Ｍ＆Ｓ ｉｓ ｇａｉｎｉｎｇ ａ ｐｒｉｍａｒｙ ｒｏｌｅ ｉｎ ｍａｎｙ ｉｎｄｕｓｔｒｉａｌ ａｎｄ ｒｅｓｅａｒｃｈ ｆｉｅｌｄｓ， ｓｕｃｈ ａｓ ｓｐａｃｅ， ｃｒｉｔｉｃａｌ ｉｎｆｒａｓｔｒｕｃｔｕｒｅｓ， ｍａｎｕ⁃ ｆａｃｔｕｒｉｎｇ， ｅｍｅｒｇｅｎｃｙ ｍａｎａｇｅｍｅｎｔ， ｂｉｏｍｅｄｉｃａｌ ｓｙｓｔｅｍｓ ａｎｄ ｓｕｓｔａｉｎａｂｌｅ ｆｕｔｕｒｅ． Ｈｏｗｅｖｅｒ， ａｓ ｔｈｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｔｈｅ ｉｎｖｅｓｔｉｇａｔｅｄ ｓｙｓｔｅｍｓ ｉｎ⁃ ｃｒｅａｓｅｓ ａｎｄ ｔｈｅ ｔｙｐｅ ｏｆ ｉｎｖｅｓｔｉｇａｔｉｏｎｓ ｗｉｄｅｎｓ， ｔｈｅ ｃｏｓｔ ｏｆ Ｍ＆Ｓ ａｃｔｉｖｉｔｉｅｓ ｉｎｃｒｅａｓｅｓ ｂｅｃａｕｓｅ ｏｆ ｔｈｅ ｍｏｒｅ ｃｏｍｐｌｅｘ ｍｏｄｅｌｓ ａｎｄ ｏｆ ｔｈｅ ｃｏｍｍｕ⁃ ｎｉｃａｔｉｏｎｓ ａｍｏｎｇ ａ ｗｉｄｅｒ ｎｕｍｂｅｒ ａｎｄ ｖａｒｉｅｔｙ ｏｆ Ｍ＆Ｓ ｓｔａｋｅｈｏｌｄｅｒｓ （ｅ．ｇ．， ｓｕｂ－ｄｏｍａｉｎ ｅｘｐｅｒｔｓ， ｓｉｍｕｌａｔｏｒ ｕｓｅｒｓ， ｓｉｍｕｌａｔｏｒ ｅｎｇｉｎｅｅｒｓ ａｎｄ ｆｉ⁃ ｎａｌ ｓｙｓｔｅｍ ｕｓｅｒｓ）． Ｔｏ ａｄｄｒｅｓｓ ｔｈｅ ｉｎｃｒｅａｓｉｎｇ ｃｏｓｔｓ ｏｆ Ｍ＆Ｓ ａｃｔｉｖｉｔｉｅｓ， ｃｏｌｌａｂｏｒａｔｉｖｅ ｔｅｃｈｎｏｌｏｇｉｅｓ ｍｕｓｔ ｂｅ ｉｎｔｒｏｄｕｃｅｄ ｔｏ ｓｕｐｐｏｒｔ ｔｈｅｓｅ ａｃｔｉｖｉｔｉｅｓ ｂｙ ｆｏｓｔｅ⁃ ｒｉｎｇ ｔｈｅ ｓｈａｒｉｎｇ ａｎｄ ｒｅｕｓｅ ｏｆ ｍｏｄｅｌｓ， ｂｙ ｆａｃｉｌｉｔａｔｉｎｇ ｔｈｅ ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ａｍｏｎｇ Ｍ＆Ｓ ｓｔａｋｅｈｏｌｄｅｒｓ， ａｎｄ ｍｏｒｅ ｇｅｎｅｒａｌｌｙ ｂｙ ｉｎｔｅｇｒａｔｉｎｇ ｐｒｏｃｅｓｓｅｓ， ｔｏｏｌｓ ａｎｄ ｐｌａｔｆｏｒｍｓ． Ｔｈｅ ＣｏＭｅｔＳ ｔｒａｃｋ ａｉｍｓ ｔｏ ｆｏｓｔｅｒ ｉｎｎｏｖａｔｉｖｅ ｒｅｓｅａｒｃｈ ｃｏｎｔｒｉｂｕｔｉｏｎｓ ｔｈａｔ ａｄｄｒｅｓｓ ｃｏｌｌａｂｏｒａｔｉｏｎ ｉｓｓｕｅｓ ｉｎ ｔｈｅ ｆｉｅｌｄ ｏｆ Ｍ＆Ｓ ａｎｄ ｖｉｃｅ ｖｅｒ⁃ ｓａ， ｉ．ｅ．， ｃｏｎｔｒｉｂｕｔｉｏｎｓ ｔｈａｔ ｕｓｅ Ｍ＆Ｓ ｍｅｔｈｏｄｏｌｏｇｉｅｓ ａｎｄ ｔｏｏｌｓ ｔｏ ａｄｄｒｅｓｓ ｔｈｅ ｄｅｓｉｇｎ ｏｆ ｃｏｌｌａｂｏｒａｔｉｖｅ ｅｎｖｉｒｏｎｍｅｎｔｓ． Ａ ｃｏｍｂｉｎａｔｉｏｎ ｏｆ ｂｏｔｈ ｉｓ⁃ ｓｕｅｓ ｉｎ ｔｈｅ ｓａｍｅ ｖｅｎｕｅ ｗｉｌｌ ｆｕｒｔｈｅｒ ｃｏｎｔｒｉｂｕｔｅ ｔｏ ｔｈｅ ｕｎｄｅｒｓｔａｎｄｉｎｇ ｏｆ ｔｈｅ ｕｎｄｅｒｌｙｉｎｇ ｍｅｃｈａｎｉｓｍｓ ｔｈａｔ ｃａｎ ａｆｆｅｃｔ ｔｈｅ ｑｕａｌｉｔｙ ｏｆ ｔｈｅ ｓｅｒｖｉｃｅ ｄｅｌｉｖｅｒｅｄ ｂｙ ｃｏｌｌａｂｏｒａｔｉｖｅ ｅｎｖｉｒｏｎｍｅｎｔｓ ｆｏｒ Ｍ＆Ｓ． Ｔｈｅ ＣｏＭｅｔＳ ｔｒａｃｋ ｉｓ ｈｅｌｄ ｕｎｄｅｒ ｔｈｅ ａｅｇｉｓ ｏｆ ｔｈｅ ＷＥＴＩＣＥ ２０１６ ｃｏｎｆｅｒｅｎｃｅ， ｔｈｅ ２５ｔｈ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｅｎａｂｌｉｎｇ Ｔｅｃｈｎｏｌｏｇｉｅｓ： Ｉｎｆｒａｓｔｒｕｃｔｕｒｅ ｆｏｒ Ｃｏｌｌａｂｏｒａｔｉｖｅ Ｅｎｔｅｒｐｒｉｓｅｓ， ｗｈｉｃｈ ｗｉｌｌ ｂｅ ｈｅｌｄ ｉｎ Ｐａｒｉｓ （Ｆｒａｎｃｅ） ｆｒｏｍ Ｊｕｎｅ １３ｔｈ ｔｏ Ｊｕｎｅ １６ｔｈ， ２０１６． Ｗｅｂｓｉｔｅ： ｈｔｔｐ：／ ／ ｗｗｗ．ｓｅｌ．ｕｎｉｒｏｍａ２．ｉｔ ／ ｃｏｍｅｔｓ１６／ 第 ３ 期 赵姝，等：基于社团结构的多粒度结构洞占据者发现及分析 ·３５１·