局部特性与全局环境融合的节点排序算法

王秋玲，贺僚僚，徐 宏，魏子昂，柯宇昊，官文英，朱璋元

(1.长安大学 运输工程学院，陕西 西安 710064；2.中铁一局集团有限公司，陕西 西安 710054)

识别网络中的关键节点是网络科学的重要研究内容之一[1]。由于复杂网络具有非同质拓扑结构的本质特征，少数关键节点失效就会导致整个网络的全局崩溃[2]。挖掘网络中的关键节点，对人们分析网络拓扑性质以及控制传播过程具有重要意义。尽管关于复杂网络关键节点的研究很多，但目前学术界对于关键节点的定义及其衡量指标没有统一的标准。关于关键节点的定义主要集中于如下3种[3]：社会网络学者认为，关键节点是对其他节点及整个网络有显著影响作用的节点；系统科学学者认为，关键节点是指遭受攻击后，使得网络效率降低甚至瘫痪的重要性最高的一类节点；而信息传播领域的学者则提出，关键节点是信息传播能力最高的一类节点。与此对应，关于衡量指标也主要集中于3个方面[4]：一是节点的显著性等价于节点的重要性；二是节点的破坏性等价于节点的重要性；三是节点的重要性取决于节点的传播能力和邻居节点的重要性。

衡量节点重要性常用的方法是基于节点属性和位置提出的节点中心性算法[5]，包括度中心性、介数中心性、紧密度中心性、特征向量中心性、K-shell、Page Rank、结构洞等[6-7]。上述方法已被应用到社交网络[8]、生物网络[9]、交通网络[10]、电力网络[11]、信息网络[12]、代谢网络[13]等各种现实网络分析中，并且取得了较为准确的评价结果。但各类方法在使用过程中优劣势并存[14]，具体汇总梳理如表1所示。

在交通网络中，从社会经济活动层面来看，出行活动将关键节点与其邻居节点紧密联系在一起，使得节点重要性与其邻居节点重要性显著相关；从物理拓扑网络层面来看，交通网络关键节点是连接、支撑整个交通系统的重要桥梁，在全局网络中居于枢纽地位。因此，为保证交通网络中关键节点的识别结果能同时表征节点间的流量作用关系和节点对整个网络连通性的影响作用，交通网络中的关键节点识别方法要综合考虑节点局部属性和全局属性两个因素[15]。但现有方法大多都不能满足这一诉求，基于此，笔者将对这一问题进行分析。

1 算法改进

目前，对交通网络关键节点识别算法的研究较多，大多都是在复杂网络节点重要度评估方法基础上进行扩展，从节点局部属性角度或全局属性角度对节点进行评价，部分学者将两者进行结合，并运用多种性能指标来衡量节点的重要程度。例如，谌微微等[16]基于节点度值、接近中心性、中介中心性 3 个指标评价轨道交通网络节点的重要度，然后以重庆市轨道交通网络为例对重要站点进行分析；梁青槐等[17]结合主客观集成赋权法思想，融合了度中心性、接近中心性和介数中心性指标，以此构建了城市轨道交通网络关键节点识别模型。然而上述方法在评估交通网络中的节点重要度时，不能说明节点负载流量差异对节点重要度产生的影响。因此，笔者将利用Page Rank的思想，融合网络的结构洞特征，用相邻节点的结构洞重要性指标来表征交通网络相邻节点间的客流贡献关系，体现节点的局部重要性。同时，Page Rank算法体现了交通节点在网络中的全局重要性。综合相邻节点间的约束度和节点全局位置信息，笔者提出了一种基于“结构洞”的Page Rank改进算法。该算法不仅能同时表征交通节点的局部特性和全局环境，而且考虑到了节点流量、位置和邻居节点重要性的影响作用，时间复杂度较低。而表1中其他算法的融合在兼顾局部特性和全局环境的基础上，无法同时体现节点流量、节点位置的影响作用以及排序惟一、时间复杂度低的优势。

1.1 Page Rank算法

Page Rank算法是Google创始人Sergey Brin 和 Larry Page在构建早期搜索系统原型时提出的链接分析算法。该算法不仅是谷歌网页排序的关键技术，还被改进应用到其他领域。参考学术论文以引用量评估重要性的方法，Page Rank的基本思想是根据网页的链接结构来进行排序[18]，被链接数量越多，网页重要程度越高。同时，Page Rank算法还将指向目标页面的其他页面自身重要度考虑在内，认为重要页面对被链接页面重要性的提升作用远远大于普通页面。因此，网页的重要性取决于指向它的其他网页的数量和重要性。指向它的网页的重要性越高，数量越多，则该网页越重要，相应的Page Rank值越高。计算方法如下所示：

