尹荣荣, 尹学良,崔梦頔, 徐英函

1(燕山大学信息科学与工程学院,河北秦皇岛066004)

2(河北省特种光纤与光纤传感重点实验室,河北秦皇岛066004)

无标度网络[1]是度分布服从幂律分布的一种复杂网络,被广泛应用于智慧城市、环境监测、火灾探测和医疗保险等多个领域.研究表明:相比于随机网络,在面临网络的随机攻击时,无标度网络具有更好的抗毁性.可对于网络的蓄意攻击,无标度网络却显得非常脆弱.因此,针对无标度网络的节点重要度评估问题[2]就显得尤为重要.通过节点重要度评估,能够在规模庞大、结构复杂的网络中准确、快速地找到关键节点,并通过对关键节点的重点保护,以提高整个网络的可靠性.

节点的中心性[3]是衡量节点重要性的常用方法,其中,度指标[4]是最基本的中心性指标,但是未考虑到节点的全局重要性,无法找到桥接节点这样的关键节点.与其相比,介数指标[5,6]利用节点到达网络其余节点的最短路径数目,从全局角度评价节点的重要性,能够有效判断出网络中的桥接节点.但该方法的时间复杂度较高,不适用于大型网络.也有学者提出了一些新的网络中心性指标:文献[7]基于节点在整个网络中位置的重要性,利用K核分解的方法提出了节点重要度评估指标,该指标相比于度、介数更能准确识别网络中影响力最大的节点,且时间复杂度低,但并不适用于存在多个传播源的复杂网络.文献[8]提出了一种基于生成树数目的节点删除法,定义最重要的节点为删除该节点使得生成树数目最小,但此方法没有考虑到相邻节点的影响,使得评估结果不准确.文献[9]综合考虑了节点效率、节点度值和相邻节点重要度贡献,提出一种重要度评价矩阵来确定复杂网络关键节点的方法,认为节点间最直接、最重要的依赖关系存在于邻接节点之间,却忽视了相互依赖程度高的非邻接节点.文献[10]则在中心度和节点删除法的基础上提出了连通中心度来度量复杂网络中节点的影响力,该方法同时考虑了节点在网络结构中位置的重要性以及节点对网络局部连通性的影响,较全面地刻画了节点的重要程度,但是其复杂度较高.

虽然以上方法都能有效找出网络中的核心节点,但是关键节点排序问题不能仅局限于网络中的核心节点,有一类处于结构洞位置的节点同样值得我们关注.结构洞是 Burt[11]研究社会网络中竞争关系时提出的经典社会学理论,结构洞体现了两个节点间的非冗余关系,例如,对于3个节点A,B,C来说,如果A和B关联,B和C关联,但是A和C不关联,此时A和C之间存在一个结构洞,并且拥有较多结构洞的网络节点更有利于信息的传播.在复杂网络中,处于结构洞位置的节点并不一定是网络的核心节点,但是因为具有结构洞的特征,使得其在网络信息传输中发挥重大作用,成为网络的关键节点.文献[12]基于结构洞指数构建了节点的重要性矩阵,通过考虑3个节点之间的结构关系来确定节点的重要性,克服了单独分析各个节点重要性的不足.文献[13]提出一种基于节点及其邻域结构洞的评估节点重要度的方法,该方法综合考虑了节点的邻居数量及其与邻居间的拓扑结构,有利于发现在具有强社团结构下最具影响力的节点.文献[14]提出一种基于改进结构洞的节点重要度排序方法,该方法无需考虑网络的全局结构信息,仅利用节点的度和近邻信息就能有效识别出整个网络中的关键节点.

当前,对于单独利用结构洞特征或中心性特征来评估节点重要度的研究已较为深入,但对于综合考虑结构洞和中心性特征的研究目前并不多.文献[15]结合结构洞和接近中心性得到节点结构洞的影响矩阵,从全局和局部的角度综合评估节点的重要程度,但计算网络接近中心性时,其复杂度较高.文献[16,17]分别提出了基于多属性决策的节点重要度排序方法,通过融合结构洞与节点的度、介数、信息指数、接近中心性、流介数中心性、子图中心性等评价指标,避免了节点重要度评估的片面性.但算法均复杂,且易造成标准不统一的情况.文献[18]引入了排序学习的方法,利用ListNet的排序学习方法,融合介数中心性、结构洞的约束系数等7个指标,得到一种综合多指标评价节点重要度的方法.此方法判定出的关键节点具有较高的传播能力,对于现实复杂网络中的实用性较强,但是算法仍较为复杂.基于以上考虑,本文针对无标度网络的节点重要度评估问题,利用构建节点重要度贡献矩阵的思想,提出一种节点重要度排序的新方法.该方法利用相邻节点的结构洞重要性指标值和K核重要性指标值得到节点间的重要度贡献关系,同时,以节点自身K核重要性表征节点的全局位置信息,在分析网络局部重要性的基础上,结合全局重要性,使得节点的重要度评价更加全面,节点重要度评估结果也更为准确.通过在无标度网络中的仿真分析,验证了该方法的准确性和有效性.并且与其他算法比较,在应对网络的蓄意攻击时,此方法较为有效,且时间复杂度较低,适用于大规模的无标度网络中节点重要度的评估.

