基于优化结构洞的无向加权网络关键节点发现方法

王丽娟　蔡晓东　杨超　甘凯今　李隆泽

摘 要： 针对目前大多数关键节点发现算法没有兼顾桥节点与其他类型关键节点，造成评价结果存在片面性的问题，使用加权网络模型结合结构洞理论，提出一种优化结构洞的无向加权网络关键节点发现方法。综合考虑了节点的邻居数量及其与邻居间的拓扑结构，首先通过定义节点的邻接度和二次邻接度来衡量邻居节点对其的重要程度，在此基础上测量网络中的结构洞约束系数并通过排序发现网络中处于重要位置的关键节点。该方法既反映出节点局部连接的特性，又可在全局拓扑未知的情况下发现其中的关键节点，解决了全局方法计算复杂度高的问题。实验结果表明，该方法比基于介数、节点强度、接近度方法更准确、有效地发现无向加权网络中的关键节点。

关键词： 桥节点； 结构洞； 约束系数； 邻接度

中图分类号： TN711?34； TP391.41 文献标识码： A 文章编号： 1004?373X（2017）06?0035?05

Abstract： In order to solve the problems that most of the exiting algorithms to find key nodes do not take into account the bridge nodes and other key nodes， which may lead to an one?sided evaluation result， an optimized structural holes based method to find the key nodes in the undirected weighted networks is proposed by means of the weighted network model and the structure hole theory. The number of neighbors around the nodes and the topology structure among the nodes and neighbors are considered in this method. The importance of the neighbor nodes to the nodes is measured by defining adjacency degree and secondary adjacency degree of the nodes， and then the constraint coefficient of the structural hole in the network is calculated to find the important position of the key nodes in the network. The method can reflect the local connection feature of the node find the key nodes in network in the case that the global topology is unknown. It can solve the problem of high computational complexity of the global methods. The experiment results show that the method is better than the methods based on betweenness， node strength and proximity.

Keywords： bridge node； structure hole； constraint coefficient； adjacency degree

0 引 言

伴随着信息技术的迅猛发展，人类的社会活动日趋网络化。人们的生活被各种复杂网络[1]包围着，例如社交网络、交通网络、电力网络、邮件网络等，其中对复杂网络中的节点关键性评估[2]一直受到研究人员的广泛关注，寻找网络中的关键节点成为网络科学的重要研究内容之一。挖掘出在各类复杂网络中扮演重要角色的关键节点，有针对性地分析其性质，从而进行有效的利用，具有重要的现实意义和实用价值。复杂网络中的关键节点发现不仅与网络的拓扑结构有关还应该综合考虑其功能特征等方面的因素，结构洞理论[3]认为，在现代信息社会中，处于结构洞位置的节点或者企业可以获取更关键的信息和为企业带来更多的竞争优势，从而影响甚至于控制社会关系与信息的传播，并为企业获得累加收益，包括信息收益与控制收益等，因此对于关键节点的发现和评估不可忽略处于捷径的节点。本文的目的是发现复杂网络中的处于重要位置的关键节点，所谓的关键节点，在网络中具有活跃度较高、控制着他人交流通信、起到连接作用等特征。

近年来，复杂网络中的关键节点发现方法已经成为研究热点。从复杂网络结构角度考虑具体的关键节点重要性评价指标主要包括度中心性、介数、凝聚度、特征向量、子图、网络流、随机行走[4?6]等。这些评估方法对复杂网络关键节点重要性的度量都是侧重于全局和局部两个不同的角度来考虑的，但这些算法存在共同的问题：都是基于无权无向图，未能全面客观反映真实复杂网络情况的问题，且大都是侧重于全局角度，对关键节点重要性的度量需要遍历整个复杂网络，但对于真实场景下的复杂网络，规模比较庞大且结构复杂，所以从全局角度衡量节点重要性的困难可想而知。文献[7]中通过构造有向赋权图结构，通过对邮件网络图局部特征的分析，即认为度越大的节点在其网络中的重要性越高，从而发现处于关键位置的重要用户，但是具有度相同的节点，在网络中的重要程度未必相同，另外还有一些“桥节点”无法发现。王建伟等在文献[8]中提出了一种基于局部特征的网络节点重要性度量方法，通过考察复杂网络中节点的度和其邻居度的大小来衡量此节点在网络中的重要程度，该方法计算简单，但这种方法仅考虑了节点本身和邻居节点之间的关系，因此无法发现网络中的一些处于捷径的节点。针对此类问题的主要研究和改进方案有：文献[9]提出另外一种基于局部特征的重要性评价方法，即发现网络中“结构洞”，提出了计算结构洞的网络约束系数对网络闭合性和结构洞进行测度，这个系数描述的是网络中某个节点与其他节点直接或间接联系的紧密程度，但是这一概念只考察了最近邻和次近邻的影响，没有考虑到邻居间的联系对控制力的影响，最终导致无法发现一些重要的“桥节点”。