(1)

Page Rank算法给出了网页的全局重要性排序，不过其缺点在于无法体现主题的相关性，没有区分页面内的导航链接、广告链接和功能链接等，容易对广告页面有过高评价。也就是说，忽略了网络中节点自身的属性。从拓扑结构角度考虑，Page Rank算法弱化了局部属性对节点的影响，从而使用户通常以相等概率随机跳转到相邻节点，然而实际生活中多数网络均普遍具有异质性特征，该方法在一定程度上对节点异质性的体现不足[19]。

1.2 “结构洞”理论

结构洞理论最初由Ronald Burt提出，并应用于社会网络竞争关系研究中。从社会学角度看，Burt 认为结构洞是“两个行动者之间的非冗余关系”。如图1所示，D与A、B、C中的任意两者之间的关系结构就是一个结构洞。对于A、B、D三者来说，A和B都与D有关，但是两者之间却不存在关系，相当于有一个空洞，洞两边的联系人可以带来累加而非重叠的网络收益，从而使占据结构洞位置的个体获得更多的竞争优势与累加收益。从复杂网络角度看，拥有较多结构洞的网络节点能够获取更关键的信息，更有利于信息的传播[20]。

图1 结构洞示意图

Burt提出，可以用网络约束系数来衡量网络中节点与节点之间的依赖关系以及网络节点形成结构洞时所受到的约束。约束系数越小，节点之间的依赖性越弱，则越有可能形成结构洞，能力就越大。网络约束系数的计算方法如下所示：

(2)

(3)

其中，Cij是i在j身上投资的精力，即约束度；Pij表示节点i为维持与节点j的邻居关系所投入的精力占总精力的比例；Piq和Pqj分别是节点i，j与共同邻居q维持关系投入的精力占其总精力的比例；Γ(i)表示i的邻居集合；aij为

(4)

由于节点之间约束度越小，则表示两节点间的交互能力越强，因此定义节点i与节点j之间依赖关系重要度指标Lij为

Lij=1-Cij。

(5)

约束系数只衡量了节点与其最近邻节点间的关系，没有进一步考虑邻居节点与其余节点相连的拓扑结构对该节点的影响，该指标不能发现一些重要的“桥接”节点[21]。

1.3 基于“结构洞”的Page Rank算法改进

根据以上分析，将局部指标“结构洞”和全局指标Page Rank结合，可以同时弥补这两种方法的缺陷。笔者提出一种基于“结构洞”的Page Rank算法改进方法，即ST-Page Rank算法。从网络约束系数来看，交通网络中的流量流动时节点会将交通流按依赖关系大小分配给相邻节点，同时依赖关系越强的邻居节点将会得到更多的流量。

定义交通网络中节点Vi的影响力指标Ii为

(6)

其中，Lij表示交通节点Vi与Vj之间的依赖关系大小，n为交通网络中的节点个数，Q为跳转概率，Ij表示交通节点Vj的影响力指标值，N(i)为节点Vi的邻居节点集合。节点初始重要性为结构洞指标值。

ST-Page Rank算法的具体步骤如下所示。

算法1基于“结构洞”和Page Rank关键节点的识别方法。

输入：G=(V，E)。

输出：rank list。

① for all connected nodesVi、Vj∈Vdo

② calculateCijusing the formula(2)

③ end for

④ for allCijbetween neighbor nodes ofVi、Vj∈Vdo

⑤ normalizeLijusing the formula(5)

⑥ end for

⑦ for allVi∈Vdo

⑧ calculateIibased on Page Rank algorithm and Constraint coefficient ratio obtained at the second of the algorithm using the formula(6)

⑨ rank list.put(Vi，Ii)

⑩ end for

2 实例仿真

2.1 仿真设计

2.1.1 数据集

选择无向无权的美国航空网络US Air[22]进行验证。网络详细信息如表2所示。

表2中，网络节点代表机场，网络连边表示机场间有直飞的航线。网络结构特征量包括节点数|v|、边数|E|、平均度〈k〉、最大度kmax、平均聚类系数C、平均路径长度L和理论传播阈值βth。

表2 网络结构特征信息

2.1.2 算法性能评估

在交通网络关键节点识别研究中，很多学者利用信息传播领域学者的观点来验证节点重要度排序结果的可靠性。例如，文献[23-24]中通过比较节点中心性算法排序结果和SIR模型排序结果的Kendall 相关系数值τ来评估算法的准确性。故笔者选择SIR模型和Kendall 相关系数评价ST-Page Rank算法的性能及有效性。

(1)SIR 模型