1 节点重要度评估方法

本文将利用构建节点重要度贡献矩阵的思想,融合网络的结构洞特征和中心性特征.本文运用K核重要性表征节点在网络信息传播中所起的作用,将相邻节点的结构洞重要性指标和K核重要性指标表征相邻节点的重要度贡献,体现节点的局部重要性.同时,节点自身的K核重要性体现节点在网络中的全局位置信息,综合相邻节点间的重要度贡献和节点自身的位置信息,最终得到节点的重要度.

1.1 基于结构洞的重要度贡献比例关系

网络是由节点和边组成的统一整体,节点并非孤立存在,节点的重要度必然受到相邻节点的影响,这种节点间的影响关系可以通过节点间的重要度贡献的形式进行描述.但是与以往研究的重要度贡献关系不同,这里在研究相邻节点间的重要度贡献关系时将引入结构洞特征,利用节点间的结构洞重要性来确定节点对其相邻节点的重要度贡献比例.

设图G=(V,E)是一个无自环的无向网络,共有n个节点、m条边,其中,V={υ1,υ2,…,υn}是网络中所有节点的集合,E={e1,e2,…,em}且E⊆V×V是节点间边的集合.邻接矩阵记为An×n=(aij)n×n,其中,

则节点i的度可以记为

结合节点的度,节点i的邻接度可表示为

其中,Γ(i)为节点i的邻居的集合.

网络的约束系数可以衡量网络中节点形成结构洞时所受到的相邻节点的约束情况,是测量结构洞的一种指标.网络的约束系数越小,结构洞程度越大,节点就越重要.约束系数可表示为

其中,q为节点i和节点j的共同邻居.考虑到节点度和节点邻居的拓扑结构对该节点的影响,可以将pij记为

因此可得出,节点i的结构洞重要性指标Li为节点i的约束系数与网络中所有节点的约束系数的比值,即:

将网络中所有的节点j按照一定的比例值将自身的重要度贡献分配给与其相邻节点i,然后将网络中的全部节点对其邻居节点的重要度贡献比例值均在矩阵中表示出来,再结合网络的邻接矩阵An×n=(aij)n×n,就形成了节点重要度贡献矩阵,记作矩阵LC:

1.2 基于重要度贡献的节点重要度评价

节点的局部信息和全局信息是评价节点重要度的两个关键因素.节点重要度贡献矩阵LC从节点的结构洞重要性入手,反映了相邻节点间的影响关系,在一定程度上可表征节点的局部相邻信息.节点的K核指标考虑的是节点在整个网络中的信息传播的影响力,是依据网络的中心性特征来评估节点重要性.相比于节点效率、介数等中心性指标,其时间复杂度低,适合用于大型网络,可表征节点的全局位置信息.这里引入混合度分解的方法[19]获取K核指标.

在获知K核指标后,可得出节点i的K核重要性Mi:

利用节点的结构洞重要性构建的节点重要度贡献矩阵LC,已经从一定程度上反映了相邻节点间的重要度贡献比例关系,考虑到节点的K核重要性表征了节点的位置信息,于是,可通过融合相邻节点的K核重要性指标值优化LC中的重要度贡献比例值,得到更为全面体现相邻节点间重要度贡献关系的节点重要度评价矩阵HC:

运用节点重要性评价矩阵HC中相邻节点间的重要度贡献关系,再结合节点自身的K核重要性,即可得到节点i的重要度Ci:

通过公式(10)可知,Ci由节点i的所有相邻节点的重要度贡献值之和与节点i的K核重要性指标值的乘积构成,说明一个节点的重要度取决于该节点自身的K核重要性指标值以及相邻节点K核重要性指标值和结构洞重要性指标值,它综合了节点的全局重要性和局部重要性,全面评估了节点的重要度,提高了评估的准确性.

