分层递阶的网络结构洞占据者挖掘及分析

崔平平，赵姝，陈洁，钱付兰，张以文，张燕平

(1. 安徽大学 图书馆，安徽 合肥 230601； 2. 安徽大学 协同创新中心，安徽 合肥 230601； 3. 安徽大学 计算机科学与技术学院，安徽 合肥 230601)

0 引言

近年来，对于社交网络用户影响力[1-2]的研究，研究者从宏观的基于复杂网络理论的分析，对网络的度与度分布、聚集系数、路径长度以及小世界和幂律分布等统计特性进行分析，到中观的网络拓扑结构分析，对网络进行合理的社团划分。在对网络的拓扑结构研究基础上，研究焦点逐渐转移到微观网络中关键节点的发现。关键节点对于控制网络信息传播具有重要作用，结构洞即是网络中的一类关键节点。1992年，罗纳德·伯特(Ronald Burt)以Granovertter的强关系和弱关系的假设、库克的社交网络交换论和伯特本人关于结构自主性和厂商边际效益为理论背景，在《结构洞》一书中首次提出并定义了结构洞[3]。

目前，对于结构洞的研究，主要是通过分析结构洞的特点，结合实际为挖掘结构洞建模。Buskens V和Van de Rijt A[4]以网络游戏的形成为结构洞建模，他们认为节点A只有处在节点B和C中间时才能获益。Goyal和Vega-Redondo[5]从博弈论的角度分析结构洞并建模，他们认为节点A在节点B和C之间任意位置都有可能获益。Kleinberg等[6]通过对社会网络随时间变化规律建模以扩展伯特结构洞理论的工作。

研究结构洞算法具有重要的现实意义和商业价值。Yu和Liu等人[7]提出一种识别网络重要节点的算法，其优越性高于中介中心度、节点度和接近中心度。Zhang等[8]提出二分查找算法寻找广义结构洞。基于网络结构特征的方法，李泓波和张健沛等[9]提出影响因子优化算法和基于拓扑势理论的重叠社区识别方法，识别社区间结构洞。基于信息传播的方法，Lou和Tang[10]根据两级信息传播理论，提出基于意见领袖的HIS和基于最小割的MaxD两种挖掘模型来挖掘top-k结构洞。

以上对结构洞的研究主要集中在单一粒度上，即只在网络中的某一层挖掘关键节点。然而我们发现，真实网络是一种具有分层嵌套现象的分层网络，网络中大的社团可以细分为多个小的社团。例如，一所大学可细分为很多院系，院系又细分为多个专业，专业细分出不同年级。将大学看作大社团，那么院系即为大社团里的小社团，专业是社团中更小的社团。从学院角度，网络是一种划分；从年级角度，网络是一种更细的划分。这种大社团里包含小社团的现象，就是网络的一种分层递阶特性。

在具有分层递阶特性的网络中，不同层级的关键节点不一定相同。上例中，学院层的结构洞节点，不一定还是专业层的结构洞节点。只对网络的某一层进行分析时，可能忽略了某些在其他层占据重要位置的节点，从而使结果并不能反映整个网络的真实状况。因此，在挖掘网络的结构洞时，需要考虑网络不同分层对结构洞结果的影响。网络的分层递阶特性符合粒计算的商空间模型，采用粒计算的商空间理论为社交网络的这种分层递阶特性的数据分析提供了理论基础。

综上所述，本文提出一种基于分层递阶的结构洞挖掘方法HI-SH。首先，基于分层递阶的商空间理论，对网络进行多粒度社团划分，得到每一粒度下网络的社团；然后，根据两级信息传播理论，用结构洞挖掘算法，挖掘每一粒度下top-k结构洞；最后，对不同粒度下结构洞的演化进行分析。在公用数据Topic16和真实数据ICML_10中进行实验。

本文第二节是相关工作，介绍结构洞的概念、粒计算的商空间模型、结构洞挖掘算法和社团划分算法，第三节是多粒度结构洞挖掘方法模型，第四节是实验及结果分析，第五节是全文总结与展望。

1 结构洞理论及相关算法

