第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=由于社交网络中存在着不直接或间接连接的关系， 从而使拥有互补资源或信息的个体之间出现了空 位，也可看做网络中的洞穴。 结构洞是信息流动的 缺口，跨越结构洞的个体可以获得不同个体之间存 在的异质性信息。 如图 １ 所示，网络由 ９ 个节点构 成，除了节点 ５ 以外，其他节点被分为两个社团，而 这两个社团内的节点只能通过节点 ５ 产生联系，若 没有节点 ５，则两侧社团之间就产生了间隙，形成了 结构洞。 显然，节点 ５ 占据了结构洞的位置。 因此， 可以通过找到类似节点 ５ 的结构洞占据者，获得网 络中的异质性信息和资源。 图 １ 结构洞示例 Ｆｉｇ．１ Ｉｌｌｕｓｔｒａｔｉｏｎ ｏｆ ｓｔｒｕｃｔｕｒａｌ ｈｏｌｅｓ １．２ 基于社团结构的结构洞占据者发现算法 无权网络可以表示为 Ｇ ＝ （Ｖ，Ｅ），含有 ｎ 个节 点，ｍ 条边。 其中 Ｖ 表示网络中节点的集合，Ｅ 表示 网络中边的集合。 Ｖ ＝ ｛ｖ１ ，ｖ２ ，…，ｖｎ ｝，Ｅ ＝ ｛ｅ１ ，ｅ２ ，…， ｅｍ ｝，社团结构为 Ｃ ＝ ｛Ｃ１ ，Ｃ２ ，…，Ｃｌ｝。 Ｌｏｕ 和 Ｔａｎｇ ［２０］ 认为跨越结构洞的个体在不同 社团间的信息传播中发挥重要作用，结构洞占据者 在社团间起到桥接作用，去除这些结构洞节点后，社 团间的联系将会最小化，他们根据这个思想并使用 最小割提出结构洞发现方法 ＭａｘＤ。 结合最小割定 义，他们提出在去除结构洞结点后，网络 Ｇ 中 Ｃ 的 最小割将显著减小，即最小割的减少量在删除结点 后将会最大，目标函数如式（１）所示： Ｑ（ＶＳＨ，Ｃ） ＝ ＭＣ（Ｇ，Ｃ） － ＭＣ（Ｇ＼ＶＳＨ，Ｃ）， ｜ ＶＳＨ ｜ ＝ ｋ （１） ＭａｘＤ 算法的具体流程如下所示。 算法 １ ＭａｘＤ 输入 网络 Ｇ ＝ （Ｖ，Ｅ），结构洞个数 ｋ，社团数 ｌ，社团结构 Ｃ ＝ ｛Ｃｉ｝。 输出 Ｔｏｐ ｋ 个结构洞占据者集合 ＶＳＨ 。 １）初始化 ＶＳＨ为空集； ２）当｜ ＶＳＨ ｜ ＜ｋ 时，循环给每个节点 ｖ∈Ｖ 初始化 流量 ｆ（ｖ）＝ ０； 对每个非空 Ｓ⊂｛１，２，…，ｌ｝，利用源点 ＥＳ ＝ ∪ｉ∈ＳＣｉ 和汇点 ＥＴ ＝ ∪ｉ∉ＳＣｉ 在诱导后的图 Ｇ ＼ ＶＳＨ上 计算最大流； 对每个节点 ｖ∈Ｖ 添加通过其的流 ｆ（ｖ）； ３） 选 Ｏ（ｋ）个具有最大 ｆ 值的节点作候选者 Ｄ； ４） 计算 ｐ ∗ ＝ａｒｇ ｍｉｎｐ∈ＤＭＣ（Ｇ＼（ＶＳＨ∪｛ｐ｝），Ｃ）； ５） 更新 ＶＳＨ ＝ ＶＳＨ∪｛ｐ ∗ ｝ ＭａｘＤ 算法的输入为网络 Ｇ ＝ （Ｖ，Ｅ） 和社团结 构 Ｃ ＝ ｛Ｃｉ｝，依据社团结构并结合最小割理论，最后 得到结构洞解集 ＶＳＨ 。 但现实网络中的社团结构存 在多粒度，本文主要研究多粒度对结构洞占据者跨 越结构洞程度的影响。 １．３ 社团划分算法 本文所使用的社团划分方法为 Ｓｈｅｎ 等［２４］ 提出 的能够同时探测出社团层次性和重叠性的算法 ＥＡ⁃ ＧＬＥ。 通过凝聚的方法划分社团，研究对象为网络 中的极大团，通过极大团之间的不断凝聚来实现社 团划分。 ＥＡＧＬＥ 算法分为 ２ 个步骤：１） 生成网络 的树状图；２） 在生成树上选择合适位置断开，得到 相应的社团划分。 为了评判社团划分结果的质量， 该算法提出一种新的模块度指标如式（２）所示： ＥＱ ＝ １ ２ｍ∑ｉ ｖ∈∑Ｃ，ｗ∈Ｃ １ ＯｖＯｗ Ａｖｗ － ｋｖ ｋｗ ２ｍ é ë ê ê ù û ú ú （２） 式中 Ｏｖ 是节点 ｖ 所属社团的数目。 通常选择在 ＥＱ 值最大的位置对生成树进行切割，进而得到最合理 的社团结构。 在 ＥＡＧＬＥ 中，将算法应用于已找到 的社团中去，得到一些规模更小、联系更紧密的子社 团，就可得到在不同粒度下的社团结构，即层次化社 团结构。 不同粒度下会影响网络的社团划分结果， 如粗粒度下的某个社团在细粒度下可能被划分为多 个社团，社团结构变化如图 ２ 和图 ３ 所示。 图 ２ 粗粒度下的社团结构 Ｆｉｇ．２ Ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｉｎ ｒｏｕｇｈ ｇｒａｎｕｌａｒｉｔｙ 第 ３ 期 赵姝，等：基于社团结构的多粒度结构洞占据者发现及分析 ·３４５·