基于精准k核的复杂网络节点重要性评估方法

卢鹏丽, 许星舟

(兰州理工大学 计算机与通信学院, 甘肃 兰州 730050)

复杂系统存在于现实生活中的各个领域.为了更好地研究事物间的联系，人们对复杂系统进行抽象，并将得到的理想模型称为复杂网络.其中网络中的实体对象被抽象为节点，实体对象之间的显性或隐性关系被抽象为边[1].伴随着全球数字化进程加快，人们在计算机、通信、刑侦、社会、金融、交通、生物等诸多领域中都抽象出了复杂网络，并吸引了大量相关领域的研究[2].关键节点是构成一个网络并实现其信息传递功能的核心要素，因此识别关键节点一直是复杂网络研究中的热门课题.研究发现，保护关键节点既可以提升网络的抗毁性，也可以从关键节点入手提出更高效的网络攻击策略[3].通过对交通网络进行关键节点识别，可以找到网络中易拥堵的路段，积极改善这一问题，能够促进智慧交通的建设[4].通过对恐怖分子网络进行关键节点识别有助于发掘潜藏的恐怖分子头目首领，从而捣毁整个犯罪网络，促进地区的和平稳定[5].通过对神经网络进行关键节点识别能够找到神经信号传递时的关键神经元，从而提升瘫痪类疾病的治愈效果[6].

为了识别关键节点，人们提出了一系列的节点中心性评估指标来衡量节点的重要性.其中最常见的经典指标包括：度中心性(degree centrality)[7]、介数中心性(betweenness centrality)[8]、k核(k-shell)[9]、H指数中心性(H-index centrality)[10]等.度中心性是最简单基础的节点评估指标，直观反映了节点拥有的邻居数量.介数中心性是根据经过节点的最短路径数量占网络中所有最短路径数量的比例来衡量节点在网络中的重要程度.k核采用类似剥洋葱的方式，根据度中心性由小到大的顺序依次剥离网络中的节点，再按照节点被剥离的先后次序来确定其重要性.H指数中心性由学术成就的评估指标H指数演化而来，能够利用邻居节点的信息来评估节点在网络中的影响力.然而，在实际应用中都存在不同程度的局限性[11].例如：度中心性由于忽略了局部特征和全局结构，从而导致识别关键节点的准确性较低;介数中心性需要找出整个网络中所有的最短路径,导致时间复杂度较高,难以适用于大规模网络;k核在节点剥离过程中会破坏整个网络结构信息;而H指数中心性只考虑到邻居节点的影响力,却忽视了节点自身的信息.为了消除这些局限性，人们结合节点的局部特征信息或全局拓扑结构信息提出了一些新的节点评估指标，例如：邻域核心度(neighborhood coreness)[12]、重力中心性(gravity centrality)[13]、局部DH中心性(local DH-index centrality)[14]和改进的k核(improvedk-shell)[15]等.

本文基于k核分解的核心思想提出了精准k核(accuratek-shell,Ak).该指标重新定义了节点的k核划分规则，能够将原本属于同一k核的节点按照剥离次序对其进行量化区分.然而精准k核在节点剥离过程中依然会破坏网络的结构信息并且忽视了邻居节点的影响力.为了更加充分地考虑节点局部特征和网络整体拓扑结构对节点的影响，本文将精准k核应用到近年来较为热门的重力中心性中提出了精准重力中心性(accurate gravity centrality,AGC)，以此来消除精准k核的局限性.此外，出于对节点重要性多元评估的目的，本文引入了信息学中的香农熵，结合节点的邻域度熵、邻域精准k核熵以及精准重力熵,最终提出了混合中心性(mixed centrality,MC).通过对度中心性、介数中心性、k核、邻域核心度、重力中心性、H指数中心性、局部DH中心性、改进的k核和混合中心性在7种真实网络下进行了一系列性能实验，实验结果表明,本文提出的混合中心性在单调性和精准性方面性能均优于其他节点评估指标.

1 相关算法定义及本文算法

