基于度与H指数扩展的复杂网络节点排序方法

卢鹏丽, 于 洲

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

在现实生活中,有很多网络都是以复杂网络(complex network)的形式存在,例如社交网络、交通网络、生命科学领域的各种网络等.复杂网络中识别有影响力的节点作为网络科学的重要研究内容之一,己经被应用到诸多领域,特别在各类传播行为(如病毒式营销[1]、流行病传播与控制[2]、社交网络分析[3])的研究中表现得尤为重要.

所谓有影响力的节点是指相比于网络中其他节点能够对网络的连通性、鲁棒性、平均距离以及同步等产生重要影响力的一类特殊节点.当一些有影响力的节点受到攻击破坏时,会影响到网络的整体结构和功能.因此,如何识别网络中有影响力的节点己成为近年来的热点问题.

国内外学者对节点影响力的评估进行了大量研究,己经有很多用于识别节点影响力的中心性指标,如度中心性[4]、介数中心性[5]、紧密中心性[6]、K-shell中心性[7]、H指数中心性[8]和聚类系数[9]等.度中心性是目前最简单的一种评估方法,该方法通过计算邻居节点的数量来衡量其影响力,即节点的邻居节点越多,其影响力越大.然而,该方法虽然简单直观,相关算法的时间复杂度也很低,但只考虑了节点的局部属性,因此具有一定的局限性.介数中心性和紧密中心性都是全局中心性方法,它们都需要遍历整个网络来确定节点的影响力,时间复杂度较大,因此全局中心性方法效率较低,不适合于大型的复杂网络.H指数中心性虽然考虑了相邻节点的影响力,但却忽略了自身的度以及网络上部分结构信息.

如果只考虑节点本身的重要性来确定其中心性,则可能忽略网络上的部分结构信息,降低了识别网络中节点影响力的准确性.例如,对于图1网络中的一些节点,本文通过SIR模型取1 000次传播过程的平均值作为节点的影响力(SC),根据网络节点SC值可知节点5的影响力大于节点10,然而,节点5和节点10的度都是6,即其度中心性都是6.出现这种情况的原因在于节点5的相邻节点比节点10的相邻节点具有更大的影响力.

H指数是赫西(Hirsch)[10]在2005年提出的,是用于衡量学者出版物的数量和引文影响的一个经典指标.近年来,有学者引入H指数来衡量网络中节点的影响力.例如,Li等[11]验证了H指数在许多现实世界网络中衡量节点影响力的有效性.然而,在一些网络中用H指数中心性识别网络中节点的影响力时,存在着一些节点具有相同的H指数值,但这些节点的真实影响力却不同.如图1,节点5和节点9的H指数值均为4,但节点9的真实影响力(SC)却大于节点5,其主要原因在于计算节点H指数值时,忽略了邻居节点中度较小的节点以及自身的度,这使得H指数中心性无法区分这些节点的真实影响力.

本文在H指数与度中心性的启发下,提出了一种基于度与H指数扩展的局部中心性方法来识别网络中节点的影响力,称之为局部DH指数中心性.该方法同时考虑了节点自身的度、H指数和邻居节点的H指数三个因素.一方面,一个节点的H指数取决于邻居节点的度;另一方面,其邻居节点的H指数取决于邻居节点的邻居的度.本文通过病毒传染模型(SIR)以及单调函数M来评价局部度与H指数中心性在识别节点影响力方面的性能.实验结果表明,较一些常用的中心性方法,本文的方法在一些实际网络以及无标度网络(BA)中能更有效地识别节点的影响力.

1 相关研究及本文算法

实验中要用到五种经典的中心性指标,即度中心性(DC)[4]、介数中心性(BC)[5]、紧密中心性(CC)[6]、K-shell中心性(Ks)[7]以及H指数中心性(H)[8].