为了解决大多数关键节点发现算法没有兼顾桥节点与其他类型关键节点，造成评价结果只能发现某一类的片面性问题，本文提出一种优化结构洞的关键节点发现方法，借鉴结构洞理论并将其运用于无向加权网络，综合考虑了节点的邻居数量及其与邻居间的拓扑结构，并通过定义节点的邻接度和二次邻接度来衡量其邻居节点对其的重要程度，通过计算对邻居节点投入时间（精力）占其总时间（精力）的比值，并测量网络中的“结构洞”约束系数，以此来发现网络中处于重要位置的关键节点。

1 无向加权网络拓扑图模型

在加权复杂网络中，边权的定义方式一般遵循两种原则：相异权和相似权。相异权与相似权表示方法恰恰相反，相异权的定义与传统意义上的距离表示相似，即边权重越小则表示两节点之间的距离越小，关系越紧密；而相似权的定义则恰恰相反，即边权重值越大则表示两节点的关系越紧密。本文提出的基于优化结构洞的关键节点发现方法是在相似权的原则下进行的。

图1给出无向加权网络的模型及符号表示：设网络模型[G=（V，E）]是一个无自环的无向加权网络，其中[V]是网络中节点的集合， [V={v1，v2，…}，vi∈V]；[E]是边的集合，[E={e1，e2，…}]，其中[N=V]，[W=E]。网络的邻接矩阵为[A=（aij）N×N]，对于本文中的无向加权网络来说，其邻接矩阵是一个对称矩阵，若节点[i]与节点[j]直接相连，则[aij=w（i，j）]，否则[aij=0]，其中[w（i，j）]表示节点[vi]与[vj]相连的边的权值。对于无向加权网络而言，定义节点的强度为节点连边的权值之和即[wi=j=1Naij]。

2 优化的结构洞关键节点发现算法

无向加权网络从结构角度考虑属于非同质拓扑结构，这就决定了网络中每个节点的重要程度是不同的。对于无权网络只反映了网络的拓扑关系和节点的连接方式，并不能准确描述节点间相互作用的强弱程度，在现实生活中一些网络的节点之间存在着强弱关系，因此，本文基于无向加权网络模型，提出了一种优化的结构洞关键节点发现方法。

2.1 相关定义

网络节点[i]的网络约束系数定义为：

[Ci=j∈Γ（i）pij+qpiqpqj2] （1）

式中：[q]为连接节点[i]和節点[j]的间接节点；[pij]为节点[i]花费在节点[j]上的时间占其总时间的比例。[pij=zijj∈Γ（i）zij-1]，[zij]指节点[i]和节点[j]之间的连接强度，但是该方法没有考虑邻居间的联系对控制力的影响，导致无法发现一些处于重要位置的桥节点。

本文基于结构洞理论，提出一种针对无向加权网络关键节点发现的优化方法，相关的定义如下：

定义1 设无向加权网络的通信特征为[（f1，f2，…，fn）]，其中边权定义：

[aij=w（i，j）=（α1，α2，…，αn）（s1，s2，…，sn）] （2）

式中：[sn]为两节点通信特征为[fn]的通信频率；[αn]表示通信特征为[sn]的权重。

在传统的结构洞理论中，并没有对边权进行定义，本文考虑到在复杂网络中，节点之间的每次通信或者联系所产生的价值可能不同，因此对两个连接节点之间的边权进行定义。例如在微博网络中，节点之间可以通过转发、私信、评论等进行通信，但是不同的通信特征在两节点间发生联系时所表征出来的紧密度或者亲密度是不同的；同样在邮件网络中，邮件收发双发通过回复、发送、抄送、密送所体现出来的紧密度关系也是不相同的。

定义2 网络节点[j]的邻接度为：

[Qj=m∈Γ（j）km] （3）

式中：[Γ（j）]是节点[j]的邻居节点的集合，[k（m）]是节点[m]的加权值。为了表征节点与邻接节点之间连接的紧密性，本文与传统方法一样定义了网络节点的邻接度。节点[j]的邻接度为与节点[j]直接相连的所有邻居节点的强度值之和。

定义3 网络节点[i] 的二次邻接度为：

[Ni=j∈Γ（i）Qj] （4）

为了反应节点在网络中的拓扑关系，本文定义了节点的二次邻接度，其中节点[i]的二次邻接度为和节点[i]直接相连的所有邻居节点的邻接度之和。