根据伯特给出的结构洞定义[3]，结构洞是社会关系网络中互相之间没有直接或间接的联系，拥有互补资源或信息的个体之间存在的空位。从网络的整体上看，这种空位就像网络结构中的洞穴，本质上结构洞表示的是三方之间的非冗余联系。如图1所示，左图中，节点1与节点2、3、4相连，信息通过节点1在节点2、3、4之间传播。如果此时删除节点1，由于节点2、3、4之间没有边相连，不能产生联系，信息将无法传播。此时节点1可能是这个网络的结构洞占据者。但右图中，删除节点1，节点2、3、4之间还有边相连，信息可以继续传播，此时节点1就可能不是这个网络的结构洞占据者。因此，找到网络中的结构洞，对于控制信息传播具有重要意义，研究结果表明，在Twitter网络上，1%的结构洞占据者将控制25%的信息传播[10]。

图1 结构洞图示

伯特提出结构洞指数[3]作为结构洞度量指标，结构洞指数包括有效规模、效率、网络约束度和等级度四个方面，其中最主要的是约束度。约束度以节点对其他节点的依赖值为衡量指标，定义为节点在个体网络中拥有的利用结构洞的能力。约束度值越小，结构洞程度越大，节点可能占据越多结构洞位置；约束度值越大，节点可能占据较少结构洞位置。

伯特指出“你自己的机会受到的约束取决于两个因素： 一是你曾经投入了大量时间和精力的另一个接触者q；另一个是在多大程度上向接触者j的关系投入大量的精力。”[3]因此，节点i对其邻居节点j的约束度计算如式(1)所示。

(1)

其中q≠i,j，pij为节点i花费在与其直接合作的节点j上的时间和精力占节点i花费的总时间和精力的关系比例，在网络中，用节点的度来衡量。piqpqj为节点i和j之间的冗余度，定义网络的冗余度为该节点所在的网络中其他节点的平均度。piqpqj的总和为节点i花费在节点j的关系上的时间和精力相对于节点i花费在其他节点关系上的时间和精力的比例。因此节点i的总约束度如式(2)所示。

(2)

根据两级信息传播理论，信息总是先流向意见领袖，再由意见领袖流向大众，Lou和Tang提出挖掘网络结构洞的HIS算法[10]，他们认为从意见领袖传播的信息更容易传播到更广泛的群体，如果一个个体与不同社团的意见领袖之间有直接联系，则这个个体很有可能成为结构洞。该算法中首先通过PageRank算法[11]，初始化网络中节点在每个社团的重要性，计算网络结构洞的可能性大小；通过迭代公式，重新计算节点重要性，重新计算网络结构洞可能性大小，直到节点的重要性不再更新为止，最后按节点重要性的值从大到小得到网络的结构洞排名靠前的结构洞。本文将以HIS算法作为单一粒度下挖掘结构洞占据者的基本算法，在分层递阶的网络中挖掘多粒度结构洞。

2 分层递阶的商空间模型

人类智能的特点是人们能从极不相同的粒度上观察和分析同一问题。人们不仅能在不同粒度的世界上进行问题求解，还能很快从一个粒度世界跳到另一个粒度世界。这种处理不同粒度世界的能力，正是人类问题求解强有力的表现[12]。商空间理论提供了一个描述不同粒度世界的模型。

定义1商空间模型[12]，对问题(X,f,T)，其中X表示问题的论域，f表示论域的属性，T表示论域的结构，从不同的粒度(角度、层次)考察问题(X,f,T)，是指给定X的一个等价关系R，并由R产生一商集[X]，然后研究相应问题([X],[f],[T])，其中[f]，[T]分别表示商集[X]上对应的商属性函数和商结构，称([X],[f],[T])为(X,f,T)的商空间。

定义2商空间链[13]，定义一个粗细关系，[X]i<[X]j⟺[X]iis coarser than[X]j。如果[X]i是[X]j的商集, 则表示[X]i<[X]j。序关系[X]1<[X]2<……<[X]m=X就叫分层商空间链。

定义3商坐标[13]，X的一个分层商空间链[X]1<[X]2<……<[X]m=X，对于∀x∈X，x=(xC1,xC2,……,xCm)，其中，xCi是[X]i中包含x的粒子。在一个分层商空间链[X]1<[X]2<……<[X]m=X中，x的分层商空间坐标即是(xC1,xC2,……,xCm)，简称分层坐标。

粒计算[14-15]以粒子为运算对象进行问题的求解。一个粒化准则对应一个粒层，不同的粒化准则对应多个粒层，这些粒层之间的相互联系构成了一个关系结构，即粒结构。在商空间模型中，建立的粒结构是一种分层递阶的链式结构，在不同的粒层上，同一个问题可以以不同的粒度表示，粒计算的主要特点是在同一个问题的求解上，可以在不同粒层间转化。本文将分层递阶的链式结构应用于网络分层中，用不同的粒度来表示不同层级的社团，实现网络的不同粒层间的转化。

