基于复杂网络理论的航材配送网络抗毁性分析*

郑文强，陈云翔，庄骏，蔡忠义

（1.空军工程大学装备管理与安全工程学院，西安710051；2.解放军94906部队，江苏苏州215157）

基于复杂网络理论的航材配送网络抗毁性分析*

郑文强1，陈云翔1，庄骏2，蔡忠义1

（1.空军工程大学装备管理与安全工程学院，西安710051；2.解放军94906部队，江苏苏州215157）

航材配送是航材保障工作的重要环节，科学地构建航材配送网络是提高航材保障效率的前提和基础。深入开展航材配送网络研究，对提高航材保障工作效益具有重要意义。针对航材配送网络节点繁多、线路交错的特点，分析了航材配送网络的复杂特性，构建了基于复杂网络理论的航材配送网络模型，设计了航材配送网络的拓扑特征参数，研究了航材配送网络的抗毁性。理论分析和实验结果表明，随机攻击时航材配送网络的抗毁性要大于选择性攻击，节点选择攻击时航材配送网络的抗毁性小于边选择攻击。

航材保障，航材配送网络，复杂网络理论，抗毁性

0 引言

航材保障工作是装备保障工作的重要组成部分，做好航材保障工作对于装备效能的发挥具有重要意义［1］。作为航材保障的重要环节之一，航材配送一直是一个受到广泛关注的问题。航材配送涉及到配送网络规划、配送中心选择、配送路径优化等诸多问题，只有科学地构建航材配送网络，充分发挥航材配送网络的整体效能，才能有效提高航材保障的效率。

航材配送网络是一个包含了不同种类节点和错综复杂线路的复杂系统，各节点之间存在着信息和物质的交互作用，而且容易受到外界环境的影响。如果网络中的节点或线路遇到突发性事故，很可能造成整个网络的受损或瘫痪，这将会造成更为严重的后果。所以，要设计高效的航材配送网络，必须首先分析航材配送网络的特征，研究航材配送网络的结构。

目前，国内外已经有一些针对航材配送网络中心选址、配送路径优化的研究［2-3］，但是还没有针对航材配送网络整体结构特征的研究。具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质旳网络可以称为复杂网络［4］。1998年Watts与Strogatz提出的小世界网络概念和1999年Barabasi与Albert提出的无标度网络概念是现代复杂网络理论研究的开端，揭示了复杂网络的本质［5-6］。本文在对航材配送网络复杂特性进行分析的基础上，构建了基于复杂网络理论的航材配送网络模型，并设计了航材配送网络的拓扑特征参数，研究了航材配送网络的抗毁性。

1 复杂网络的基本拓扑特征

网络的拓扑结构对网络的性质有着重要的影响，用于描述复杂网络拓扑结构的特征有许多，本文重点研究了其中3类最为重要的特征：平均路径长度、度和介数。

1.1 平均路径长度

网络中连接两个节点的最短路径上的边的数目定义为这两个节点之间的距离，网络中任意两个节点之间距离的最大值称为网络的直径。假设网络中任意两个节点i和j之间的距离为dij，则网络的直径可以表示为：

不考虑节点到自身的距离，网络的平均路径长度可以表示为：

式（2）中N为网络中所有节点的数量。网络的平均路径长度刻画了网络中各个节点的分离程度。复杂网络的平均路径长度通常较小，因此，它具有小世界特性。

1.2 度和度分布

节点i的度ki定义为与该节点相连接的边的数目，可以应用网络的邻接矩阵进行定义：

其中aij表示邻接矩阵中的非零元素。一般认为度反映的是节点的重要程度，度越大，节点就越重要，在网络中的作用也越大，反之亦然。网络中所有节点的度的平均值称为平均度，即为＜k>。

网络中节点度的分布情况可以用分布函数P（k）来描述，表示了一个随机选定的节点度数恰好为k的概率分布，反映了网络系统的宏观统计特征。另外一种表示方法是累积度分布函数，表示的是度数不小于k的节点的概率。

随机网络的度分布是泊松分布，显示了网络中度分布比较均匀，不存在度数过高或过低的节点。小世界网络模型中，节点度分布服从泊松分布，而无标度网络的度分布则是幂律分布，节点度值相差悬殊，往往可以跨越几个数量级，常常偏离泊松分布，可以用P（k）～k-r表示。