假设每个网络都可以表示为G=(V,E),其中节点集V={v1,v2,…,v|V|}表示个体,边集E={e1,e2,…,e|E|}表示个体与个体之间的关系.如果两个节点vi和vj之间有关系,则eij=1,否则eij=0.di表示节点vi的度,为其邻居节点的个数,这些邻居节点的集合由Ni表示,各中心性指标介绍如下.

1.1 度中心性

在网络中节点vi的度是指在网络中与节点vi直接相连的节点个数,节点的邻居节点越多,节点越重要.节点vi的度中心性为

(1)

式中:N表示网络中的节点总数.

1.2 介数中心性

在网络中节点vi的介数中心性是指网络中所有最短路径中经过节点vi的路径总数占所有节点对的最短路径总数的比例,因而在运行此算法时需要遍历整个网络.节点vi的介数中心性为

(2)

式中:Ljk是指每一对节点vj与vk之间的最短路径数;Ljik是指节点vj与vk最短路径中经过节点vi的路径总数.

1.3 紧密中心性

在网络中节点vi的紧密中心性值是节点vi到网络中其他节点的最短路径长度的倒数之和,因而在运行此算法时需要遍历整个网络.节点vi的紧密中心性为

(3)

式中:dij表示节点vi与vj之间的最短路径长度.

1.4 K-shell中心性

K-shell中心性是根据节点的位置度量节点影响力.K-shell分解算法通过迭代删除节点,给网络中所有节点赋予K-shell值.算法思想如下：

1) 首先,从图中删除所有度为1的节点以及相关的连边,若剩下的节点里,仍有度值为1的节点,则继续上述过程,直到图中所有节点的度值都大于1,然后,将所有删除的节点的K-shell值记为1.

2) 删除度为2的节点,直到没有度为2的节点.然后将所有删除的节点的K-shell值记为2,这个过程一直持续到所有节点都删除为止.显然,K-shell值越大的节点越接近网络的中心位置,节点影响力越大.

1.5 H指数中心性

H指数中心性是利用H指数的概念,通过考虑邻居节点的度来确定节点的中心性.节点vi的H指数中心性为

H-index(vi)=H(du1,du2,du3,…,dudj)

(4)

式中:(u1,u2,u3,…,udj)为节点vi的邻居节点;dui表示节点ui的度;函数H(du1,du2,du3,…,dudj)返回值y,使得du1,du2,du3,…,dudj中有y个值大于等于y.

除了上述方法外,近来学者还提出了一些新方法.Hu等[12]试图通过同时使用多个中心性指标来确定节点的影响力,Wang等[13]提出了一种混合的中心性度量方法用于描述多层网络中节点的影响力,Wang等[14]提出了衡量加权图中节点影响能力的方法,Fu等[15]提出了一种基于模量密度谱优化的中心性度量方法.

本文考虑了度中心性与H指数中心性在识别网络中节点影响力的局限性,并在此基础上提出了局部DH指数中心性.

1.6 局部DH指数中心性

由式⑷可知,H指数中心性通过考虑邻居节点的度来确定节点的中心性,但忽略了邻居节点的部分信息,例如完全忽略了度小于y的邻居节点,导致确定节点影响力的准确性降低.如图1,节点10的H指数中心性H-index(10)=2,节点12的H指数中心性H-index(12)=3.然而,根据网络节点的影响力SC值可知,节点10的真实影响力大于节点12.考虑到H指数的不足,本文提出了一种基于度与H指数扩展的局部中心性方法.该方法既继承了H指数中心性与度中心性的所有优点,又解决了H指数中心性的不足.节点vi的DH指数值定义如下：

(5)

式中:a,b是[0,1]的可调参数,经过实验,本文取a=0.15,b=0.15;D(i)表示节点vi的度;Hindex(i)表示节点vi的H指数;Ni是节点vi的所有相邻节点的集合.由式(5)可知,该方法同时考虑了节点自身以及邻居节点和邻居的邻居节点;该方法分为三部分,第一部分是节点自身的度,第二部分是节点的H指数,它根据具有较高度的邻居节点的数量来评估节点的影响力.然而,对于某些网络,H指数中心性识别节点的影响力的能力是有限的,有可能存在多个节点具有相同的H指数值,因此,也考虑了邻居节点的H指数,进而,第三部分邻居节点的H指数相加.