定义4 节点[j]相对于节点[i]的相对重要程度：[pji=QjNi， j∈Γi， jpji=1] （5）

为了反映节点间邻居关系对控制力的影响，定义了相对重要度。其中与节点[i]直接相连的节点[j]相对于节点[i]的相对重要度，反映了节点[i]对节点[j]所投入的时间或者精力占节点[i]对其所有邻居节点投入的总时间或者精力的比例。若节点[i]的一个邻居节点[j]与一个度值很大的节点[m]直接相连，这就意味着节点[m]的初始重要性较高，则节点[i]期望投入节点[j]的时间或者精力就较大，即人们总期望对有重要关系的人投入更多的精力和时间。

定义5 每个节点在网络中的重要性：[D（i）=jp（j|i）+qpqipjq2， i≠q≠j] （6）

本文采用定义4 中所定义的[pji]来取代“结构洞”约束系数中的[pij]，即节点[i]对邻居节点[j]投入的时间（精力）占其总时间（精力）的比例用其邻接度和二次邻接度的比率来替代，一个直观的思想是如果节点[i]的邻居节点[j]有更好的社会关系[m]，[m]为节点[i]的次邻节点，那么对于节点[i]和节点[m]之间的共有节点[j]；由于[j]有更好的社会关系[m]，则节点[i]更倾向于对节点[j]投入更多的时间（精力），以期获取更多的回报，这和现实生活中的人们之间的交往也相符合。

2.2 算法描述

利用上述理论分析，基于优化的结构洞关键节点发现方法描述如下：

算法描述：

1.For 1：N

2.计算[aij=w（i，j）=（α1，α2，…，αn）（s1，s2，…，sn）]

3.Input 无向加权网络的邻接矩阵[A=（aij）N*N]

4.计算[wi=j=1Naij]

5.Delect[m]when [k（m）]=0

6.计算 Q（[i]）

7.计算 N（[i]）

8.计算[pji=QjNi]

9.计算[D（i）=jpji+qpqipjq2]，[i≠q≠j]

10.Select top?4 or top?10 from D（i）

11.end

3 实验分析

为了验证本文提出的基于优化结构洞的关键节点发现方法可有效、准确发现网络中处于重要位置的关键节点，且适用于大规模真实网络，采用APRA（Advanced Research Project Agency）网络数据集和安然公司邮件往来数据集进行验证。

3.1 小规模网络数据集实验

为了进一步证明该优化算法的有效性和准确性，本文使用如图2所示的ARPA网络拓扑结构，它由21个节点和23条边组成，对ARPA网络进行边赋权得到的无向加权网络，其中默认节点之间通行特征只有一个。并给出了该网络的基于改进结构洞的关键节点发现排序结果如表1所示。

从表1中得到top?4的关键节点分别为14，3，6，12，为了证明该算法的有效性和可行性，表2和图3给出了与其他三种算法相比较的结果。

表2给出本文中提出的算法以及采用度中心性、介数、接近度等方法确定的关键节点发现的排序结果。结果四种算法得出的处于重要位置的关键节点排序都略有差异，主要是因为各自的判断侧重点不同。在基于度中心性的关键节点发现算法中，排名前4位的关键节点分别为2，3，14，15，由图2可看到这些节点皆为网络中节点强度较大且与邻居节点连接最为紧密频繁的一类节点；在基于邻近度的方法中，排名前4位的关键节点为8，9，10，7，结合图2和表1可知该类节点强度较低，网络约束系数较大；在基于burt的方法中，排名前4的关键节点分别为3，6，12，19，但是其中6，12，19的网络约束系数是相同的，无法进一步判断这三个节点的重要程度；在基于介数的关键节点发现方法中，关键节点为处于桥接处的一类节点，忽略了其他类型的节点；在本文提出的方法中，排名前4位的关键节点分别为14，3，6，12，其中包括节点强度较大的14，3节点和处于桥连接位置的6节点和其他关键节点12。

为了进一步验证该算法优于其他四种算法。图3给出了采用上述五种方法得到的ARPA网络关键节点重要性排序后删除前4个关键节点后的情况。其中本文中的改进算法删除前4个关键节点后，ARPA网络被独立地划分为6个社团，说明本文的算法很好地计算出了ARPA网络的关键节点；图3中使用基于度中心性[4]、burt[9]、介数和接近度[2]算法删除前4个关键节点后将网络分为5个独立的社团，在接近度算法中删除前4个关键节点之后网络被划分为1个独立的社团，对比实验结果说明本文提出的算法在对ARPA网络中的关键节点发现中要优于其他算法。