1.3 介数和介数分布

一个节点的度可以从一个角度反映出这个节点在网络中的重要性，但不能完全反映其在网络中所处的地位和扮演的角色。介数就是用来描述相应节点或边在整个网络中作用和影响力的参量。节点的介数为网络中所有的最短路径中经过该节点的数量［7］。假设任意两个节点j与k之间的最短路径为σjk，其中经过节点的最短路径为σjk（i），则节点i的介数反映的是节点i在节点j与k之间的重要程度，可以表示为：

同度分布类似，介数分布表示的是随机选定的节点的介数恰好为Bi的概率分布。累积介数分布函数表示的是介数不小于Bi的节点的概率，如下式所示：

边介数的定义与节点介数类似，可以定义为通过该边的节点对之间的最短路径的数目，边e的介数反映的是边e在节点g与h之间的重要程度，可以表示为：

2 航材配送网络的复杂性分析

航材配送网络是由两个以上互相区别又互相联系的单元结合起来，以完成航材的实体流动为目的的有机结合体。航材配送网络的复杂性主要体现在3个方面：

2.1 航材配送网络结构的复杂性。

网络结构的复杂性通常体现在网络的大规模性和行为的统计性、连接结构的复杂性、网络连接的稀疏性等方面，而且航材配送网络通常会呈现出复杂的层次结构。因此，随着航材种类的不断更新和航材配送范围的不断扩大，为满足不同配送目标的需求，航材配送的网点将不断增加，航材配送网络会呈现出大规模发展的趋势。

2.2 航材配送网络节点的复杂性。

航材配送网络包含多种各自独立的实体，构成某一特定网络的实体在地理上一般是分散的，组织结构、技术水平、资源状况、职能等许多方面也不尽相同，这说明其节点自身存在复杂性。而当节点之间不停地进行航材的产生和转移时，这些节点之间已经不再是简单的起点与终点的关系，它们之间存在动力学行为的复杂性和同步运动的复杂性。

2.3 各种复杂性因素的相互影响。

实际的复杂网络会受到各种各样的因素影响和作用，从而使得网络产生时间和空间上演化的复杂性。影响航材配送运输效果的因素很多。动态因素如战争因素影响、自然灾害影响、车流量变化、道路施工、配送目的地的变动、可供调动的车辆变动等；静态因素如配送部队的分布区域、道路交通网络、车辆运行限制等。这些因素之间的相互影响以及对航材配送网络的影响使得配送网络在一定的时间和空间内进行演化，成为更加复杂的网络。

3 航材配送网络模型构建

鉴于航材配送网络具有的复杂特性，可以利用复杂网络理论构建航材配送网络的模型。首先将航材配送网络抽象为一个由节点集合V和边集合E组成的网络图。节点数记为，边数记为。E中每条边都有V中一对点与之相对应。如果任意点对（i，j）与（j，i）对应同一条边，则该网络称为无向网络，否则称为有向网络。如果给每条边都赋予相应的权值，那么该网络就称为加权（或有权）网络，否则称为无权网络，当然，无权网络也可以看成边权为1的等权网络。在此基础上，可以定义无向无权、无向加权、有向加权等网络。航材配送网络显然是一个有向加权网络，如图1所示，通常可以用邻接矩阵来刻画网络节点之间的相互关系，根据连接情况将每条边的权值赋予矩阵中，图中的邻接矩阵如式（8）所示。

图1 航材配送网络示意图

航材配送网络中的各个拓扑特征参数可以在向加权网络的基础上结合航材配送网络自身的特点进行定义。

3.1 平均路径长度

航材配送网络的平均路径长度描述的是网络中各个节点间的分离程度情况，能提供航空配送网络连通性的测度指标，可以直接用式（2）表示。

3.2 节点的度

由于航材配送网络是一个有向加权网络，因此首先要将一个节点的度分为出度（out-degree）和入度（in-degree）。节点的出度是指从该节点指向其他节点的边的数目，节点的入度是指从其他节点指向该节点的边的数目。节点i的出度，入度。其次，由于不同的边具有不同的权重，计算度数时还要考虑权重的影响，航材配送网络中边的权重主要是指配送路径的可靠性、安全性、路径长度、承载力等因素。最后需要考虑航材配送网络的特殊性，航材配送网络的每一个节点都会有库存航材，这对该节点的度数具有一定程度的影响。假设μi为节点i的初始库存，ωij和ωji分别表示边ij和ji的权重，节点i总度数可表示为：