任何由复杂系统抽象得到的复杂网络都可以由简单无向图G=(V,E)来表示，其中V是实体对象的集合对应网络中的节点集，E是实体对象之间相互联系的集合对应网络中的边集.A代表网络的邻接矩阵，当节点i与节点j之间存在连边时，则Aij=1，否则Aij=0.

1.1 相关研究

以下是本文中所涉及到的节点评估指标，在后续的实验部分中将对这些指标进行单调性和精准性的对比实验.

1) 度中心性(degree centrality)

度中心性[7]是衡量节点重要性最基础的指标，定义为与节点相连边的数量或节点的邻居节点数量.节点的度越大，则可以传播信息的渠道和对象越多，其自身的重要性也越高.节点i的度中心性可以表示为

(1)

其中:N是网络中节点的总数.

2) 介数中心性(betweenness centrality)

介数中心性[8]是一种全局指标，能够反映一个节点作为交通枢纽的重要程度.通过计算经过节点的最短路径数量在整个网络最短路径数量的占比来评估节点的重要性，其公式为

(2)

其中:σst代表节点s和节点t之间所有最短路径的数目;σst(i)表示网络中所有最短路径中经过节点i的路径总数.

3)k核(k-shell)

k核是Kitsak等[9]提出的一种基于位置信息来评估节点重要性的指标，其基本思想为：首先设置ks=1，即将网络中所有度中心性为1的节点视为重要性最低的节点进行剥离.检测剥离后的子网络中是否仍然存在度中心性为1的节点，如果仍然存在则继续剥离直至子网络中不再存在度中心性为1的节点，此时已被剥离节点的k核值即为1.随后设置ks=2，再将网络中所有度中心性为2的节点进行剥离，循环往复直到所有节点都被分配到k核值.k核能够通过网络中节点被剥离的次序对节点进行评估，越是最后被剥离的节点其k核越大，节点的重要性越高.

Baus等[12]在k核中心性基础上充分考虑了节点局部的重要性,提出了邻域核心度(neighborhood coreness)，将邻居节点的k核之和作为评估其重要性的指标，其公式为

(3)

其中:Neii表示节点i的邻居节点集;ks(j)代表节点j的k核.

4) 重力中心性(gravity centrality)[13]

受牛顿重力公式的灵感启发，Ma等[13]将网络中的节点类比成为天体行星，将节点的k核类比为行星的质量，将节点之间的最短距离类比为行星之间的距离，从而计算节点间的相互影响力，其公式为

(4)

其中:ks(i)代表节点i的k核;φi代表距离节点i的距离不超过3的节点集;dij代表节点i到节点j之间的距离.

重力中心性是指节点从邻居节点处受到的相互影响力之和，其公式为

(5)

其中:Neii表示节点i的邻居节点集.

5)H指数中心性(H-index centrality)

H指数是学术界中普遍用于评估学者学术成果的指标，Korn等[10]将其思想推广到了复杂网络当中并提出了H指数中心性，其定义为

Hindex(i)=H(dj1,dj2,…,djn)

(6)

其中:n是节点i的度;(j1,j2,…,jn)是节点i的邻居节点集;(dj1,dj2,…,djn)是其邻居节点的度集.函数H(dj1,dj2,…,djn)的最终返回值为y，并使得邻居节点的度集中有y个值大于等于y.

Lu等[14]通过将度中心性和H指数中心性结合的方式提出了局部DH指数中心性，其定义为

DHindex(i)=αDC(i)+βHindex(i)+

(7)

其中:DC(i)代表节点i的度中心性;Hindex(i)代表节点i的H指数中心性;Neii表示节点i的邻居节点集；α=β=0.15.

6) 改进的k核(improvedk-shell)

Wang等[15]通过将信息学中的香农熵引入复杂网络中对k核进行了改进.根据节点熵的大小对k核中每一层元素进行排序，从而得到网络中节点的重要性序列.其节点的度熵定义为

其中:DC(i)代表节点i的度中心性;N代表网络中节点的个数;Neii代表节点i的邻居节点集.

1.2 本文算法

