.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所示。图 ３ 细粒度下的社团结构 Ｆｉｇ．３ Ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｉｎ ｆｉｎｅ ｇｒａｎｕｌａｒｉｔｙ ２ 多粒度结构洞发现方法 本文算法基于社团结构，主要思想为将多粒 度［２５⁃２６］与社团划分结合，得到不同粒度下的社团结 构，最后再根据不同粒度下的社团结构求出网络中 的结构洞占据者。 为有效挖掘层次网络中的结构 洞，我们将 ＭａｘＤ 模型［２０］ 中的最小割思想引入到层 次网络中，作为分层网络结构洞挖掘的理论依据。 在不同粒度的社团结构中，使用最大流算法，分析节 点的最大流变化情况并根据最小割求出结构洞占据 者。 多粒度结构洞发现方法 ＭＧ＿ＭａｘＤ 的主要步 骤：１）使用分层社团发现算法对网络进行多粒度划 分，并得到不同粒度的社团划分结果；２） 根据当前 层网络的社团结构，使用 ＭａｘＤ 算法中的最大流和 最小割求出结构洞占据者；３）重复第 ２）步，直到求 出前 ｒ 层的结构洞占据者集合 Ｖ ｒ ＳＨ 。 实验最后将分 析不同粒度下结构洞占据者的结构洞程度变化。 ＭＧ＿ＭａｘＤ 算法的输入为网络 Ｇ、结构洞个数 ｋ、分层 数 ｒ； 输 出 为 前 ｒ 层 结 构 洞 占 据 者 集 合 Ｖ ｒ ＳＨ 。 ＭＧ＿ＭａｘＤ算法具体步骤如下。 算法 ２ 层次结构网络结构洞发现方法 ＭＧ＿ ＭａｘＤ 输入 网络 Ｇ ＝ （Ｖ，Ｅ），结构洞个数 ｋ，分层数 ｒ 输出 前 ｒ 层结构洞占据者集合 Ｖ ｒ ＳＨ １）使用分层社团发现算法将网络 Ｇ 分层，并获 得前 ｒ 层的网络社团结构 Ｃ ＝ ｛Ｃ ｈ ｉ ｝（１≤ｈ≤ｒ，１≤ｉ≤ ｎｈ ｝，式中 Ｃ ｈ ｉ 表示第 ｈ 层的第 ｉ 个社团，ｎｈ 表示第 ｈ 层的社团个数，ｈ 越大，表示社团划分粒度越细。 ２） 对 Ｃ ｈ （１≤ｈ≤ｒ）层网络 给每个节点 ｖ∈Ｖ 初始化流量 ｆ（ｖ）＝ ０； 对每个非空 Ｓ ｈ⊂｛１，２，…，ｌ｝，ｌ 为当前层网络 社团个数； 利用源点 ＥＳ ＝∪ｉ∈Ｓ ｈＣ ｈ ｉ 和汇点 ＥＴ ＝ ∪ｉ∉Ｓ ｈＣ ｈ ｉ ，在 图 Ｇ ＼Ｖ ｈ ＳＨ上计算最大流； 对每个节点 ｖ ∈ Ｖ， 对节点 ｖ 添加通过其的 流 ｆ（ｖ）。 ３） 选择 Ｏ（ｋ）个具有最大 ｆ 值的节点作为候选 者 Ｄ。 ４） 对 ｐ ｈ∈Ｄ，即第 ｈ 层网络的结构洞占据者候 选节点，计算：ｐ ∗ ｈ ＝ ａｒｇ ｍｉｎｐ ｈ∈ＤＭＣ（Ｇ ＼ （Ｖ ｈ ＳＨ∪｛ｐ ｈ ｝）， Ｃ ｈ ）。 ５） 更新 Ｖ ｈ ＳＨ ＝ Ｖ ｈ ＳＨ∪｛ｐ ∗ ｈ ｝。 ６） 重复 ２） ～ ５），直到｜ Ｖ ｈ ＳＨ ｜ ＝ ｋ。 ７） 重复 ２） ～ ６），直到求出前 ｒ 层的结构洞占 据者集合 Ｖ ｒ ＳＨ 。 社团结构是复杂网络最重要和最普遍的拓扑性 质之一。 在信息传播网中，同一社团内的信息传播 较为迅速，而社团间的信息传播较为缓慢。 在分层 网络中，社团划分粒度的变化将改变整个网络的社 团结构，跨越社团的结构洞占据者属性也会随之变 化。 对分层网络中的结构洞占据者进行发现及分析 可以帮助揭露多粒度网络中节点跨越结构洞程度， 即不同粒度下结构洞节点在社团间信息传播和异质 性资源获取方面优势的变化，以及结构洞位置的变 化情况。 在 ＭＧ＿ＭａｘＤ 方法中，使用 ＥＡＧＬＥ 算法首先获 得最优模块度下的社团结构，然后在此社团结构下， 将网络细化得到较细粒度下的社团结构，重复此步 骤直到获得前 ｒ 层的社团结构。 根据获得的多粒度 社团结构，使用 ＭＧ＿ＭａｘＤ 算法获得网络 Ｇ 在不同 粒度下的前 ｋ 个结构洞占据者。 社团划分粒度越 细，则网络中的社团个数越多，且社团规模可能减 小，即粗粒度下的社团在细粒度下可能被划分为多 个社团，使社团结构产生很大变化。 ３ 实验设置与结果分析 ３．１ 数据及衡量指标 本文所使用的数据包括公用数据和实例数据。 公用数据为在清华大学 ＡｒｎｅｔＭｉｎｅｒ（研究者社会网 络分析与挖掘系统） 系统下载的数据 Ｔｏｐｉｃ １３１ 和 Ｔｏｐｉｃ １４５，是公用的合著网络数据集。 以论文中的 作者作为网络的节点，作者间的合著关系作为边。 实例数据为 ＣＣＦ 推荐国际学术会议 Ａ 类的 ＩＣＭＬ 会议从 ２００５ 年到 ２０１４ 年共 １０ 年出版的论文，统计 论文标题和文章作者信息，对数据进行处理，若两个 作者出现在同一个文章里，则这两个作者之间有一 条边，依据这些信息最后构建为一个合著网络，将数 据集表示为 ＩＣＭＬ＿１０。 实验数据具体信息如表 １ 所示。 ·３４６· 智 能 系 统 学 报 第 １１ 卷