3.3 节点的介数

介数表示的是信息流经某个节点的可能性，节点的介数值会随着经过该节点的信息流的变化而增大或减小，是动态变化的，利用介数这个统计特性能够找到信息负载大的网络节点。介数越大，说明流经该节点的数据分组就越多，该节点就越重要。由于介数可以反应出一个网络的动态特征，因此，它是分析航材配送网络中配送中心重要程度和网络受到影响后出现动态变化的重要特征参量。通常节点的介数表示为网络中所有的最短路径中经过该节点的数量，但是在航材配送网络中还需要考虑配送流量的影响，同样是最短路径，有的最短路径可能流量大，有的最短路径可能流量小，因此，介数会存在差别，在计算介数时需要考虑边权重的影响。假设ωjk表示节点j与k之间通过节点i的最短路径的权重，在式（6）的基础上，可以将航材配送网络的的介数表示为：

4 航材配送网络抗毁性分析

由于航材配送网络具有典型的无标度特性，利用复杂网络理论能够有效分析航材配送网络的抗毁性并为网络的设计和维护提供支持。本文采用了应用得最为广泛的抗毁性指标——网络全局效率和加权抗毁度进行分析。

4.1 网络全局效率

网络全局效率可以表示为［8］：

式（1）中G表示网络图，N为网络中节点的总数，εij节点i和节点j之间的连通性，是节点i和节点j之间最短距离dij的倒数。

为了评价不同节点失效后给整个网络带来的影响，可以定义一个毁伤指标D来衡量一个节点或边被破坏后导致的网络效率损失：

式（12）中，E0和E1分别表示初始网络和网络中部分节点或边失效后的网络全局效率。

4.2 加权抗毁度

其中Ni为与节点i直接连接的节点的集合，将与节点i直接相连的所有边的权值全部置1后，可以得到节点i到其他节点间最短路径上边权的总和为lij。节点i的权值si越大，位置重要度li越小，表示它与其他节点直接的联系越紧密，也表示它的作用越重要［9］。在此基础上，可以得出网络图G的加权抗毁度为：

式中分子表示网络图G中所有节点重要度之和，分母表示同等网络规模下全连通网络中所有节点重要度之和。显然全连通网络的加权抗毁度为1，加权抗毁度越接近于则1，网络连通性越好。

5 仿真实验

首先构建一个包括三级配送中心的模拟网络，如图2所示，网络中包括一级配送中心1个，二级配送中心4个，三级配送中心8个共13个节点，图中各边上的数值表示的是归一化的权重，权重为重点考虑路径长度，结合考虑路径可靠性、安全性、承载力、平均流量得到的结果。

图2 模拟航材配送网络示意图

图2中粗线为规划路径，细线为非规划路径，攻击主要围绕规划路径展开，如果攻击非规划路径则对网络不会产生实质性的影响。一级配送中心是该网络的顶点，假定它一旦受到攻击，整个网络瘫痪，抗毁性为0，因此，重点考虑的是攻击其他各节点时对抗毁性指标的影响。假设二级配送中心的库存μ2=3，三级配送中心的库存μ3=1，按照式（9）和式（10）可以计算各节点和边的度和介数，归一化后的结果如下页表1和表2所示。采用5种攻击方式进行模拟，分别是：

①随机节点破坏模式：随机移除网络中的节点；

②高度数节点破坏模式：按照度数的大小依次移除节点；

③高介数节点破坏模式：按照介数的大小依次移除节点；

④高度数边破坏模式：按照度数的大小依次移除节点；

⑤高介数边破坏模式：按照介数的大小依次移除节点。

表1 各节点的度和介数

表2 各边的度和介数

采用不同攻击方法对网络进行攻击后，得到的网络效率变化情况如图3所示，其中图3（a）是攻击节点的结果，图3（b）是攻击节点的结果。从图3（a）中可以看出，采用高度数节点破坏模式和高介数节点破坏模式时，网络的抗毁性相差不多，这是因为高度数节点和高介数节点基本一致。从图3（b）中可以看出，对边进行攻击时，高介数攻击比高度数攻击要更为有效，结合表2也可以发现，边的介数比度数更能反应边的重要性。比较图3（a）和图3（b）可以发现，对节点进行攻击比对边进行攻击对整个网络产生影响要更大一些，因此，节点对航材配送网络具有更重要的意义。