在SIR模型中，所有节点存在 3 种状态：易感状态S，指未受感染但缺乏免疫能力，容易被其他节点感染；感染状态I，指感染节点以β的概率感染其他节点，以γ的概率恢复到免疫状态；免疫状态R，由感染状态恢复且具有免疫能力，不会再次被感染。

将种子节点Vi经t步感染后网络中感染节点及恢复节点的平均数量定义为该节点的SIR传播能力，用来评价节点的传播重要性：

(7)

(2)Kendall相关系数

采用Kendall相关系数τ评价两个序列的相关程度。在文中的两个序列集合X，Y分别指通过 SIR 模型识别的关键节点排序结果和通过中心性方法得到的排序结果。τ的定义如下：

(8)

其中，X，Y表示两个不同的序列，τ(X，Y)表示序列X和Y的肯德尔相关系数值，C为具有一致性排序顺序的元素对数，D为具有不一致性排序顺序的元素对数，T是排序向量中的元素个数。τ的取值在[-1，1]之间。τ=1，为完全正相关；τ=-1，为完全负相关；τ=0，为不相关。τ值越大，则两个序列相似性越高；反之，相似性越低。

2.2 结果分析

为了验证上述算法的准确性，在实验过程中选取度中心性(DC)、介数中心性(BC)、紧密中心性(CC)、特征向量中心性(EC)、K-shell分解法(Ks)、Page Rank(PR)以及结构洞(ST)这7个经典算法作为对照实验。在美国航空网络中计算出文中算法以及另外7个传统算法的排序结果，然后在特定的感染率β=βth=0.02，γ=0.01下进行SIR传播实验。利用式(7)和式(8)计算出SIR模型排序结果，将笔者提出的算法以及对照算法排序结果的肯德尔相关系数列在表3。τ值越大，则表明相关节点重要性识别方法越准确。从表3的实验结果可以看出，笔者提出方法的肯德尔相关系数τ值高于其他7个经典算法。因此，ST-Page Rank算法在识别网络关键节点时具有一定优越性。

表3 SIR传播模型与各中心性指标排序结果的肯德尔相关系数表

为了更好地验证算法的准确性，减少感染率β对实验结果的影响，在实验过程中，β的取值范围设置为0.01～0.10，分别计算不同的β下的肯德尔相关系数τ。实验结果如图2和图3所示。

图2 新算法与经典局部属性算法对比图

图3 新算法与经典全局属性算法对比图

从图2及图3实验结果中可以得出，在美国航空网络中，当β取0.01时，结构洞算法的识别效果最优，紧跟其后的分别是K-shell、度中心性和新算法，介数中心性识别效果最差，介于它们之间的有接近中心性、特征向量中心性和Page Rank。此时，新算法的肯德尔系数值居于中间地位。当β从0.01上升到0.02时，除特征向量中心性和Page Rank之外，其他算法的肯德尔系数都逐渐减小，且新算法的τ值排名从第4名迅速上升到第1名。之后，随着β继续增大到0.05，各算法在不同感染率下的肯德尔系数都有较大波动，整体上呈现出先下降后上升的趋势。其中，新算法的肯德尔系数整体上高于其他算法，识别效果最优；特征向量中心性、结构洞、Page Rank这3种算法的肯德尔系数较为接近，识别效果差异不大，但明显优于度中心性、接近中心性、K-shell和介数中心性。当β从0.05上升到0.07时，各算法的肯德尔系数变化趋势相似且较为稳定，新算法的识别效果略逊于结构洞。当β从0.07上升到0.10时，各算法的识别效果并不稳定。当β取0.07和0.10时，K-shell识别效果最优。当β取0.08时，接近中心性识别效果最优。当β取0.09时，Page Rank识别效果最优，介数中心性识别效果依然排在末位。

综上所述，当感染率β在0.02附近时，新算法明显优于其余7个经典方法；当感染率β较大时，新算法的值并不完全优于其余算法，但与最优算法差异不大。这充分说明了较一些经典的关键节点识别算法，笔者提出的基于“结构洞”的Page Rank改进算法能更准确地识别网络中有影响力的节点。

3 总 结

笔者提出了一种局部特性与全局环境融合的交通网络关键节点识别算法。该方法结合了“结构洞”和“Page Rank”的优点，同时考虑了节点的局部拓扑结构和网络全局特征。为了验证所提算法的有效性，首先，选取7个经典方法和笔者提出的算法进行对比，在美国航空网络中计算各种方法的排序结果；然后，利用 SIR传播模型模拟不同感染率β下的传播过程，使用肯德尔相关系数分别计算这8种算法的排序结果和SIR传播模型得到的排序结果的相关性。实验结果表明，基于“结构洞”的Page Rank改进算法(ST-Page Rank)在交通网络中能够准确地识别网络中有影响力的节点。