在分层递阶网络的社团划分上，沈等[16]提出一种基于极大团的凝聚层次聚类算法EAGLE用于层次和重叠社团的结构挖掘，该算法的主要思想： 首先，找到网络的极大团，作为初始社区；其次将具有最大相似度的社团对不断合并，生成网络的树状图；最后在生成树上根据EQ的值选择合适位置断开，得到相应社团划分。为获取最合理的社团结构，文章提出一种新的模块度指标，如式(3)所示。

(3)

其中，m是网络中边总数，kv是节点v的度，Ci是网络中社团，Ov是节点v所在社团数目，A是网络图的邻接矩阵，如果两节点之间有连接边，则Avw=1，否则为0，通常选择在EQ值最大的位置对生成树进行切割，进而得到理想社团划分。

本文在EAGLE方法层次社区结构基础上，最终获取分层递阶社团结构，将每一粒度下的社团作为HIS算法输入，取该粒度下的结构洞占据者，最终通过结构洞的商坐标建立结构洞在不同粒度下的联系，并对其进行分析。

3 多粒度结构洞挖掘方法3.1 主要框架

分层递阶网络的多粒度结构洞挖掘方法，其主要思想是在社团划分时将网络进行分层，网络中的每一层代表一个粒度，分别挖掘不同粒度下的结构洞。主要步骤： 首先对网络进行多粒度社团划分，得到每一粒度下的社团划分结果，实验中选取了三个粒度，分别为一个社团模块度最优、两个模块度次优的三种情况下的社团划分作为三个粒度；对于不同粒度下的节点与节点所在的社团，使用HIS算法求结构洞。接着，记录结构洞占据者排名靠前节点的分层坐标。对比这些结构洞占据者的位置变化，分析网络结构洞这类关键节点的演化过程。

3.2 多粒度结构洞挖掘方法HI-SH

分层递阶网络的多粒度结构洞挖掘方法的逻辑符号表示如下：

其中，αi和βS均是可调的参数，且αi+βS<1。

(6)

其中节点v的PageRank值r(v)的计算如式(7)所示。

(7)

式中，c是一个常数，节点v′是节点v的所有邻居节点，N(v′)表示节点v′的度。

HI-SH多粒度结构洞挖掘过程如下：

方法1 HI-SH多粒度结构洞挖掘方法输入:给定网络G(V,E),参数αi,βS,收敛阈值ε输出:结构洞占据者集合VSH和结构洞节点分层坐标XSHStep-1:对每一个节点v∈VStep-2:使用分层社团发现算法,求每一层网络社团CLji={v1,v2,…}Step-3:对每一层网络Step-4:对当前层的每一个节点v∈VStep-5:根据公式I(v,CLi)=r(v),v∈CLiI(v,CLi)=0,v∉CLi对网络中的每个节点进行初始化Step-6:对每个节点v∈VStep-7:对每个社团CLi∈CLStep-8:计算I(v,CLi)=maxeuv∈ESL⊆CL∧CLi∈SL{I(v,CLi),αiI(u,CLi)+βSLH(u,SL)}Step-9:计算H'(v,SL)=minCLi∈S{I'(v,CLi)}Step-10:判断maxv∈V,CLi∈C|I'(v,CLi)-I(v,CLi)|≤ε是否成立?若成立,则结束,不成立,则继续Step-11:计算VSH=max|SL|≥2{βSLH(v,SL)}的值Step-12:对这一层网络的VSH取top-k结构洞Step-13:标记VSH中每个节点xSH在不同粒度社团的坐标Xv={(CL1i1,CL1k1,…),(CL2i2,CL2k2,…),…,(CLnin,CLnkn,…)}Step-14:重复Step-3到Step-13,直到求出前三层VSH节点End

通过上述方法，即得到分层递阶网络在不同粒层下排名靠前的结构洞和结构洞节点在不同分层下所在的社团坐标。下面以图2中节点为例来说明多粒度结构洞挖掘过程。

图2 网络在不同粒度下的社团划分

4 实验

4.1 实验数据

本文实验数据包含公用数据和真实数据。公用数据是清华大学ArnetMiner系统里下载的To-pic16数据。真实数据是搜集CCF推荐国际学术会议A类的ICML从2005年到2014年共10年的会议论文，搜集论文标题和文章作者信息，对数据进行处理，若两个作者出现在同一篇文章里，则这两个作者之间有一条边，数据集记为ICML_10。数据信息如表1所示。

