基于PageRank算法的武器装备体系重要节点评估*

李 锴，吴 纬，刘福胜，陈庚申，陈守华

（1.装甲兵工程学院，北京 100072；2.后勤学院，北京 100858）

基于PageRank算法的武器装备体系重要节点评估*

李 锴1，吴 纬1，刘福胜1，陈庚申2，陈守华1

（1.装甲兵工程学院，北京 100072；2.后勤学院，北京 100858）

将武器装备系统抽象为网络节点，利用复杂网络理论研究评估武器装备体系中的重要节点。针对传统PageRank算法在该应用中存在的问题，提出一种修正的PageRank算法。该算法对悬挂节点及有向环状网络节点的重要度评估具备收敛性。仿真实例验证了该修正算法对双目标作战环节点重要度评估的有效性。为了进一步验证所提算法的准确性，引入特征谱理论和移除节点法评估网络的抗毁性。

PageRank算法，武器装备体系，复杂网络，节点重要度

0 引言

在一体化联合作战背景下，体系作战的概念在网络中心战的基础上被提出并被深入研究。在体系作战的整体进程中，各种武器平台和武器装备系统通过信息系统与技术构成武器装备体系［1］。武器装备体系是在一定的战略指导、军事指挥以及综合保障的前提下，为完成一定的使命任务，按照作战规律，将一定数量、不同种类和型号的主战装备、电子信息装备以及综合保障装备等武器装备系统，通过信息系统与技术综合起来的功能整体［2-4］。

复杂网络可以看作是对复杂系统的抽象数学模型，利用复杂网络对武器装备体系进行研究取得了许多研究成果［5-7］。采用复杂网络理论对武器装备体系进行研究时，主要利用数学图论和统计物理理论展开研究，基本方法是：将武器装备体系抽象为一个图 G=（V，E），节点集 V={v1，v2，…，vn}表示体系中各武器装备平台和武器装备系统，如指挥控制中心和火力打击系统；有向边集 E={e1，e2，…，en}表示体系中的信息流、物质流和能量流及各武器装备节点间的协同控制关系［8］。通过将武器装备体系抽象为图的方式，整个战场空间中的装备实体及交互关系构成一个复杂网络，采用统计物理方法，对武器装备体系复杂网络的整体统计特性进行相关研究［9］。

体系对抗的本质是对敌方武器装备体系的重要节点实施打击，通过体系干扰和体系退化，达到克敌制胜的作战目标。现阶段对网络节点重要度的评估主要有两种方法［10-11］：一是从复杂网络的拓扑结构出发，通过节点度、介数和中心性等度量参数来评估节点的重要性，如跳面节点法；二是通过移除节点和连接边的方式，考察网络的抗毁性变化，以此对网络节点的重要度进行评估，如生成数目法。研究发现，以上方法对不具备连通性的复杂网络不能适用，因此，需要提出新的网络节点重要度评估方法。研究武器装备体系重要节点，对于保己克敌，制定作战方案具有重要的战略意义，同时为武器装备体系的下一步发展提供参考。

1 基本PageRank算法

PageRank算法的基本思想是：网络中节点的重要度不仅由节点的度值决定，还与其邻居节点的重要度有关，该算法的优势在于将复杂网络作为整体研究，从全局进行考虑，不是以孤立的节点为研究对象［12］。

基本PageRank算法的主要步骤为：

1）对网络中的所有节点设定PageRank初值（简称PR值），为网络中的节点数目。

2）在k-1步时，将节点i的PR值平均分给其指向的邻居节点。简单来说，若节点i的出度值为mi，那么节点i所指向的所有邻居节点从节点i处分配到的PR值为。若节点i的出度值为0，则节点i在k-1步时只能接受其他节点分配的PR值。

节点i的PR值结果为它最终分配得到的PR值之和：

其中：aji为有向网络G的邻接矩阵A（G）中的元素，若存在边由节点j指向节点i，则aji=1，否则aji=0。

需要说明的是：网络G中的所有节点的PR值总和是不变的，即对于k∈Z+，恒成立。

基本PageRank算法可以写成矩阵形式，具体如式（2）所示：

表1 8个节点的PR值计算结果

在复杂网络研究中，通常将出度值为0的节点称为悬挂节点（Dangling Node），通过研究发现，基本PageRank算法对于悬挂节点是失效的，无法对悬挂节点进行PR值计算。同时对于环状结构的复杂网络，基本PageRank算法也可能会出现无限循环而不能收敛的情况。对于图2中的有向环状网络结构，经过5次迭代后，PR值又重新回到初值，因此，需要对基本PageRank算法进行改进。