本文提出了一种识别复杂网络中关键节点的评估指标混合中心性.该方法首先改进了k核的分解过程，大幅提升了k核识别关键节点的精准度.其次，将改进后的k核应用到重力中心性中，弥补了其忽视节点局部特征和网络整体拓扑结构的不足.考虑到单一指标在评估节点时产生的片面性，本文引入了信息学中的香农熵并对节点的邻域度中心性、邻域精准k核以及精准重力中心性进行了归一化处理.最后，通过将这三种熵结合来实现对节点的多元化评估.

1) 精准k核(accuratek-shell)

基于k核分解法的思想，本文认为网络中越早被剥离的节点重要性越低，即使拥有相同k核的节点也应该根据剥离次序进行评估区分.本文提出了一种可以根据节点剥离次序逐层量化k核的方法，其核心思想为：默认初始ks=1，统计ks每次变动前一共经历了多少次剥离过程.假设ks=1到ks=2期间一共经历了N次剥离过程，那么最先剥离的节点的k核为ks=1+0/N，第二次被剥离节点的k核中心性为ks=1+1/N，依此类推，最后一次被剥离节点的k核为ks=1+(N-1)/N.

根据图1所示，精准k核分解法能够对网络进行更加细致的划分，使处于同一k核的元素得到区分.而由表1可知，k核只能将网络区分为3个重要性等级，而精准k核能够在此基础上进行细分并最终得到8个重要性等级.相较于传统的k核分解，精准k核分解能够将更多的节点细分量化，在识别关键节点的准确性上性能更优秀.尽管如此，精准k核依旧忽视了节点的局部特征信息和全局结构信息.

图1 精准k核对网络节点的分解Fig.1 Accurate k-shell decomposition of network nodes

2) 精准重力中心性(accurate gravity centrality)

重力中心性是基于k核提出的一种节点评估指标，而由于精准k核在识别关键节点的性能优于k核，因此本文将精准k核应用到重力中心性中对其进行改进.其节点间的精准相互影响力为

(10)

其中:Ak(i)代表节点i的精准k核;φi代表距离节点i的距离不超过3的节点集;dij代表节点i到节点j之间的距离.

精准重力中心性定义为节点i与邻居节点间的精准相互影响力之和，其公式为

(11)

其中:Neii表示节点i的邻居节点集.

3) 邻域中心性(neighbourhood centrality)

精准重力中心性和邻域核心度都是将邻居节点的重要性之和作为衡量自身重要性的新指标，这种方法能够充分考虑到局部特征信息对节点重要性的影响.基于这种思想，本文提出了邻域度中心性和邻域精准k核两种新的节点评估指标，其公式为

其中:Neii表示节点i的邻居节点集.

4) 香农熵(Shannon entropy)

香农熵在复杂网络中具有良好的拓展性，将香农熵公式中事物出现的概率替换成节点的重要性，有助于从信息学角度对节点进行评估分析.在信息论中，香农熵是衡量信息不确定性的指标，熵值越大则说明这条信息的不确定性越高，理解成本越高.而在复杂网络中，节点的熵值越大则说明节点在网络中的影响力越大.假设节点的邻域度重要性为

则节点的邻域精准k核重要性和邻域精准重力重要性分别为

其中:DCnei(i)代表节点i的邻域度中心性;Aknei(i)代表节点i的邻域精准k核;AGCnei(i)代表节点i的精准重力中心性;N代表网络中节点的个数.则节点的邻域度熵、邻域精准k核熵和精准重力熵分别为

其中:Neii表示节点i的邻居节点集.

5) 混合中心性(mixed centrality)

通过结合邻域度熵、邻域精准k核熵和精准重力熵，本文提出了混合中心性，其公式为

MC(i)=EDCnei(i)+EAknei(i)+EAGCnei(i)

(17)

混合中心性中所涉及的邻域度中心性、邻域精准k核和精准重力中心性中包含了节点的拓扑结构信息、位置信息、局部特征信息和网络整体拓扑结构信息.利用香农熵对这三种指标进行归一化处理再结合，不仅能将这些信息充分融合，还能确保节点均衡地受到这三种指标的影响.此外，还可以消除单一指标评估节点时产生的片面性，从而达到多元化评估的目的.

2 实验数据与评估方法