表1 实验数据

4.2 实验结果及分析

4.2.1 不同粒度下的排序情况

在对社团分层时，选择一个社团模块度最优、两个模块度次优三种情况下的社团划分结果，公用数据Topic16的社团分层结果分别为： 粒度最粗的39个社团、粒度变细的163个社团、粒度更细的245个社团。使用HIS算法作为单粒度下的结构洞挖掘算法，对挖掘结果分析时取每一粒度下的排名前20的结构洞，结果如图3所示，图中的断层表示节点不在top20之内。

真实数据ICML_10的社团分层结果分别为： 粒度最粗的342个社团、粒度变细的565个社团、粒度更细的806个社团。取每一粒度下的排名前20的结构洞，结果如图4所示。

图3 HI-SH方法多粒度结构洞占据者排名变化(Topic16)

图4 HI-SH方法多粒度结构洞占据者排名变化(ICML_10)

从图3、图4两种数据可以看出，在不同的粒度下，社团中的节点发生变化导致结构洞占据者发生变化，细粒度下的结构洞占据者连接的两个社团很可能变成粗粒度下的一个社团。此时，该节点可能会变成社团内部一个普通的节点，而不再承担粗粒度下结构洞占据者的角色。

4.2.2 分层坐标情况

为进一步分析结构洞占据者在信息传播中所起的作用，对于Topic16数据，表2给出最细粒度下top20结构洞占据者和意见领袖PageRank排名，表中第三列表示节点在由粗到细的三个粒度中所在社团编号，如1,(2,7),(15,17,32)，用“，”表示不同的分层。“1”表示在最粗粒度下属于第一个社团，“(2,7)”表示在第二粗粒度下，同时属于编号为2和7两个社团，“(15,17,32)”表示在最细粒度下同时属于编号为15、17和32三个社团。

表2 Topic16在粒度最细时top-20结构洞的PageRank排名和分层社团坐标

通过观察发现，节点所在不同粒层的社团粒度由粗到细的过程中，占据重叠位置的节点变多，结构洞节点占据的社团也在变多。结合图3，在社团粒度较粗的时候，重叠节点不在结构洞位置上。再进一步将社团粒化，可以发现更多占据结构洞位置的重叠节点。在这些结构洞占据者中，在粗粒度下，若节点是重叠节点，粒度细化时，占据结构洞位置的节点还是重叠节点，并且占据更多的社团。表中结构洞节点在粒度最粗时所在社团大部分都在1号社团，所以有可能某个社团存在很多结构洞。

对于ICML_10数据，表3同样地给出最细粒度下top20结构洞占据者和意见领袖PageRank排名。

表3 ICML_10在粒度最细时top-20结构洞的PageRank排名和分层社团坐标

续表

对真实数据ICML_10，节点在粒度变细的过程中，同样表现出占据更多的重叠节点的可能性。

4.2.3 结构洞评价指标

使用约束度来评价求得结构洞的重要程度，对不同粒度下top-20结构洞节点求约束度之和，结果如图5所示，其中横坐标数字表示结构洞排名前多少的节点，纵坐标表示排名前多少节点的约束度之和。

图5 HI-SH方法(HIS)多粒度结构洞约束度之和变化

对于Topic16，对比不同粒层下结构洞节点约束度之和，可以明显发现，不论哪个粒层的结构洞，其约束度之和都比意见领袖的约束度之和明显偏低，即结构洞要比意见领袖更不受网络其他节点的约束，在信息传播中更不受网络中其他节点的约束。对比不同粒层结构洞约束度之和，在粒度最粗的情况下，节点约束度之和最优。当k<7时，不同粒层结构洞的约束度之和差别不大；当k>7时，在粒度最粗的情况下，节点约束度之和最优。对于ICML_10，对比不同粒层结构洞约束度之和，当k<9时，约束度之和差别不大；当k>9时，细粒度下的结构洞约束度之和增幅变小，此粒层下的结构洞节点更不受网络的约束。相比于结构洞，发现其意见领袖约束度之和更低，更不受网络的约束。

4.2.4 对比不同算法约束度之和

MaxD算法是文献[10]中提到的另一种计算结构洞的模型，它基于最小割原理，该算法对社团粒度的变化敏感性不大。使用MaxD算法求单粒度下结构洞，对两组数据求结构洞约束度之和，结果如图6所示。

图6 HI-SH方法(MaxD)多粒度结构洞约束度之和变化