2 实验数据与评估方法

2.1 数据集

为了检验本文方法的有效性,将其应用于真实网络和模拟网络,真实网络包括：空手道俱乐部网络(Karate)[16],海豚社会网络(Dolphins)[17],爵士音乐家网络(Jazz)[18],美国航空运输网络(USAir)[19],大学电子邮件网络(Email)[20],联合作者科学家网络(Authorship)[21],芽殖酵母蛋白质相互作用网络(Yeast)[22].表1介绍了相关网络的顶点数(|V|)、边数(|E|)、阈值(βc)、平均度(average degree)、最大度(maximum degree)以及同配系数(assortativity).

表1 网络数据集的一些统计特性Tab.1 Some statistical characteristics of network data sets

2.2 传播模型

易感染-感染-恢复(SIR)传播模型[23]被广泛用于描述和模拟疫情或信息的传播过程.本文采用SIR传播模型来评估排序节点的真实影响力.在SIR传播模型中,个体可以处于三种可能状态之一：易感染状态(S)、感染状态(I)和恢复状态(R).在易感染状态下,此类个体一般为健康个体,但是可以被病毒感染.在感染状态下,此类个体己经被病毒感染,并具备感染其他健康个体的能力.在恢复状态下,此类个体既不能感染其他个体,也不能被其他个体感染.

在SIR传播模型中,网络初始状态时只有一个节点处于感染状态(I),其余所有节点处于易感染状态(S).然后,己感染的节点试图以感染率β感染其他节点.在每个时间段,每个被感染的节点都会选择继续感染其他节点,或者根据Gillespie算法[24]进入恢复状态.这个过程重复进行,直到网络中没有受感染的节点.一个节点的影响力即为该节点在传播过程可以感染的节点数,进而,可以得到网络中所有节点影响力的排序表.本文实验取100次传播过程的平均值作为节点的影响力.

本文实验将SIR传播模型得到的排序结果与各中心性方法计算得到的排序结果进行比较,中心性方法计算得到的结果越接近于SIR传播模型得到的排序结果,说明该中心性方法的准确性越高.

2.3 评价方法

本文用到了单调函数(M)[26]和肯德尔相关系数[27]两种方法来评价本文所提方法识别网络中节点影响力的有效性.下面将分别说明这两种方法.

在本文中,单调函数用于检验各中心性方法识别网络中不同影响力节点的能力,利用下式计算各中心性方法计算出网络中节点影响力的排序表R的单调性：

(6)

式中:n为排序表R上的排序数;nr为排序表R上元素为r的数量.M值的取值为[0,1],M值越大,相关中心性方法识别网络中不同影响力节点的能力越强.

肯德尔相关系数用于评价两个序列的相关程度,肯德尔相关系数T的取值范围在-1到1之间,T值越接近1,表示两个序列的相关性越高,T值为0表示两个序列相互独立.

假设两个集合X和Y,其元素个数均为n,两个集合取的第i(1≤i≤n)个值分别用xi和yi表示.X与Y中的对应元素组成一个元素对集合XY,其中包含的元素为(xi,yi).对于集合中任意两个元素(xi,yi)与(xj,yj),当xi>xj且yi>yj或者当xixj且yiyj时,这两个元素就被认为是不和谐对；当出现xi=xj或者yi=yj时,这两个元素既不是和谐对也不是不和谐对.

在本文中,两个序列集合一个是通过SIR传播模型识别网络中节点的影响力得到的结果,另一个是通过中心性方法计算得到的排序结果.肯德尔相关系数T值越接近1,说明中心性方法计算得到的排序结果越接近SIR传播模型得到的结果,从而说明中心性方法越准确.肯德尔相关系数定义如下：

(7)