2 修正PageRank算法

修正PageRank算法的基本思想是：从当前节点i出发，不论节点i是否为悬挂节点，都将以一定的概率随机选择网络中的任意其他节点作为节点i的出度目标节点。

修正PageRank算法的主要步骤为：

1）对网络中的所有节点设定PageRank初值（简称PR值），为网络中的节点数目。

2）给定一个收缩因子 t∈（0，1），按照基本PageRank算法计算节点的PR值，再利用收缩因子t对网络中所有节点的PR值进行缩减，此时网络中节点的PR值满足。

3）将1-t的PR值平均分给网络中的N个节点，则悬挂节点PR值为，整个网络的PR值总和满足。

节点的修正PR值为：

修正PageRank算法可以写成矩阵形式，如式（5）所示：

对于收缩因子t的取值，需要充分考虑到算法的有效性和收敛性［13］：若 t→1，则收敛速度愈慢，当t=1时，算法则无法收敛；若t→0，则收敛速度愈快，当t=0时，算法在计算环状网络时可能会无限循环。对于收缩因子t的取值，建议为t=0.85［12］。

3 实例应用

3.1 实例分析

从复杂网络理论中节点和连接边的分类出发，Cares建立了基于信息网络的作战模型［14］，将武器装备体系的武器平台和武器装备系统分为4类节点：决策节点（Decider）、响应节点（Influencer）、传感器节点（Sensor）和目标节点（Target）。现代战争的作战形式是一个循环反复的过程：传感系统发现目标后，通过信息传输系统将目标信息传递给指控系统，指控系统经过分析决策后向火力系统下达攻击命令，火力系统接到命令后对目标节点实施打击。图3为双目标节点作战环结构示意图，图中有向边分别表示信息流、物质流和能量流及武器装备系统间的控制协同关系。

利用修正PageRank算法对图3作战环中武器装备体系节点的重要性进行评估，收缩因子t=0.85，计算结果如表2所示。图3所示作战环的武器装备体系中节点重要度评估结果为。

3.2 结果验证

为验证修正PageRank算法评估结果的准确性，利用特征谱理论和移除节点法评估图3网络的抗毁性，基于抗毁性的测度连通度来表征节点的重要性［15］，将两种评估结果进行比较分析，证明修正PageRank算法是否具备可行性。

表2 双目标作战环节点PR值结果

设网络G有N个节点，根据矩阵理论，邻接矩阵A（G）包含有N个特征值，分别记为由于A（G）不是对称矩阵，因此中会存在共轭复数。

对于k阶矩Mk而言，临界矩阵A（G）中的元素为1或 0，若，说明存在一条长度为k的闭合回路，起点和终点均为节点i1。NMk表示网络G中长度为k的闭合回路的数目。

复杂网络连通度是抗毁性的重要测度之一，网络中节点和连接边的冗余程度决定网络连通度的大小。通常采用网络中节点对之间的路径数目C来表征网络的连通度：

其中：mk为长度为k的闭合回路的数目。

对于节点i而言，若存在长度为k的闭合回路，从理论上来讲，该闭合回路可重复计算，故闭合回路的长度k→+∞，C无法收敛；同时网络闭合回路越长，包含的节点和连接边的数目越多，则该路径的抗毁性越低，因此，对C引入加权系数，得到：

对于复杂网络G而言，C'值越大，说明网络G的路径冗余程度越大，连通度越高，抗毁性越强。图3双目标作战环中C'=1.393 3。采用移除节点和连接边的方式，分别计算移除节点后其网络子图的C'值。若C'值下降程度较大，则说明移除的节点对网络的抗毁性影响较大，该节点的重要度较高，计算结果如表3所示。

表3 移除节点后网络的值

从表3的计算结果可以看出，移除节点S3后网络G的C'值最小，说明在移除节点后网络的抗毁性下降程度最大，节点S3是该网络中重要度最高的节点。从网络全局来看，基于谱测度理论，节点重要性的顺序为：，该结果与修正PageRank算法的结果一致，说明修正PageRank算法具备可行性。

4 结论