1.3 算法流程

基于重要度贡献的节点重要度评估方法,综合考虑相邻节点的K核重要性指标和结构洞重要性指标来确定相邻节点的重要度贡献,获得节点重要度评价矩阵HC.在此基础上,结合节点自身的K核重要性得到节点的重要度Ci,运用此方法综合全局和局部两个方面对复杂网络中节点的重要度进行评估,其评估结果较为准确.节点重要度评估方法具体步骤如图1所示.

2 仿真分析

本文选择具有代表性的BA无标度拓扑网络[20]进行仿真分析,并进行了如下3类实验:实验1运用30个节点的网络结构进行验证,说明所提出方法的有效性;实验 2模拟网络的蓄意攻击,进一步验证所提方法在不同网络规模下的有效性(重点对比100个节点的小规模网络以及1 000个节点的大规模网络中的情况);实验3统计各方法进行节点重要度评估的运行时间,验证所提方法的计算效率.

2.1 算法有效性分析

本次仿真假设将节点随机分布在500m×500m的方形区域,节点数目设定为30个,拓扑图如图2所示.首先,利用本文方法与其他算法可以得到各节点的节点重要度,评估结果见表 1.下面结合拓扑图进行分析,将本文方法与其他算法进行对比.

通过分析拓扑图(如图 1所示)与无标度网络节点重要度评估结果(见表 1)可知:节点v11,v22,v27的连接度均为 7,但显然它们的重要程度不一样,v23的连接度虽然只有5,但它却处在网络信息传输的关键位置,重要程度明显高于v11,v22,v27,因此,仅依靠节点的连接度无法准确评估节点重要性.采用邻域结构洞法判定关键节点,虽然此方法通过分析节点的度及其邻域结构改进了结构洞指标,但是并未考虑到节点的中心性特征,如拓扑图所示:虽然v23比v27存在较多的结构洞,但是v27的连接度却比v23的连接度大.重要度矩阵法虽然结合了网络的局部属性和全局属性,但是此方法并未从结构洞的角度考虑关键节点,有些结构洞的关键节点对于在网络中的重要度很大,如节点v11,通过拓扑图可以看出此节点拥有较多结构洞.介数方法虽然能够很好地体现在网络信息传输过程中的关键程度,但是一些位置重要程度相近的节点,如v14,v19,v24,仍需进一步结合节点的局部信息来评估,并且此方法的时间复杂度高.节点删除法中,由于删除节点v1,v6,v7,v19,v21,导致网络不再连通,使得删除这些节点后生成树数目为 0,相应的节点重要度为 1,从而无法进一步区分这些节点的重要度.但是由拓扑图可看出,这些节点的重要程度明显不同.

Table 1 Node importance evaluation results in the scale-free network表1 无标度网络节点重要度评估结果

本文所提出的方法则克服了以上方法的不足,它综合节点中心性和结构洞两个角度,同时综合考虑节点的位置信息(全局重要性)和相邻节点的影响(局部重要性),通过此方法可提高评估节点重要度准确性,显著地区分关键节点.表1中,通过本方法判定出的前10个关键节点与其他方法判定出的关键节点大致相同,各方法节点重要度排序因为侧重点不同存在差异.如通过评估结果可看出,节点v22的重要度最大.依据拓扑图,节点v22的连接度较大,则K核重要性较大,且拥有较多结构洞,同时与其相连的v23,v27,v28均具有较大连接度,可体现出此节点处于网络传输信息的重要位置,属于重要的桥接节点.从表 1还看出,本方法进一步区分了v14,v19,v24和v1,v6,v7,v19,v21这些节点的重要程度,克服了介数法和节点删除法的不足.通过对比,本文所提方法是有效的,可提高评估节点重要程度的精度,能显著区分无标度网络中特殊节点间的重要程度.

2.2 在网络的蓄意攻击中进一步验证

为进一步验证本方法的准确性,模拟网络的蓄意攻击,即有针对性地移除网络中重要的节点,可利用蓄意攻击前后网络最大连通分支节点数的变化,分析网络遭受攻击后对网络鲁棒性的影响.首先,统计在不同规模(节点总数从 50～1000)的网络结构下,移除由这几种算法各自判断出的前 10%的关键节点后,网络最大连通分支节点数占网络总节点数的比例.如图3所示.