式中:nc表示和谐对的个数;nd表示不和谐对的个数.使用肯德尔系数计算利用SIR模型感染过程得到的排序结果与中心性方法计算得到的排序结果的相关性可以评价排序结果的准确性.

3 结果分析

在实验过程中用DC表示度中心性、BC表示介数中心性、CC表示紧密中心性、Ks表示K-shell中心性、H表示H指数中心性、DH表示局部DH指数中心性.

3.1 单调性

在第一个实验中,根据单调函数(M)计算出不同网络数据集上各中心性方法得到节点影响力排序表的M值,表2为实验结果.从表2的结果可以看出,本文的方法除了在联合作者科学家网络中的单调性M值低于CC方法外,在其余6个网络上的单调性M值都接近于1且高于其余5个中心性方法,因此,本文所提出的DH方法较其他几个中心性能更好地识别网络中不同影响力的节点.

表2 7个网络数据集上不同中心性指标的排序表的单调性M值Tab.2 Monotone M value of sorting tables with different centrality indexes on seven network data sets

3.2 准确性

在第二个实验中,为了验证本文中的方法用于识别网络中不同影响力节点的准确性,利用式(7)计算出本文的中心性方法以及5个传统的中心性,在识别7个真实网络中节点影响力生成的排序表与在特定的感染率β下进行SIR传播模型实验计算出排序表的肯德尔相关系数T值.肯德尔系数T值越大,相关方法识别真实网络中节点影响力的准确性越高.从表3的实验结果可以看出,本文方法的肯德尔相关系数T值高于其他5个中心性方法,因此,局部DH指数中心性方法能更准确地识别网络中节点的影响力.

表3 在7种不同规模的真实网络中,节点影响力与各指标的肯德尔相关系数TTab.3 Kendall correlation coefficient T values in seven real networks with different scales

在实验过程中,为了减少感染率β对实验结果的影响,SIR传播模型中β的取值设置为0.01～0.10.本文实验将中心性计算得到的结果和通过SIR传播模型得到的结果进行相关性比较,并计算肯德尔相关系数T值,实验结果如图2所示.将各中心性方法在爵士音乐家网络、美国航空运输网络、大学电子邮件网络和芽殖酵母蛋白质相互作用网络中计算出的节点影响力排序表,与通过传播模型(SIR)在不同的感染率β下计算出的排序表进行相关性比较,得出肯德尔相关系数T值.从图2可以看出,对于爵士音乐家网络,DH方法和传播模型的肯德尔系数T值一直优于其余5个中心性方法.对于其余三个网络,当感染率β较小时,DH方法的T值并不完全优于其余5个中心性方法,但是随着感染率β增大到阈值βc附近乃至大于βc时,DH方法却明显优于其余中心性方法.这充分说明了较一些传统的中心性方法,本文提出的局部DH指数中心性能更准确地识别网络中节点的影响力.

为了更好地验证局部DH指数中心性的准确性,本文还将其在无标度网络模型(BA)[28]中与其他中心方法进行了比较.BA模型生成网络的主要步骤如下：首先,网络从一个初始连接的m0节点网络开始;然后,每次将每个新节点添加到网络中,用m(m

4 结论

本文提出了一种基于局部度与H指数扩展的复杂网络节点排序方法(局部DH指数中心性),该方法同时考虑了节点自身的度与H指数以及邻居的H指数,结合了度中心性与H指数中心性的优点.为了验证所提方法的有效性,首先,本文通过单调函数(M)验证各中心性指标识别网络中不同影响力节点的能力,实验在7个真实网络中与其余5个中心性方法的结果比较,发现局部DH指数中心性更优于其余5个中心性方法.然后,本文将所提方法应用到7个真实复杂网络以及无标度网络模型(BA)中,并且使用SIR传播模型模拟传播过程,使用肯德尔相关系数计算各中心性方法得到的排序结果和SIR传播模型得到的排序结果的相关性.通过对比发现,局部DH指数中心性更能准确地识别网络中有影响力的节点.