·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等 从网络整体看好像网络结构中出现了洞穴。”简单 认为网络中很难存在单节点形成的结构洞，他们在 地说，结构洞是指两个关系人之间的非重复关系。拓扑性质含有无标度、小世界特性和社团结构等，转 移到对网络中重要节点的分析，如结构洞［１］ 、意见 领袖［２］等。 结构洞是网络中普遍存在的现象，在网 络中占据何种位置能够获益的想法已经得到了许多 人的关注。 个体或者团体中的中间人可以获得丰富 的信息并控制他们的网络关系，在网络中占据中心 位置的主体可以获得丰厚的利益［１］ 。 结构洞在获 取网络有效信息方面起着关键的作用，且发现网络 中的结构洞可以对网络结构进行优化和增强鲁棒 性。 结构洞理论作为网络结构分析的重要方法，在 不同 领 域 和 学 科 的 研 究 中 都 获 得 了 丰 富 的 成 果［３⁃７］ 。 在结构洞研究的推进过程中，研究者发现结构 洞占据者在网络中可以获得竞争优势和网络收益， 并提出不同的结构洞模型。 Ｋｌｅｉｎｂｅｒｇ 等［８］ 从战略 和动态方面研究了结构洞理论，进一步扩充了伯特 等研究者的工作。 他们模拟了这样的过程，即当所 有个体都在竞争桥节点位置的时候，社会网络随着 时间是如何改变的。 Ｂｕｓｋｅｎｓ 和 Ｖａｎ ［９］ 使用博弈论 方法来模拟具有结构洞的网络形成过程，认为节点 Ａ 只有处在节点 Ｂ 和 Ｃ 中间时才能获益。 Ｇｏｙａｌ 和 Ｖｅｇａ ［１０］ 提出网络形成的模型来研究社会网络中结 构洞的形成，并认为当节点 Ａ 位于任意长的 Ｂ⁃Ｃ 路 径上，且作为节点 Ｂ 和 Ｃ 的中介时，都将获得潜在 利益。 这种模型将导致形成星形网络，然而，现实中 的大部分网络并不一定是星形拓扑结构。 Ｂｒｕｇｇｅ⁃ ｍａｎ 等［１１］考虑了生态位重叠导致的分散竞争对网 络中个体的结构自主性的影响，修正了伯特的模型。 研究者通过对结构洞的性质进行分析，提出许 多基于网络结构和社团结构的结构洞度量指标。 基 于网络结构的度量主要考虑结构洞的优势，伯特提 出了 ４ 个定量描述结构洞的度量指标［１，１２⁃１３］ ，即网 络约束系数、网络有效规模、效率和等级度；Ｆｒｅｅｍａｎ 提出介数中心性指标［１４］ ；Ｎｅｗｍａｎ 等［１５］ 提出局部聚 类系数；邓世果等［１６］提出一种基于基尼系数的结构 洞测量方法，并讨论贡献度和结构洞程度之间的关 系；基于社团结构的度量主要考虑结构洞跨越不同 社团的属性，Ｒｅｚｖａｎｉ 等［１７］ 根据伯特定义中个体连 接的社团数和个体的邻居节点数提出一种结构洞度 量指标。 随着对结构洞的价值和意义继续深入研究，研 究者提出多种结构洞发现算法，在不同结构和类型 的复杂网络中准确发现结构洞占据者。 Ｚｈａｎｇ 等［１８］ 认为网络中很难存在单节点形成的结构洞，他们在 结构洞理论的基础上提出“广义结构洞”概念，并给 出基于谱图理论的启发式“广义结构洞”发现算法 ＤＧＳＨ。 Ｈｕ 等［１９］将结构洞理论扩展到有向模糊社 交网络并提出单向模糊结构洞和双向模糊结构洞的 算法，分别计算行动者占据的单向和双向模糊结构 洞个数。 Ｌｏｕ 和 Ｔａｎｇ ［２０］ 在假设网络社团结构已知 的情况下，基于两级信息流理论和最小割分别提出 两个结构洞占据者的挖掘算法 ＨＩＳ 和 ＭａｘＤ。 目前对于结构洞［２１⁃２２］ 的研究中，研究者发现社 团结构与结构洞的属性存在很大关系，并提出相应 算法。 如 Ｌｏｕ 和 Ｔａｎｇ ［２０］ 假设社团结构已知的情况 下，提出两个结构洞挖掘算法 ＨＩＳ 和 ＭａｘＤ。 研究者 主要考虑单一粒度下的结构洞，然而网络的社团结 构在不同粒度下的划分具有很大差异，且层次结 构［２３］具有嵌套关系。 社团划分粒度由粗到细时，社 团结构的规模和数量也随之变化，在粗粒度下的某 个社团，粒度变细时可能划分为多个社团。 如中国 的行政区划，将全国看作一个大网络，可从省、市、 县、乡等不同大小的区域描述网络。 省、市、县、乡等 分别代表不同粒度下划分的社团，从不同粒度描述， 则网络社团结构也会不同。 网络的层次结构特性对 节点属性如重要性、中心性等具有重要影响。 细粒 度下的结构洞占据者在粗粒度下可能不再跨越结构 洞，或结构洞程度降低甚至丧失。 综上所述，本文在单粒度基础上，研究多粒度对 网络中结构洞占据者跨越结构洞程度的影响。 本文 提出一种基于社团结构的多粒度结构洞发现方法 ＭＧ＿ＭａｘＤ，首先使用分层社团划分算法得到不同粒 度下的社团结构；然后用结构洞发现方法获得不同 粒度下的结构洞占据者集合；最后，对结构洞占据者 的跨越结构洞程度的变化规律进行分析，发现结构 洞占据者的结构洞程度即结构洞节点在社团间的优 势会随着粒度的变细而增大。 本文使用不同数据 集，并进行多组对比实验，验证实验结果。 １ 结构洞理论及相关算法 １．１ 结构洞理论 结构洞理论由美国社会学家罗纳德·博特于 １９９２ 年在其撰写的《结构洞：竞争的社会结构》 ［１］一 书中首次提出的。 所谓结构洞，即“社交网络中某 个或某些个体和有些个体发生直接联系，但与其他 个体不发生直接联系。 无直接或关系间断的现象， 从网络整体看好像网络结构中出现了洞穴。” 简单 地说，结构洞是指两个关系人之间的非重复关系。 ·３４４· 智 能 系 统 学 报 第 １１ 卷