3.2 大规模真实复杂网络实验

本文实验选用的数据集是FERC在2003年公开的安然邮件语料库，该数据集为 1999—2002年间安然公司内部成员邮件收发情况，由151个节点，517 435条边构成的复杂网络。为了便于后续的实验分析，现需要对安然邮件数据集进行预处理：删除无效数据，例如noaddress@enron.com、非规范格式邮箱地址；将邮箱地址进行映射转换，给每个邮箱账号赋予一个连续但不重复的整数；去除重复邮件、收发为同一账号的邮件；邮件分为密送、回复和发送三个通信特征。

为了证明该算法适用于大规模复杂网络和实验结果的有效性，表3给出了该算法的关键节点评价结果。

从表3的排名和对应的职位可以看出，本文提出的算法得到的结果都是职位很高，在公司掌握最新消息或者是与外界联系较为频繁的活跃者，其中，前3名表征了该节点活跃度相对不高，但是在公司的职位较高，这符合关键节点的特征，Mike Grigaby为Manager，作为管理者需要经常与员工和上司沟通，且是联系公司上下层的桥梁；对于职位是Employee的Kay Mann而言，因为其活跃度相对较高，被视为关键节点，结合结构洞原理，可推测该员工近期可能会升职。

下面是对算法的时间复杂度进行分析比较。优化结构洞的关键节点发现方法与其他方法相比对网络中关键节点的发现非常有效，因为它使用了更多的信息，而且比介数计算有更低的复杂度。由于本文中提出的基于优化结构洞的關键节点发现方法的时间复杂度主要集中在“结构洞”约束系数的计算上，若采用标准的矩阵乘法，算法复杂度为[O（n3）]。但对于大部分复杂网络来说，其邻接矩阵往往是稀疏矩阵，如果不考虑其他优化算法，仅采用稀疏矩阵存储复杂网络，则“结构洞”的主要运算为[qpiqpqj]，而计算此式的稀疏矩阵乘法的算法复杂度为[O（n2+m2n）]，其中[n]为网络中顶点的个数，[m]为网络中边的数量。由于[m]可能的最大值为[n2]，因此有[m2n=mmn≤m（n2n）=mn]。对于加权图有[n

4 结 语

在无向加权网络中，对处于重要位置的关键节点进行评估发现对于研究网络的抗毁性和后续社团发现等都具有十分重要的意义。针对目前关键节点发现算法大多数没有兼顾桥节点与其他类型重要节点，造成评价结果只能发现某一类的片面性问题，本文借鉴结构洞理论中网络约束系数评价方法，结合无向加权网络，利用节点之间的通信特征定义边权。通过节点的邻居数量及其与邻居间的拓扑结构，定义节点的邻接度和二次邻接度来衡量其邻居节点对其的重要程度。考虑到邻居间的联系对控制力的影响，提出节点相对重要性的定义。实验分析表明该方法能够准确、有效地发现无向加权网络中的关键节点，且算法的时间复杂度小于[Onm]，具有很强的实用性。该算法通过局部特征进行关键节点发现，克服全局法应用的局限，无需对网络全局架构进行了解，适用于大规模复杂网络中。

参考文献

[1] LANDHERR A， FRIEDL B， HEIDEMANN J. A critical review of centrality measure in social networks [J]. Business & information systems engineering， 2010， 2（6）： 37l?385.

[2] HE N， LI D， GAN W， et al.Mining vital nodes in complex networks [J]. Computer science， 2007， 34（12）： 1?5.

[3] 梁鲁晋.结构洞理论综述及应用研究探析[J].管理学家（学术版），2011（4）：52?62.

[4] REN Z， SHAO F， LIU J， et al. Node importance measurement based on the degree and clustering coefficient information [J]. Acta physica Sinica， 2013， 62（12）： 1289011?1289015.

[5] ZHU T， ZHANG S， GUO R， et al.Improved evaluation method for node importance based on node contraction in weighted complex networks [J]. Systems engineering and electronics， 2009， 31（8）： 1902?1905.

[6] WANG J， WU X， LIAO W， et al.Improved method of node importance evaluation in weighted complex networks [J]. Computer engineering， 2012， 38（10）： 74?76.

[7] 张立晓，徐汀荣，李海彦，等.一种基于局部特性的重要邮箱用户发现方法[J].计算机应用与软件，2013，30（3）：51?54.

[8] 王建伟，荣莉莉，郭天柱.一种基于局部特征的网络节点重要性度量方法[J].大连理工大学学报，2010，50（5）：822?826.

[9] BURT R S. Structural holes： the social structure of competition [M]. Cambridge， Mass： Harvard University Press， 1992.