2.1 数据集

为了测试本文所提出的节点重要性评估指标的性能，选取了7种真实网络数据集：海豚社交网[17]、美国大学生足球俱乐部网(Football)[18]、政治图书网(Polbooks)[19]、爵士乐网(Jazz)[20]、美国航空运输网(USAir)[21]、大学生电子邮件网(Email)[22]和仓鼠网(Hamster)[23].

表2反映了各个网络的详细信息，介绍了网络的节点数(|V|)、边数(|E|)、节点平均度数(Ave degree)、网络中节点最大度数(Max degree)、阈值(βth)、感染率(β)和同配系数(Assortativity).

表2 真实网络数据集的属性

2.2 SIR模型

SIR模型的抽象概念源自于对传染病的研究，当今学者将其广泛应用于传染病动力学和信息传播学中来发现具有较大影响力的人，以此来抑制传染病扩散和终结谣言[24-27].SIR模型分别由S、I、R三种状态持有者构成，分别为：

1) 易感者(Susceptibles)：免疫力低下，极易被病毒侵染.

2) 感染者(Infectives)：病毒携带者，已经被病毒侵染，有几率将病毒传播给周围人.

3) 康复者(Recovered)：已康复的感染者，体内已经产生了抗体，不会再受该病毒影响.

在初始阶段，整个网络中仅有一个感染者，其余均为易感者.每间隔一段时间感染者节点都会以β的传染概率向其邻居节点的易感者传播病毒.同时，感染者也都会获得θ=2β的康复率，康复后的感染者不会被再次感染.传播过程将持续到网络中不再有感染者节点时停止，将传播期间每个节点成功传染的节点数作为该节点的重要性.为了确保实验数据精准，消除SIR模型在传播过程时产生的随机性，本文分别对表2中的7个真实网络进行1000 次SIR病毒传播实验，并取其平均值作为节点在网络中的真实重要性.

2.3 评估方法

在测试节点重要性评估指标的性能时，学者们通常采用M单调函数[28-29]和肯德尔相关系数[30-32]这两种方法.其中，M单调函数能够反应节点评估指标对网络中节点重要性的区分能力，肯德尔相关系数能够衡量节点评估指标的准确性.

1)M单调函数

M单调函数能通过计算节点重要性序列中相同元素的比例来衡量节点评估指标的性能，其公式如下：

(18)

其中:R表示由节点评估指标得到的节点重要性序列;r表示节点重要性序列中的元素;N表示节点重要性序列中元素的数量;Nr表示节点重要性序列中元素r的数量.M的取值范围为[0,1]，M的值越大则说明评估指标能够区分的节点越多.当M=1时，说明网络中所有的节点都能够得以区分；而当M=0时，说明网络中所有的节点都具有相同的重要性，无法区分.

2) 肯德尔相关系数

假设X与Y是元素数量均为R的两个集合，分别从两个集合的第i个位置和第j个位置取出元素并构成数据组，即(xi,yi)和(xj,yj).当xi>xj且yi>yj或者xiyj或者xi>xj且yi

(19)

其中:RT和RF分别表示一致组和非一致组的数量.肯德尔相关系数的取值范围为[-1,1].当τ=1时，说明两个集合中元素的等级相关性相同；当τ=-1时，说明两个集合中元素的等级相关性相反；当τ=0时，则表示这两个集合中的元素相互独立.

3 实验结果分析

本节中，将提出的节点评估指标MC与其他节点评估指标进行单调性和相关性的对比来验证其性能.本文选择度中心性(DC)、介数中心性(BC)、k核(ks)、邻域核心度(NC)、重力中心性(GC)、H指数中心性(H)6种常见的节点评估指标作为传统对照组.此外，还选择了两种近期提出的性能优秀的节点评估指标作为新阶对照组，分别是局部DH指数中心性(DH)和改进的k核(Iks).

3.1 单调性比较

