基础设施网络上PageRank算法的应用

2018-11-30李泽荃郭作星

计算机应用与软件 2018年11期

李泽荃郭作星申咪

1(华北科技学院北京 101601)2(北京印刷学院北京 102600)

0 引言

诸如生物、社会、神经系统、计算机网络、交通运输等复杂系统[1-6]都可以用网络来表示。其中：节点代表系统的各个实体；节点间的连边表示实体间的关系。同样，包括电力、通信、供水、供气、航空、道路等基础设施[7-11]也可以表示为复杂网络，利用网络的拓扑结构和动力学特征来研究其特性。

众多学者[10,12]研究这些基础设施网络的统计特性和动力学过程，结果表明现实网络中的节点地位或者位置不同，在扰动下网络的破坏性也存在不同程度的差异。因此，针对基础设施网络中的节点重要性进行排序，识别网络中的关键节点对于网络抗毁性能的研究具有重要意义。而对于此项工作，复杂网络中称为最优渗流，目前也成为网络科学的重要研究方向之一[13-14]。

关于网络中重要节点的排序方法目前常用的有度中心性[15]、k-壳分解法[16]、信息指标[17]、介数中心性[18]以及它们的含权方法等。可以看出，网络重要节点评价方法较多，各有侧重。为便于针对实际问题选取合适的方法，任晓龙等[19]系统分析了复杂网络领域具有代表性的30多种重要节点挖掘方法，并将其归纳为4个大类，即基于节点近邻的排序方法、基于路径的排序方法、基于特征向量的排序方法和基于节点移除和收缩的排序方法。

相对于其他类的排序方法，基于特征向量的方法不仅考虑了节点的邻居数量，还考虑了其质量对节点重要性的影响，因此，近年来在理论和商业上都受到了广泛关注。特别是谷歌搜索引擎的核心算法PageRank，除在网页排序领域中的广泛应用之外，很多学者也将其引入到其他方面，如识别社会网络中的领导者[20]、科学论文引用分析[21]、水网中节点重要性的评价[10]等。

文献[10]以山西大水网工程为网络背景，研究了度中心、接近中心、介数中心和k-核分解四种单指标水网节点重要性排序方法的缺点，提出了基于TOPSIS的多属性决策方法。并在考虑水网方向和级别差异的情况下，运用PageRank算法对有向赋权水网节点进行了重要性评价。或许对于像水网这样的基础设施网络运用PageRank算法进行重要节点排序还很少见，文献[10]的研究结果也没有通过相关模型进行验证。为解决此问题，本文将选4种重要节点排序方法进行了节点排序对比，并通过灾害蔓延模型进行仿真验证。

1 网络原型及方法

文中采用的基础实施网络为美国航空交通控制网络ATC(Air traffic control)，来源于美国的联邦航空管理局飞行数据中心(FAA-NFDC)。在该网络中，节点代表机场或者服务中心，连边表示由NFDC推荐的首选飞行线路。ATC网络为有向无标度网络，共有1 226个节点、2 615条边，网络中节点的最大度为37，幂律常数为3.7。

文献[19]通过分析目前学术界和工业界有关网络重要节点排序的常用方法，并总结出4种基本类型。本文借鉴其思路，分别从4种类型的方法中各选择一种，即度中心性(基于节点近邻的排序方法)、介数中心性(基于路径的排序方法)、残余接近中心性(基于节点移除和收缩的排序方法)和PageRank方法(基于特征向量的排序方法)。下面针对这四种方法作简要介绍：

(1) 度中心性：一个节点的重要性等价于该节点与其周围节点建立直接联系的能力，定义为节点的邻边数，记为:

DC(i)=ki/(n-1)

(1)

(2) 介数中心性：一个节点的重要性是通过该节点负载的信息或能量的大小来刻画的，即经过该节点的最短路径数越多，其就越重要，记为：

(2)

式中：gjk为节点j与节点k之间的所有最短路径数目；gjk(i)为节点j与节点k之间经过节点i的最短路径数目；(n-1)(n-2)/2为最大可能的节点介数。

(3) 残余接近中心性：若一个节点的删除增加了网络的脆弱性，则该节点就越重要，用来衡量节点的移除对网络带来的影响，记为：

(3)

式中：djk(-i)为删除节点i之后，节点j与节点k之间的最短距离。

(4) PageRank算法：最初主要用于网页排序，一个页面的重要性取决于指向它的其他页面的数量和质量，如果一个页面被较多的高质量页面指向，则这个页面的质量也比较高，记为：

