第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数据集在两种社团划分算法下得到的社团数 分析结构洞占据者的方法。在不同数据集上进行实 相差不大，得到的结构洞解集质量也很相近。可以 验，对结果进行分析，发现不同粒度的社团划分将影 发现在单一粒度下，社团数量对结构洞占据者跨越 响节点跨越结构洞的程度。通过多组对比实验发 结构洞程度存在一定影响，从整体上看，当社团数增 现，在细粒度上，结构洞解集中的节点的结构洞程度 加时，结构洞解集质量也随之提高，即节点跨越结构 较高，而在粗粒度上，由于将整个网络粗化，减弱了解集的质量存在一定关系，在寻找网络中的结构洞 时应结合社团划分结果的模块度因素，并选择合适 的社团划分粒度。 图 １０ Ｔ１３１ 数据集多粒度下不同算法对比结果（ｔｏｐ ２０） Ｆｉｇ．１０ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｒｅｓｕｌｔｓ ｏｆ ｄｉｆｆｅｒｅｎｔ ａｌｇｏｒｉｔｈｍｓ ｏｎ Ｔ１３１ ｉｎ ｍｕｌｔｉ⁃ｇｒａｎｕｌａｒｉｔｙ （ｔｏｐ ２０） 图 １１ Ｔ１４５ 数据集多粒度下不同算法对比结果（ｔｏｐ ２０） Ｆｉｇ．１１ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｒｅｓｕｌｔｓ ｏｆ ｄｉｆｆｅｒｅｎｔ ａｌｇｏｒｉｔｈｍｓ ｏｎ Ｔ１４５ ｉｎ ｍｕｌｔｉ⁃ｇｒａｎｕｌａｒｉｔｙ （ｔｏｐ ２０） 为验证单一粒度下社团数对结构洞解集质量的 影响，本文使用 Ｆａｓｔ⁃Ｎｅｗｍａｎ 算法［２７］ 和 Ｂｌｏｎｄｅｌ 算 法［２８］分别对 Ｔ１３１ 数据集和 Ｔ１４５ 数据集的原网络 进行社团划分，并获得单一粒度下相应的社团结构， 使用 ＭＧ＿ＭａｘＤ 算法获得单一粒度下的结构洞占据 者，最后对结构洞解集的质量进行分析。 Ｔ１３１ 数据 集在 Ｂｌｏｎｄｅｌ 和 Ｆａｓｔ⁃Ｎｅｗｍａｎ 算法下分别得到 ２５ 和 ３０ 个社团，Ｔ１４５ 数据集在 Ｂｌｏｎｄｅｌ 和 Ｆａｓｔ－Ｎｅｗｍａｎ 算法下分别得到 １６ 和 ３０ 个社团。 实验结果如图 １２ 和图 １３ 所示。 图 １２ 和图 １３ 显示， 由于单粒度下 Ｔ１３１ 和 Ｔ１４５ 数据集在两种社团划分算法下得到的社团数 相差不大，得到的结构洞解集质量也很相近。 可以 发现在单一粒度下，社团数量对结构洞占据者跨越 结构洞程度存在一定影响，从整体上看，当社团数增 加时，结构洞解集质量也随之提高，即节点跨越结构 洞的程度变大。 图 １２ Ｔ１３１ 数据集在单粒度下对比结果（ｔｏｐ ２０） Ｆｉｇ．１２ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｒｅｓｕｌｔｓ ｏｆ Ｔ１３１ ｉｎ ｓｉｎｇｌｅ ｇｒａｎｕ⁃ ｌａｒｉｔｙ 图 １３ Ｔ１４５ 数据集在单粒度下的对比结果（ｔｏｐ ２０） Ｆｉｇ．１３ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｒｅｓｕｌｔｓ ｏｆ Ｔ１３１ｉｎ ｓｉｎｇｌｅ ｇｒａｎｕ⁃ ｌａｒｉｔｙ （ｔｏｐ ２０） 通过对比 ＭＧ＿ＭａｘＤ 算法和 ＨＩＳ 算法在不同数 据集上的实验结果，发现在同一网络下，不同的社团 划分粒度会影响结构洞占据者的选取。 所以在获取 网络中的结构洞占据者时，由于不同社团划分粒度 将影响节点跨越结构洞的程度，可以综合网络的多 粒度社团划分结构，找到合适的粒度，发现更加准确 的结构洞占据者。 ４ 结束语 本文主要研究了多粒度对结构洞占据者跨越结 构洞程度的影响，从社交网络的结构洞理论出发，考 虑到不同社团划分粒度将影响结构洞占据者的选 取，在多粒度社团划分的基础上，提出从多粒度角度 分析结构洞占据者的方法。 在不同数据集上进行实 验，对结果进行分析，发现不同粒度的社团划分将影 响节点跨越结构洞的程度。 通过多组对比实验发 现，在细粒度上，结构洞解集中的节点的结构洞程度 较高，而在粗粒度上，由于将整个网络粗化，减弱了 第 ３ 期 赵姝，等：基于社团结构的多粒度结构洞占据者发现及分析 ·３４９·