本文给出修正PageRank算法对复杂网络中节点重要性评估的理论方法，依据作战循环理论，建立双目标的作战环，对武器装备体系中的节点重要性进行研究，并通过特征谱理论对修正PageRank算法评估结果进行验证，证明了修正PageRank算法的可行性。在体系对抗过程中，可采用修正PageRank算法对武器装备体系的装备节点进行重要性评估，采取保护自身重要节点和打击敌方重要目标的作战方式，达到克敌制胜的作战目标。

［1］张强，李建华，沈迪，等.基于复杂网络的作战网络建模与优化研究 ［J］.系统工程与电子技术，2015，37（5）：1066-1071.

［2］倪忠仁.武器装备体系对抗的建模与仿真［J］.军事运筹与系统工程，2004，18（1）：2-6.

［3］卜广志.武器装备体系的体系结构与体系效能［J］.系统工程与电子技术，2006，28（10）：1544-1548.

［4］游光荣，初军田，吕少卿，等.关于武器装备体系研究［J］.军事运筹与系统工程，2010，24（4）：15-22.

［5］ALFREDO G，ANDREA T.On the reliability analysis of systems and SoS：the RAMSAS method and related extensions［J］.IEEE Systems Journal，2015，9（1）：232-241.

［6］ENDER T，LEURCK R F，WEAVER B，et al.Systems-of-Systems analysis of ballistic missile defense architecture effectiveness through Surrogate modeling and simulation［J］.IEEE Systems Journal，2010，4（2）：156-165.

［7］吴忠杰，张耀中，杜支强，等.复杂网络理论下军事体系对抗的研究进展［J］.复杂系统与复杂性科学，2014，11（4）：52-61.

［8］吴金闪，狄增如.从统计物理学看复杂网络研究［J］.物理学进展，2004，24（1）：18-46.

［9］刘涛，陈忠，陈晓荣.复杂网络理论及其应用研究概述［J］.系统工程，2005，23（6）：1-7.

［10］李琳，刘稚奇.通信网节点重要性的多指标评价方法［J］.海军工程大学学报，2010，22（5）：69-73.

［11］李茂林，龙建国，刘伟涛.信息化条件下作战体系节点重要性指标的选择［J］.火力与指挥控制，2011，36（8）：119-121.

［12］汪小帆，李翔，陈关荣.网络科学导论［M］.北京：高等教育出版社，2015.

［13］钱功伟，倪林，MIAO Y，等.基于网页链接和内容分析的改进PageRank算法［J］.计算机工程与应用，2007，43（21）：160-164.

［14］CARES J R.Distributed networked operations the foundations of network centric warfare ［M］.Landeda：Alidade Press，2004：36-59.

［15］齐新社，宋晓峰，杨东升，等.基于谱测度的地域通信网络节点重要性评估［J］.火力与指挥控制，2012，37（7）：51-53.

［16］赵永毅，史定华.复杂网络的特征谱及其应用［J］.复杂系统与复杂性科学，2006，3（1）：1-12.

［17］谭跃进，张小可，杨克巍.武器装备体系网络化描述与建模方法［J］.系统管理学报，2012，21（6）：781-786.

［18］陆皖麟，何新华，屈强，等.基于SEM的武器装备体系作战能力关联关系判定方法［J］.兵器装备工程学报，2016，36（8）：38-42.

Evaluating Nodes Importance in Equipment System-of-Systems Based on PageRank Algorithm

LI Kai1，WU Wei1，LIU Fu-sheng1，CHEN Geng-shen2，CHEN Shou-hua1
（1.Academy of Armored Force Engineering，Beijing 100072，China；2.Logistics Academy，Beijing 100858，China）

To research the equipment System-of-Systems based on the complex network theory，the equipment systems are regarded as the nodes in the network.In this paper，the nodes importance in equipment System-of-Systems is evaluated based on the amendatory PageRank algorithm to avoid the deficiencies of the basic PageRank algorithm.The amendatory PageRank algorithm possess convergence with dangling node and directed circular network.The simulation results show the amendatory PageRank algorithm could be used to evaluate the nodes importance for two targets combat circle.Finally the results of the nodes importance is conformed based on the spectral measure and node removed process to assess theinvulnerability of the network.

PageRank algorithm，equipment system-of-systems，complex network，nodes importance

E917

A

10.3969/j.issn.1002-0640.2017.11.08

1002-0640（2017）11-0034-04

2016-09-21

2016-11-09

装备技术基础基金资助项目（2015H04）

李 锴（1990- ），男，山东淄博人，博士研究生。研究方向：武器装备体系建模仿真及评估。