(4)

另外，对于本文的研究思路，描述如下：首先，采用上面提到的4种排序方法对ATC网络中所有的节点进行排序；然后，分别选取前5(Top-5)、前10(Top-10)和前20(Top-20)的节点运用灾害蔓延动力学模型进行攻击模拟，模拟时间为20步；最后，对比相变之后某个时间步时网络中崩溃节点的总数，从模拟结果来看，t=10时已达到平衡。

2 灾害蔓延动力学模型

在评价各种节点重要性挖掘算法时，传统上一般采用传染病模型，即SIS模型和SIR模型，如通信网络中的病毒传播[22]、电力网络中的相继故障[23]等。然而，对于犹如电力系统等基础设施网络，采用传染病模型不能有效地描述灾害在网络中的传播过程。信息和病毒在网络中的传播有很大的不同，病毒的传播需要物理层面上的接触，有关此问题的详细讨论可参考文献[24]。自从Buzna等[6]提出灾害蔓延动力学模型后，众多学者开始转向采用该模型进行基础设施网络上的灾害传播研究。因此，本文也采用该动力学模型作为排序算法的评价验证模型。

对于基础设施网络，本文主要关注的是网络的脆弱性，即网络中某个(些)节点破坏后，这种破坏状态或者灾害在网络中的传播速度和传播范围。基于此，Buzna等[6]建立了一个普适性的灾害传播动力学模型，用于模拟灾害在网络中的传播过程。

假定一个有向网络G=(N,S)包含节点i∈N:={1,2,…,n}和边(i,j)N×N，它们分别代表系统的节点和各节点之间的相互关系；xi表示节点的属性值，当xi=0时表示节点处于稳定状态，当xi偏离零时表示节点发生破坏。因此，节点关于时间的演化动力学模型可以表示为：

(5)

(6)

(7)

该动力学方程包括三个部分：式(5)等号右边第一项表示节点的自我修复功能；第二项表示节点的灾害蔓延机理；第三项表示节点的内部随机噪声。其中：1/τ为节点的自我修复速度；Mij为节点i对节点j的影响程度；tij为节点i和节点j之间的影响延迟时间；β为传播过程中的阻尼作用。式(6)为Sigmoid函数，α为定值，θi为节点i的阈值。式(7)为节点i的出度函数，反映节点i对其他节点的影响程度，oi为出度值，a和b为定值。

3 结果分析

按照上述思路，本文首先给出4种排序方法的排序结果，详细情况见表1。可以看出，对于前20个重要节点，度中心性和介数中心性的排序重合度较大，而残余接近中心性和PageRank算法与前两者交叉性非常小，特别是对于PageRank算法，前5个重要节点与其他三种方法完全不同。

表1 节点排序结果(Top-20)

为了更好地理解PageRank排序算法下节点的特性，这里给出3个节点的邻居数量及其质量示意图，具体如图1所示。可以看出，排序靠前的节点除邻边数目较多以外，其邻居的质量更好，或者说其邻居的邻居更多。从原理上来讲，PageRank算法属于基于特征向量的方法，其不仅考虑到邻居的数量，而且还考虑到邻居的质量对节点重要性的影响。这与图1所展现的特性刚好吻合。

(a) 节点52，排序第9位

(b) 节点266，排序第20位

表1已经给出了4种算法的重要节点排序结果。本文通过灾害蔓延动力学模型进行模拟仿真，对算法的排序结果进行评价验证，具体结果如图2所示。图2(a)中，PageRank算法和度中心性方法的模拟仿真结果基本类似，相比其他方法，特别是度中心性排序方法，PageRank算法的优势还不够显著。但随着增加排序节点数，如图2中的(b)和(c)，运用PageRank得出的排序节点模拟仿真后，网络中的崩溃节点累积数逐渐增加，例如图2(c)中的PageRank已经远远超过介数中心性。因此，可以说明采用PageRank算法求解出的排序节点对网络的影响较大。

(a) 前5个重要节点

(b) 前10个重要节点

4 结语

本文在一个实际的航空交通基础设施网络(US Air traffic control)上对比了度中心性、介数中心性、残余接近中心性和PageRank4种重要节点排序算法的排序结果，并通过灾害蔓延动力学模型进行了模拟验证。结果表明，PageRank算法可以用于进行基础设施网络上的重要节点排序，与其他排序方法相比，它使得网络最终的崩溃节点数始终保持最多，说明PageRank算法拥有比其他方法具有更好的重要节点识别能力。