对于Topic16数据，当k<10时，节点约束度之和在粒度最粗的时候较小；当k>10时，约束度之和相同。对比不同算法的结果，发现两种结构洞算法求得的排名靠前的结构洞节点的约束度都比较低，而PageRank排名靠前的节点的约束度之和相对较高。对于数据ICML_10，节点的约束度之和与网络的粒度没有直接关系。在不同粒度情况下，都有可能出现约束度比较低的结构洞。而PageRank排名靠前的节点的约束度之和介于两者之间。

Topic16和ICML_10数据实验结果表明，对网络结构洞的挖掘，不能通过单一的一个粒层找到最优的，即网络的结构洞是动态变化的。在挖掘结构洞的过程中，粒度过粗或者过细的实验结果都不是单调变化的。因此，下一步的研究工作是在实验中找到合适的粒度，并通过这些粒度的变化分析网络的演化过程。

5 总结与展望

本文针对结构洞研究中没有考虑网络的分层递阶特性的问题，提出了一种从多粒度角度挖掘结构洞的方法，使用该方法对不同数据进行实验，可以看到不同粒度下的结构洞占据者信息，这对研究社交网络影响力、网络的演化过程和控制信息的传播具有重要意义。本文在结构洞的研究理论和实践基础上，对分层递阶网络的多粒度结构洞特性进行了分析，由于结构洞算法求得排名的稳定性还有待提高，不同粒度下得到的结构洞影响力指数不同，约束度与粒度粗细并没有直接联系。所以在接下来的研究中，将针对如何自适应挖掘最合适的粒度，使得对于整个网络来说找到最具影响力的结构洞，将该方法进一步完善。

[1] 黄俊铭,沈华伟,程学旗.利用社交网络的影响力骨架探索信息传播[J].中文信息学报,2016,30(02):74-82.

[2] 许丹青,刘奕群,张敏,等.基于在线社会网络的用户影响力研究[J].中文信息学报,2016,30(02):83-89.

[3] Burt R S. Structural holes: The social structure of competition [M]. Boston: Harvard University Press,1992.

[4] Buskens V, Van de Rijt A. Dynamics of networks if everyone strives for structural holes [J]. American Journal of Sociology, 2008, 114(2): 371-407.

[5] Goyal S, Vega-Redondo F. Structural holes in social networks [J]. Journal of Economic Theory, 2007, 137(1):460-492.

[6] Kleinberg J, Suri S, Tardos É, et al. Strategic network formation with structural holes[J]. Proceedings of Acm Conference on Electronic Commerce, 2008, 7(3):284-293.

[7] Hui Y, Zun L, Yongjun L.Using local improved Structural Holes method to identify key nodes in complex networks[C] //Proceedings of Measuring Technology and Mechatronics Automation (ICMTMA), 2013 Fifth International Conference on. IEEE, 2013: 1292-1295.

[8] Zhang E, Wang G, Gao K, et al. Generalized structural holes finding algorithm by bisection in social communities[C]//Proceedings of Genetic and Evolutionary Computing (ICGEC), 2012 Sixth International Conference on. IEEE, 2012:276-279.

[9] 李泓波,张健沛,杨静,等. 基于拓扑势的重叠社区及社区间结构洞识别——兼论结构洞理论视角下网络的脆弱性[J].电子学报, 2014,42(1):62-69.

[10] Lou T, Tang J. Mining structural hole spanners through information diffusion in social networks[C]//Proceedings of the 22nd International Conference on World Wide Web. International World Wide Web Conferences Steering Committee, 2013:825-836.

[11] Page L, Brin S, Motwani R, et al. The PageRank citation ranking: Bringing order to the web[R].Stanford University： Stanford InfoLab, 1999.

[12] 张铃.问题求解理论及应用[M]. 北京:清华大学出版社, 2007.

[13] Zhao S, Zhang L, Xu X, et al. Hierarchical description of uncertain information[J]. Information Sciences, 2014, 268(1):133-146.

[14] Zhang B, Zhang L. Theory and applications of problem solving[M]. North-Holland: Elsevier Science Publishers BV, 1992.

[15] 张铃, 张钹. 模糊商空间理论(模糊粒度计算方法)[J]. 软件学报, 2003, 14(4):770-776.

[16] Shen H, Cheng X, Cai K, et al. Detect overlapping and hierarchical community structure in networks[J]. Physica A Statistical Mechanics & Its Applications, 2009, 388(8):1706-1710.

E-mail: chenjie200398@163.com