基于Pajek的航空网络特征评价与可生存性分析

刘典勇，左小五，张冰冰

(上海理工大学 光电信息与计算机工程学院，上海200093)

针对航空网络使用可视化工具Pajek进行分析和模拟仿真，通过模拟对比对比国内航空网络与国外航空网络的抗打击能力，对航空网络的可生存性进行研究［1］。

1 航空网络特征评价

1.1 航空网络统计特征简介

小世界效应是指在大尺度复杂网络结构中任意两点之间存在着一条相对很短的连接路径［2］。

网络中两个结点i和j之间的距离dij定义为连接这两个结点的最短路径上的边数。网络中任意两个结点之间距离的最大值称为网络的直径，记为D［3］，即

网络的平均路径长度L定义为任意两结点之间距离的平均值［4］，即

其中，N为网络结点数。有时平均路径长度又称为特征路径长度。

一般地，假设网络中的一个结点i有ki条边将其与其他结点相连，这ki个结点就称为结点i的邻居。显然，在这ki个结点之间最多可能有ki(ki－1)/2条边。而这ki个结点之间实际存在的边数Ei和总的可能的边数ki(ki－1)/2之比就定义为结点i的类聚系数Ci［5］，即

许多复杂网络的度分布可用幂律形式P(k)～k－γ来更好地描述，如图1所示。幂律分布函数具有如下无标度性质［6］:

考虑一个概率分布函数f(x)，若对任意给定常数a，存在常数b使得函数f(x)满足“无标度条件”

图1 幂律分布(对数坐标系)

网络直径是指复杂网络中距离最远两点间的距离。若在航空网络真实反映出来，则是拥有最多站点的航线的站点数目。

结点的介数则是指网络中经过某结点的最短路径数目，其侧面反映了结点的综合影响力，各种交通枢纽都是介数较大的结点。这对于在现实网络中发现和保护关键资源具有重要意义。

1.2 航空网络拓扑图的绘制

本课题选取的是2005年的美国航空网络和中国航空网络，其中美国航空网络由332个通航城市、2 461条直飞航线组成，中国航空网络选取了2005年其中30个最主要城市作为通航城市，组成了274条直飞航线。其中所涉及到的网络数据全部来源于互联网［7］。

将美国和中国航空网络数据.net文件读入Pajek软件后，单击Draw按钮就可以得到航空网络的拓扑结构图，如图2和图3所示。

图2 美国航空网络拓扑结构图

图3 中国航空网络拓扑结构图

1.3 中美航空网络的统计特性

美国是发达国家，航空网络的发展已到了一定阶段且已基本成熟。而中国是发展中国家，虽然航空领域已经日趋成为我国主要的交通运输业，但毕竟还未发展成熟，容错率和抗击打能力仍不足。通过静态统计特征值:度分布、平均路径长度、结点介数、网络直径、类聚系数等来分析两个具有代表性的国家的航空网络模型。

通过Pajek软件对中国和美国航空网络进行关于统计特征的计算，得到中国航空网络的基本统计特性，平均度:15.967，平均路径长度:1.444，网络直径:5，平均类聚系数:0.472，平均结点介数:0.325。

美国航空网络的基本统计特性，平均度:12.808，平均路径长度:2.738，网络直径:6，平均类聚系数:0.396，平均结点介数:0.204。

对比两国航空网络模型的统计特征值，大体可知中国航空网络具有高类聚系数，呈现小世界网络的特征。

2 可生存性分析

2.1 随机攻击下的可生存性分析

随机攻击即以一定比例随机移除结点，网络在随机破坏作用下的网络生存性，主要根据Pajek的强大网络分析能力和计算能力来评价航空网络。因此，就在此基础上进行随机性攻击［8］。对于航空网络而言，随机攻击主要指一些随机因素造成一个结点(城市)的失效。随机攻击假设通常的随机性攻击指的是网络中的结点以某种概率被随机的攻击和破坏［9－10］，以中美航空网络为例，考虑到航空网络中的机场城市数目较多，因此文中按照前0%，10%，20%，30%，40%，50%，60%的结点比例随机删除网络中的结点，利用Pajek分别得到遭受随机删除结点后的平均长度L，并得到平均长度变化趋势图。

由图4可知，中国航空网络在遭受10%随机打击时，平均路径长度变为1.478，直至增加到删除结点50%时，平均长度变为1.67，这说明中国航空网络中各个通航城市之间联系紧密，而不会因为某几个结点的移除而变成网络崩溃。然后随着移除结点的比例逐渐增加，直到60%时，航空网络之间的联系遭到了严重破坏，一直到彻底崩溃。而美国航空网络则在50%以内的打击下，网络基本没受影响，而在随机打击了60%的结点后，平均路径长度仍为2.2，各通航城市之间保持较高的连接性。