由图3可知,随着网络规模的增大,移除网络的前10%的关键节点对于网络连通性的影响程度也随之变大.这表明关键节点的有效评估不仅对小规模网络鲁棒性有重要影响,对大规模无标度网络更为重要.并且在不同网络规模下,移除本文方法所判断出的前 10%的关键节点,网络的最大连通分支占网络总节点数的比例总是小于重要度矩阵法,说明此方法判断出的关键节点对于网络的鲁棒性影响更大.同时,此方法与邻域结构洞法、介数法、节点删除法相比,对于网络的连通性影响程度较为接近.

为进一步区分几种方法判断出的关键节点对网络连通性的影响程度,下面分别讨论在小规模网络(100个节点)以及大规模网络(1 000个节点)下,依次移除前10%的关键节点后对于网络连通性的影响.

图4给出了在100个节点的小规模无标度网络中,依次移除各方法评估出的前10%的关键节点,网络最大连通分支节点数的变化情况.

通过分析图 4的变化趋势可知,与其他算法相比,本文方法的网络最大连通分支节点数下降速度最快,当前6个关键节点失效时,本文方法的最大连通分支节点数已经少于50个(原网络规模的1/2),而其他算法中的最大连通分支节点数仍多于 50个.因此,相对其他算法而言,若依据本文方法判断出的关键节点对小规模网络实施蓄意攻击,网络结构将快速瓦解.从而表明,本文方法对小规模无标度网络中节点的重要性能够进行有效评估.

图5给出了在1 000个节点的大规模无标度网络中,依次移除各方法评估出的前10%的关键节点,网络最大连通分支节点数的变化情况.

由图5可知,对于规模为1 000的无标度网络,甚至只需移除各种方法判断出的前4%(40个)的关键节点,就足以使整个网络崩溃.这进一步验证了对于大规模无标度网络而言,关键节点对于网络鲁棒性的影响更为明显.并且在前 4%的关键点移除过程中,与其他算法相比,依次移除用本文方法得到的关键节点,网络最大连通分支节点数下降速度最快,明显优于重要度矩阵法和邻域结构洞法,且略优于介数法和节点删除法.为此,下面进一步分析在1 000个节点的网络规模下,依次移除前10个关键节点后的网络最大连通分支变化情况,如图6所示.

由图6可见,依次移除各方法评估出的前10个关键节点,本文方法中的最大连通分支节点数的下降速度明显优于其他算法,在移除10个关键节点后,网络最大连通分支节点数已经降至500(原网络规模的1/2)以下;介数法和节点删除法的网络最大连通分支节点数介于 600～700之间;重要度矩阵法和邻域结构洞法的网络最大连通分支节点数介于800～900之间.因此,相对其他算法而言,若依据本文方法判断出的关键节点对大规模网络展开蓄意攻击,只需攻击极少量的关键节点,网络结构便会快速瓦解,从而表明本文方法对大规模无标度网络中节点的重要性也能够进行有效评估.

综上所述,无论无标度网络规模如何变化,相比于其他算法,本文方法判断出的关键节点对于网络的连通性影响更为明显.当然,依据此方法对网络中的关键节点进行针对性的保护,便能有效地抵御网络的蓄意攻击,增强网络的鲁棒性.因此,通过在网络蓄意攻击中的仿真过程,进一步验证了本文方法的有效性.

2.3 算法效率分析

在微机上运行MATLAB程序,分别用本文方法、邻域结构洞法、介数法、重要度矩阵法、节点删除法对不同规模的无标度网络进行节点重要度评估,统计出运行的时间如图7所示.

随着网络规模的扩大,本文方法的运行时间与邻域结构洞法的运行时间基本相同,且明显少于另外 3种算法,评估400个节点的重要度时本文方法运行时间为重要度矩阵法的16.5%,为介数法的4.3%,为节点删除法的3.1%.这说明本文提出的节点重要度评估方法是有效的,同时对于大型的网络具有理想的计算能力.

3 结 论

针对无标度网络节点重要度评估的问题,提出了一种基于节点间重要度贡献关系来确定无标度网络中的关键节点的新方法.经过理论分析及仿真分析算法效率可知:该方法的时间复杂度低,适用于大型网络的节点重要度评估.仿真实验分析表明:该方法可行有效,能够找到网络中同时具有中心性和结构洞特征的关键节点,克服其他算法的不足,使得评估节点重要度更加准确.依据该方法得到的节点重要度排序对网络进行蓄意攻击,可以使网络结构快速瓦解.尤其是大型网络,仅攻击少量关键节点即可损毁整个网络.因此,利用该方法识别出的关键节点也可有效地帮助我们设计网络的防护策略,提高网络的抗毁性.