图3 网络效率变化情况分析

进一步分析不同节点破坏时的毁伤指标情况，如图4所示，基本上当度或介数较大的节点被破坏时，毁伤指标通常较大。但也有部分节点虽然度或介数很高，毁伤指标却较小，这是因为有些节点被破坏后，对整个网络的最短路径分布影响很大，此时对网络效率的影响也就很大，而有些节点发生被破坏后，对整个网络的最短路径分布影响很小，因此，它们的移除对网络效率的影响也就较小。

最后利用式（14）计算整个网络的加权抗毁度，可以得出网络的加权抗毁度为0.706 4，这一指标可以为网络抗毁度的优化提供依据。

图4 不同节点被破坏时毁伤指标情况分析

6 结论

本文从航材配送网络的特点出发，引入复杂网络理论，详细分析了应急物流网络的结构特征和抗毁性。首先分析了航材配送网络的复杂性，并在此基础上利用复杂网络理论构建了航材配送网络的拓扑模型，给出了航材配送网络的拓扑特征，最后，利用构建的航材配送网络拓扑模型分析了航材配送网络的抗毁性，为航材配送网络的设计提供了有效支持。理论分析和实验结果表明，随机攻击时航材配送网络的抗毁性要大于选择性攻击，节点选择攻击时航材配送网络的抗毁性小于边选择攻击。在进行航材配送网络规划时，可依据选择或随机攻击概率的大小合理规划网络布局。

［1］陈盖凯，王瑛，张毅.基于二元语义的高原地区航材配送中心选址决策研究［J］.数学的实践与认识，2012，42（10）：81-85.

［2］王瑛，陈盖凯，张毅.军用飞机航材配送中心选址方法与模型［J］.火力与指挥控制，2012，37（3）：204-207.

［3］何亚群，胡寿松.基于粗糙集的空军航材供应点的偏好选址［J］.系统工程理论与实践，2003，23（7）：95-99.

［4］史进.电力系统复杂网络特性分析与模型改进［J］.中国电机工程学报，2008，28（25）：93-98

［5］Watts D J，Strogatz S H.Collective Dynamics of'Small-world' Networks［J］.Nature，1998，393（5）：440-442.

［6］Barabasi A L，Albert R.Emergence of Scaling in Random Nnetwork［J］.Science，1999，286（12）：509-512.

［7］邱原.邢焕革基于复杂理论的作战网络关键边评估方法［J］.兵工自动化，2005，30（08）：22-25.

［8］吴俊.复杂网络拓扑结构抗毁性研究［D］.长沙：国防科学技术大学，2008.

［9］Holme P，Kim B J，Yoon C N，et al.Attack Vulnerability of Complex Networks［J］.Phys.Rev.E，2002，65（5）：056109.

Invulnerability Analysis of Aircraft Material Distribution Network Based on Complex Network Theory

ZHENG Wen-qiang1，CHEN Yun-xiang1，ZHUANG Jun2，CAI Zhong-yi1
（1.School of Materiel Management and Safety Engineering，Air Force Engineering University，Xi’an 710051，China；2.94906 Troops of PLA，Suzhou 215157，China）

Aircraft material distribution is an important part of aircraft material support.Scientific design of aircraft material distribution network is the foundation of aircraft material support efficiency. The study of aircraft material distribution network is significant for improving the effectiveness of aviation material support work.There are a lot of nodes and lines in aircraft material distribution network.In this paper，the complex characteristic of aircraft material distribution network is analyzed；the aircraft material distribution network model is designed based on complex network theory，the topological parameters of aircraft material distribution network is proposed;the invulnerability of aircraft material distribution network is studied.The theory analysis and simulation result show that the influence of random attacks for the network invulnerability is less than the influence of selective attacks，the influence of nodes selection attacks for the network invulnerability is larger than the influence of lines selection attacks.

aircraft material support，aircraft material distribution network，complex network theory，invulnerability

TP301

A

1002-0640（2015）02-0128-05

2013-12-23

2014-01-21

“十二五”国防预研基金资助项目（51327020104）

郑文强（1988-），男，北京人，硕士研究生。研究方向：装备维修保障。