图4 随机攻击下中美航空网络平均长度趋势图

在对航空网络的评价分析中，移除比例分别为0%，10%，20%，30%，40%，50%，60%进行随机攻击航空网络，通过统计剩余可攻击航线数N来表征航空网络的完整性和可生存性。

分别统计中美航空网络可攻击航线条数N，通过Pajek强大的数据统计和分析能力，得到以下可达航线数N与移除结点比例的趋势图，如图5所示。

图5 随机攻击下中美航空网络可达航线数趋势图

中国航空网络在随机攻击下的可达航线数逐渐下降，即网络总边数会急剧下降，一直到40%时，网络总边数变为1，即网络已遭到严重破坏。而美国在遭到移除60%的结点时仍有1 000多条航线，两组趋势图均说明中国航空网络在随机攻击下具有一定的可生存性，但其随机打击下的生存性不如美国。

2.2 蓄意攻击下的可生存性分析

为得到在蓄意攻击下，网络的生存性特点，选择删除结点的办法。为使这两个网络尽快的崩溃，因此选择攻击网络中度最高的结点，将它们依次删除，然后在Pajek中删除网络中指定的结点。

由于所选航空网络模型的结点数比较多，因此选择采取按百分比攻击度排在前面的结点，假设选取蓄意攻击前0%，10%，20%，30%，40%，50%，60%的结点，然后分别绘制出中国和美国的航空网络在遭受蓄意攻击情况下的平均路径长度和蓄意打击总边数等统计特性趋势图，通过对比其中的性能指标来对比其可生存性，如图6和图7所示。

图6 蓄意攻击下中美航空网络平均长度趋势图

图7 蓄意攻击下中美航空网络可达航线数趋势图

从以上两组图中可以看出，当网络遭受蓄意攻击时，平均长度急剧上升，当打击到30%结点或当蓄意攻击前40%的结点时，平均最短距离为0，即中国航空网络之间不连通。当攻击10%结点后，中美航空网络中的大部分的结点之间都是连通的，可相互到达。当攻击前40%的结点时，中国航空网络整体结构已遭到严重破坏，直至当蓄意攻击网络中60%的结点时，中国航空网络已经完全断开连接。而从图7中可以看出，即使蓄意攻击网络中的前60%的结点，美国航空网络中的大部分结点还是连通且可到达的。由此可见，美国航空网络在蓄意攻击下的可生存性远优于中国。

说明美国航空网络在蓄意攻击下具有更好的可生存性，可见发达国家的航空网络较发展中国家来说具有明显的优越性和稳定性。

3 结束语

本文主要是运用Pajek和复杂网络理论的观点和方法针对国内和国际的航空网络建立不同的可视化模型，以中国和美国的航空网络的模型数据为例进行分析，美国是发达国家，航空网络的发展已基本成熟。而中国是发展中国家，虽航空领域已日趋完善，但毕竟还未发展成熟，容错率和抗击打能力仍不足。研究表明，中国航空网络仍是一个小世界网络。

在研究航空模型的过程中引用了Pajek可视化软件，运用Pajek可直观的发掘航空网络的一些特征，但Pajek也有其的不足之处，例如要对网络的蓄意攻击进行模拟时，删除结点只能手动进行，若网络中的结点过多时，则手动删除的效率就会变得较低，这功能有待优化。且由于文中所掌握的中国国内航空网络的实时数据不足，导致在建立Pajek网络模型时会存在误差。若能获得更多详细的航空网络数据，模型将得到大幅改善。

［1］ 朱冰心.中国航空网络结构及其演化分析［D］.上海:复旦大学，2007.

［2］ 黄加增，余国伟.城市公交复杂网络研究［J］.计算机技术与发展，2012，22(6):234－238.

［3］ 彭俊.复杂网络的拓扑结构及传播模型的研究［D］.西安:西安电子科技大学，2009.

［4］ 邓雪莲.负责网络抽样研究［D］.南宁:广西师范大学，2008.

［5］ 安莉莉，马杰良，邢雪.南京市公交网络建模与拓扑特性分析［J］.公路交通科技:应用技术版，2009(2):181－183.

［6］ 蔺志峰.复杂网络的搜索策略研究［D］.石家庄:石家庄经济学院，2011.

［7］ 中国民用航空总局规划发展财务司.从统计看民航2005［M］.北京:中国民航出版社，2005.

［8］ 熊静.基于复杂网络理论的交通网络可生存性分析［D］.武汉:华中科技大学，2009.

［9］ 俞桂杰，彭语冰，褚衍昌.复杂网络理论及其在航空网络中的应用［J］.复杂系统与复杂性科学，2006，3(1):79－84.

［10］张雯雯.复杂网络理论在航空网络中的应用研究［D］.天津:中国民航大学，2009.