表3中的数据反映出了各个节点评估指标在7种真实网络下的M单调性，实验结果表明，由于MC和GC都考虑到了网络的整体拓扑结构信息，因此都具备优秀的节点区分能力.其中MC仅在爵士乐网中略低于传统对照组中GC的单调性，在剩下6种网络中其单调性都达到了最大值.此外，MC在大学生足球俱乐部网、政治图书网和大学生电子邮件网中的单调性都达到了0.999 9，明显高于新阶对照组的两个指标.而ks由于算法特性的原因在各个网络中区分节点的性能普遍较差.

表3 不同指标在7种真实网络中的M单调性

3.2 相关性比较

表4汇总了7种不同规模的真实网络在特定感染率β下各个节点评估指标的肯德尔相关系数.实验数据表明,在新阶对照组中只有Iks在美国航空运输网络中取得了最佳性能，而在大学生足球俱乐部网络传统对照组中的NC取得了最好性能.其中由于BC的算法局限性导致其几乎在所有的网络中都取得了最差的结果.MC在其中的5种网络中都表现出了最佳的性能，尤其是海豚社交网络中τ(MC)=0.950 8,远超其余对比节点指标的肯德尔相关系数.然而同样具有优秀节点区分能力的GC在评估节点的准确性上却不及MC，这证明了多元化评估思想的先进性，也反映出MC具备精准评估节点重要性的能力.

表4 7种不同规模真实网络中的肯德尔相关系数τ

为了更好地验证MC识别关键节点的性能，消除特定网络阈值对实验结果的影响，本文从政治图书网、爵士乐网、大学生电子邮件网和仓鼠网的阈值附近均匀地取出10个数据作为感染率，对不同感染率下SIR病毒传播模型中各个节点评估指标的准确性进行了研究.如图2所示，在这4种网络中起初感染率β较小时，MC并未表现出较好的节点评估性能.随着感染率β逐渐增大,MC的节点评估性能开始变得越来越好.尤其是当感染率β接近乃至大于网络阈值时，可以发现MC的性能明显优于其他节点评估指标，这表明MC更能精准有效地评估网络中节点的重要性.

图2 真实网络在不同的感染率β下的节点重要性与各节点评估指标的肯德尔相关系数

此外，本文还研究了构成MC的三种熵对算法整体的贡献，熵的肯德尔相关系数越大则代表该熵对MC的贡献越大.通过观察图3中海豚社交网和美国大学生足球俱乐部网的邻域度熵、精准k核熵和精准重力熵的肯德尔系数，可以发现邻域度熵在感染率β较小时具有更高的准确性，精准重力熵的准确性较差.而当感染率β接近或大于阈值时精准重力熵能够取得较高的准确性.在政治图书网中邻域度熵和精准k核熵都表现出了较高的准确性，精准重力熵的节点识别准确性相对较弱.在大学生电子邮件网中，精准重力熵在初始阶段表现出了较高的准确性，在感染率β接近阈值时被邻域度熵和精准k核熵的准确性超越.由此可见，不同网络中三种熵对算法整体的贡献各不相同，其中邻域度熵和精准重力熵的贡献较为突出，精准k核熵的贡献较弱.然而相较于构成MC的三种香农熵而言，MC在不同规模真实网络中的大多数情况下都能取得最高的肯德尔相关系数，这表明MC有效消除了单一指标评估节点时的片面性，提升了自身的算法性能.

图3 真实网络在不同的感染率β下的混合中心性与其组成部分的肯德尔相关系数 Fig.3 The node importance of real networks under different infection rate β and correlation coefficient τ of the mixed centrality and its components

4 结论

关键节点的识别能够促进人们对网络的认识，在诸多领域都具有重大意义，而如何精准有效识别网络中的关键节点一直是复杂网络领域中的一大难题.本文首先在k核分解思想的基础上提出了一种精准k核中心性Ak，并将其应用到重力中心性中提出了精准重力中心性AGC，通过结合邻域度中心性、邻域精准k核中心性以及精准重力中心性三者的香农熵最终提出了混合中心性MC.在7种不同的真实网络下，通过对MC与几种流行的节点评估指标进行了单调性和精准性对比实验，数据表明MC具备更优秀的关键节点识别能力.在后续的研究中，可以将精准k核应用到更多基于k核提出的指标中对其进行改进.