基于功能链的作战体系复杂网络节点重要性评价方法

李尔玉　龚建兴　黄健　孔江涛

复杂网络是现实复杂系统的抽象,自Watts和Strogatz[1]对小世界网络的研究以及Barabasi和Albert[2]对无标度网络的研究以来,受到世界的广泛关注.复杂网络相关领域中,节点的重要度评价是重要课题之一.目前,对节点重要性评价有两种思想,一是“重要性等价于显著性[3]”,代表方法有度中心性[4]、特征向量中心性[4]、介数中心性[5]、接近中心性[6]等.二是“重要性等价于该节点(集)被删除后对网络的破坏”,通过分析删除某节点(集)前后网络结构的破坏来评价节点重要性,破坏程度的参考值有连通度、最短路径、紧密度等,代表方法有节点删除法[7]、节点收缩法[8]等.上述方法都是通过分析网络的拓扑结构特性得到节点重要性,在数学上有严格的证明,但很多时候与实际情况不符.度中心性虽然能表示节点获得资源的渠道数量,但没有考虑邻接节点的质量；介数中心性是最短路径的集中体现,但现实中还会考虑路径的安全性和节点(成员)的偏好.关于实际复杂系统的节点重要性评价方法,国内外有大量研究,针对蛋白质信息传递网络,Philip M等人在2007年提出瓶颈点识别法[9],Chungyen Lin等人提出最大邻居连通度识别法[10],杨汀依提出基于流量分布的关键性测度指标算法[11].针对互联网上网页的重要度排序,Kleinberg提出PageRank算法[12],何建军提出基于相似度贡献的节点重要度评价算法[13].但是,对于作战体系复杂网络分析领域,国内的研究还处于非常初步的阶段.自2004年起,国内军方相关人员才开始对此研究,其中李德毅院士[14]、胡晓锋教授[15]、卢厚清教授[16]等人先后对复杂网络在军事领域的应用进行了一些基础性研究,论证了其可行性.在作战体系复杂网络节点重要度评价方面,李茂林[17]等利用度、介数、紧密度和特征向量等常规统计特征对作战体系节点的重要性进行评估,并根据最大连通分支的大小、平均路径长度和紧中心性对作战体系受到攻击后的受损程度进行度量,提出了可供参考的节点重要度指标,但是评价指标没有针对作战体系的特点,结果的可靠性不高；金鑫[18]等利用复杂网络相关理论对各类卫星信息对作战效能的影响度进行了评估并排序,区分各类军事卫星在作战中的重要程度,也是一种变相的节点重要度评估,但是只对卫星进行评估,不是面向整个作战体系的.

作战体系是一个典型的开放式复杂巨系统,它有规模巨大、成员种类多、层次分明、关系复杂、受环境影响不断演化的特点.所以,对作战体系复杂网络的节点重要度的评估结果中,应当能够体现不同功能节点、不同层次节点的重要度差别.并且,不同作战任务环境下,节点重要度评估结果也不应该相同.综上所述,本文提出一种基于功能链的作战体系网络节点重要性评价方法.根据作战需求,将作战体系网络中不同功能的节点按其作用时序组成链状结构,形成能够完成特定任务的最小整体,称之为功能链.最后根据网络中功能链的构成情况,对节点重要度进行排序.本文的组织结构如下:在第1部分,分析作战体系网络的组成及结构特点,并提出作战体系网络节点重要性排序应当具有的分布特点；在第2部分,介绍功能链以及基于功能链的节点重要度排序方法,给出了具体算法流程和实例分析；在第3部分,给出了3组对照仿真实验,以证明算法的有效性；在第4部分,对排序方法进行总结.

1　作战体系网络节点重要度

一个复杂网络G=(V,E)由节点集合V={v1,v2,···,vn}和边集E={e1,e2,···,en}构成. 本文将作战单元抽象为节点,作战单元之间的联系抽象为边,分别构成作战体系网络的点集V和边集E.作战体系网络由于其自身特点,要对其进行准确的分析,首先要建立能准确描述其特征的复杂网络模型.

1.1　作战体系复杂网络

对比通信网、交通网、WWW网等,作战体系网络最大的特点就在于其节点的异质性.作战体系网络中节点的异质性表现在物理结构、层次、功能等方面,在复杂网络中描述该系统时就应该体现这些性质.本文认为,作战体系网络中的节点不应该只具有“编号”这一单一属性,而应该是一系列属性的集合.本文定义节点V={id,ability,name,level,neighbours{}},其中,

id:节点编号,由阿拉伯字母表示；

ability:节点能力,分别由字母 “A”～“F”抽象表示,其中“A”代表指控功能节点；

name:节点名称,由 “id”+“ability”组成；

level:节点所在的层次；

neighbours{}:节点的邻接节点,其中,除顶层节点外,第一个邻接节点为自身的父节点.

传统的作战体系网络是一种描述指控关系的树状图,网络中节点为各级指挥所[19].树状图中,叶子节点为低级指挥所下各种能力的作战实体.作战中的上下级指控关系作为网络模型中节点间的连边,将网络中的节点划分为不同层次,形成纵向上层次分明的特点,如图1(a)所示.现在,在信息化时代的背景下,为响应作战体系化、联合化以及指控体系扁平化的要求,实际的作战体系中应同时包含逐级指挥关系、机构内部协同关系、机构之间协同关系和跨级指挥关系[20].本文认为,作战体系网络可以归类为一种组织结构网(DWS),组织结构网是一种同时具有树形骨架和隐含连接的层级网络.作战体系网络以指控关系构成的树状图作为整个网络的支撑,再以树状图为基础添加隐含连边,如图1(b)所示.每种节点对之间的连接概率不同,相同指挥体系下的节点间更容易相连,同时跨越层数越少也越容易相连.

图1　两种不同形式的指控网络图

1.2　分析思路

由于作战体系网络以层次化树状图为主体结构,其高层节点应当更偏向于处于重要地位.李茂林用度指标、介数指标、紧密度指标以及特征向量指标对作战体系网络进行分析,但从结果来看,各指标间偏差较大,也无法区别出不同层级的重要度分布.这是由于:1)在上述作战体系模型下,指控关系组成的树状图中,除了叶子节点的度为一之外,其他节点的度基本相似；在之后的隐含连边添加上,每个节点增加连边的总体概率大致相同,因为越高层节点有更多的跨级指挥关系,但有更少的同层协同关系,越低层节点则反之.这使得作战体系网络中节点度的异质性不大.2)以网络为中心的战场上,作战网络形式非常紧密,很少存在起桥梁作用的节点.如果从体系架构上来看,中层指控节点会具有更高介数,这使得它们的重要性高于更高层指控节点,显然与事实不符.3)中层节点以更大概率处于网络中心,同时也会导致按紧密度排序的结果中,中层节点重要度最高,显然也不符合实际.4)作战体系网络中,许多节点在网络中却不在任务中,同时也有许多连接没有实际价值,以上算法均不能判别这种情况.

本文认为,针对作战体系网络,一个合理有效的节点重要度排序方法,应当既能凸显不同层级间重要度差别,又能描述同层间重要度高低顺序,同时也要能找出低层高重要度的特殊节点.另外,作战体系中节点存在的价值在于完成作战任务,而单一节点往往无法完成一个作战任务,尤其是具有协同性质的任务.通常,一项作战任务可以分解为多个步骤,每个步骤由不同能力作战单元完成,以此形成时序上有先后的作战整体.因此,作战体系网络中节点重要度的评价应当从节点组合的整体价值着手.

1.3　作战体系网络相关研究方法

近几年来国内外对作战体系网络的建模方法和分析方法的研究越来越深入,自有网络中心战[21]趋势以来,传统的树状层级指控网络已不能适应现代战争,应运而生的有美国Jeffery R.Cares[22]提出的信息时代战斗模型(Information Age Combat Model,IACM),同时澳大利亚国防科工组织(DSTO)Anthony Dekker[23]开展了基于不同的网络生成规则研究作战网络的作战效能的项目.在国内,王运民[24]、权良涛[25]等人考虑了通信能力、作战任务、武器装配等节点属性以及所在层级、所在体系等网络属性,从不同的角度为传统层级树状指挥网络添加隐含连边,不同程度地压缩了指控网络的层次,构建了扁平化联合作战体系模型.其中权良涛还考虑节点自身属性,为不同功能节点设计对应属性集合,在模型中体现.卞泓斐[26]和姜志鹏[27]等人均综合考虑了节点自身属性和节点在网络中的结构属性来评估作战体系网络的节点重要度,自身属性通常根据作战任务评估节点能力与任务的适应度,结构属性通常以度中心性、介数中心性、接近中心性等指标评估.虽然已有同时考虑节点自身属性和结构属性的重要度评估方法,但都是两者的线性组合,形式上做到了两者的结合,实际上并没有.

2　基于功能链的节点重要性评估方法

军事对抗可以看成是一个博弈的过程,博弈双方的最小整体被称为局中人[28],而不是个体,局中人就是形成该整体的个体总价值的最佳体现.受局中人的概念启发,对作战体系的分析不能离开整体价值这一指标,而军事行动的价值则是建立在作战功能的形成上.在任何时代的军事对抗中,一次作战都需要不同能力的部队的配合,这是由于单个作战单元作战能力非常有限,需要由多种功能作战单元组合协同才能体现最大作战能力.

2.1　功能链的定义

本文将根据作战任务在时序上分先后不同功能的节点构成的链状结构定义为功能链.以作战环分析[29]为例,根据作战环对作战过程的划分,作战环将其映射到作战体系建模中,形成4个不同功能节点,分别为传感器Sen、决策器Dec、影响器Inf、目标Tgt.如图2所示,作战环包括4种类别的节点,其中S为侦查节点、D为决策节点、I为打击节点、T为目标节点.那么针对目标T,链路“S→D→I”就形成了一种消灭“T”的功能链.

图2　作战环示意图

2.2　基于功能链评价节点重要性

基于功能链进行节点重要度评估,首先要根据作战需求确定作战任务t的清单T,例如,若确定作战任务为{火力压制,打击敌方外围作战力量,部署防空力量},抽象为T=[t1,t2,t3].根据功能链的定义,清单中每种功能链由网络中能先后连接的且功能一一对应的节点构成.由于作战体系复杂网络中各节点所在层级不同、功能不同、邻接节点功能不同,每个节点能构成功能链的种类、数量也必然不同.本文认为,一个节点能构成的所有种类的功能链总和越多,重要度也就越高.设任务清单为T=[t1,t2,···,tn],记节点vi构成功能链tj的数量为cij,那么最终的节点vi重要度Valuei为

2.3　指控节点的处理

在作战体系中,指控单元作为整个体系的“骨架”处于十分重要的位置.其中,一级指挥所(id=1)显然处于极其重要的位置,在重要性排序中更倾向于排在前列.但是,在作战体系复杂网络中,顶层节点与其他节点存在隐含节连接的概率并不比其他层次的节点多很多,并且在第一步建立网络“骨架”时,顶层节点还无法与底层功能节点建立直接联系,所以如果单纯使用路径搜索得出的重要度排序结果,不能凸显指控节点的重要性,与事实不符.于是,本文认为,当低级指控节点与其他功能节点构成一条功能链,其父级指控节点也能构成同样的功能链.如图3所示,若定义“A→B→D”为一种功能链,那么路径“2A→4B→6D”就构成了这种功能链.并且,节点“1A”为与节点“2A”相连的父级节点,所以本文认为路径“1A→2A→4B→6D”也构成了这种功能链.

图3　高级指控节点示例

在这里,本文给出如下两个定义:

定义1.最小功能链.删除任何节点都将不能构成该功能的功能链.

定义2.冗余功能链.存在两个或者两个指控节点的功能链.

不过,这种做法虽然可以凸显高级指控节点的重要性,但仍需考虑信息流转效率的问题.路径 “1A→2A→4B→6D”虽然能构成功能链,但与“2A→4B→6D”相比,由于多一层指控节点,信息流转效率必然降低.本文认为,父级节点虽然可以从其子指控节点处构成的功能链中获得重要度,但重要度增量应随效率的降低而降低.通常,两节点间通信效率与距离成反比[30],故父级指控节点获得的额外重要度增益应当有一个与路径长度相关的衰减.本文规定该衰减I为

其中系数α为小于1的正实数,lorg为遍历最小功能链所有节点后路径总长度,lext存在两种情况,如图4(a)所示,冗余功能链中指控节点若为Ⅰ型连接,那么遍历整个功能链不需要重复经过路径,此时lext为3；如图4(b)所示,冗余功能链中指控节点若为Y型连接,遍历整个功能链需要重复经过路径,此时lext为4.此外,有可能出现多级的父级指控节点,按照该方法迭代.

图4　高级指控节点处于功能链的不同位置

2.4　算法流程

本文以DWS网络建模方法建立作战体系复杂网络模型,在此基础上,根据作战体系网络节点的多样性,加入节点的功能标签.设有图G=(V,E),具体步骤如下:

步骤1.输入功能链集合T={t1t2,···,tn},ti={ai1,ai2,···,ain}为一种功能链.

步骤2.建立集合St存储所有实体功能链s,设i=1.

步骤3.在Vt中取功能链ti={ai1,ai2,···,ain},在图G中用路径搜索算法找到所有符合功能链ti的节点集合{v1,v2,···,vn},即集合中每个节点的功能按功能链中顺序与功能链中功能相匹配,将该节点集合记作实体功能链si并入栈操作进入集合St.

步骤4.如果i＜n,令i+1,重复步骤3；若i=n,设j=1,进入步骤 5,此时St={s11s12,···s1m(1),s21,s22,···s2m(2),···sn1,sn2,···snm(n)},其中m(i)为第i种功能链对应的功能链实体总数.

步骤5.取St中功能链实体sj,为实体sj中每个节点增加一点重要度,若sj可以构成冗余功能链,则转入步骤6；若sj不可构成冗余功能链,且令j+1,重复本步骤；若进入步骤7.

步骤6.根据2.3节方法为冗余功能链实体中每个父级增加额外重要度.

步骤7.对每个节点按重要度进行排序,输出排序结果.

3　实验设计

由于DWS网络结构与作战体系网络结构类似,本文按照DWS网络构建方式构建网络模型[31],步骤如下:

步骤1.生成节点,建立指控关系骨架网络.从一个中心节点开始,在中心节点下随机生成3～5个子节点,接着为新节点再随机生成3～5个子节点,重复此步骤直到节点数达到50.

步骤2.为骨架网络中,有子节点的节点功能标记为“A”,即指控功能节点,为叶节点随机标记功能“B”～“F”.

步骤3.为网络中各节点对之间按如式(3)给出的概率规则建立链接.

其中λ和ξ是可调参数,Dij为两节点最近共同父节点的深度,di与dj为节点深度.共进行了4组实验.

3.1　基于功能链节点重要度排序方法与其他方法对比实验

首先建立了50个节点的DWS网络,分别用基于功能链的节点重要度排序方法、度中心性节点重要度排序方法、PR值排序方法和瓶颈点排序方法进行分析,并进行归一化处理.其中DWS建立的各参数为:λ=6、ξ=3、α=0.4,构建出的网络层数为4,共有13个指控节点.网络模型如图5所示.

图5　具有50个节点的复杂网络图

从图6中可以看出,由于PageRank算法与节点度相关性很高,所以排序结果与度中心性相似性很高,除此之外,各方法得出的排序结果间差别较大.图6(a)显示,基于功能链的节点重要度排序方法将1号节点排在首位,重要度排前十的节点中指控类节点占4个,重要度排前五的节点中指控节点占3个；图6(b)显示,基于度中心性的节点重要度排序方法将1号节点排在第13位,重要度排前十的节点中指控类节点占5个,重要度排前五的节点中指控节点占4个；图6(c)显示,基于PageRank的节点重要度排序方法将1号节点排在第13位,重要度排前十的节点中指控类节点占5个,重要度排前五的节点中指控节点占4个；图6(d)显示,基于瓶颈点的节点重要度排序方法将1号节点排在第21位,重要度排前十的节点中指控类节点占5个,重要度排前五的节点中指控节点占4个.从实验结果可以看出,首先基于度中心性和基于PageRank的节点重要度排序结果中各节点重要度差异较小,基于功能链和基于介数中心性的节点重要度排序结果中节点重要度梯度较明显,有更高的参考价值；其次,除基于功能链的节点重要度排序将一号节点放在最重要位置,其他排序方法均没有评估出一号节点的高重要度；最后,4种排序方法均能体现指控节点重要度偏向于更高这一实际情况.综上,基于度中心性、基于PageRank和基于介数中心性的节点重要度排序实验结果与第2.2节分析一致,基于功能链的节点重要度排序结果明显优于其他方法.

3.2　不同λ和ξ对重要度排序结果的影响

根据不同网络隐含连接参数建立200节点DWS网络,每组参数进行了50次实验,当λ=2、ξ=2时,排在前1/4的节点中指控类节点占比为0.336,1号节点排13.4位；当λ=5、ξ=5时,排在前1/4的节点中指控类节点占比为0.444,1号节点排1.6位；当λ=2、ξ=4时,排在前1/4的节点中指控类节点占比为0.372,1号节点排3.8位；当λ=2、ξ=8时,排在前1/4的节点中指控类节点占比为0.428,1号节点排3.2位；当λ=4、ξ=2时,排在前1/4的节点中指控类节点占比为0.368,1号节点排30位；当λ=8、ξ=2时,排在前1/4的节点中指控类节点占比为0.372,1号节点排19位；

综上,λ和ξ增大都会使得指控节点整体排位提前,ξ增大会使得1号节点排位提前,同时节点重要度变化会更加平滑.

3.3　不同α对重要度排序结果的影响

根据不同的冗余功能链额外重要度衰减系数计算节点重要度,每组参数进行了50次试验,当α=0时,排在前1/4的节点中指控类节点占比为0.312,1号节点排15位；当α=0.1时,排在前1/4节点中指控类节点占比为0.4,1号节点排6.8位；当α=0.2时,排在前1/4的节点中指控类节点占比为0.468,1号节点排2.2位；当α=0.3时,排在前1/4的节点中指控类节点占比为0.432,1号节点排2位；当α=0.4时,排在前1/4的节点中指控类节点占比为0.488,1号节点排1.4位；当α=0.5时,排在前1/4的节点中指控类节点占比为0.452,1号节点排1位.

图8　不同衰减系数对照实验

综上,系数α增大会提高1号节点排位,同时在α较小时,会提高指控节点的整体排序,在α较大时,对指控节点整体排序无明显影响.

4　结论

本文面向作战任务,基于不同功能个体联合后的整体价值,提出一种新的针对作战体系复杂网络的节点重要度评价方法,称为基于功能链的节点重要度评价方法.与其他现有的节点重要度评价方法相比,本文提出的方法,考虑到了作战整体,根据实际情况制定功能链,调节衰减系数,所以更具有实用性.从排序结果来看,本方法曲线比较光滑,同时节点间重要度差别也比较明显,最高与最低重要度节点间差距将近50%,可以很容易判断出作战重心.

但是,本文仅考虑了链状结构的作战整体,但实际中许多作战整体不是链状结构的.针对非链状结构的任务团进行节点重要度评价,是下一步的研究工作.

1 WATTS D J,STROGATZ S H.Collective dynamics of“small-world”networks[J].Nature,1998,393(6684):440−442.

2 ALBERT R,JEONG H,BARABASI A L.Error and attack tolerance of complex networks[J].Nature,2000,406(6794):378.

3 BURT R S,MINOR M J.Applied network analysis:a methodological introduction[J].Canadian Journal of Sociology,1983,63(3):205-207.

4 BONACICH P.Factoring and weighting approaches to status scores and clique identification[J]Journal of Mathematical Sociology,1972,2(1):113−120.

5 FREEMAN L C.Centrality in social networks[J].Social Networks,1979,1.

6 FREEMAN L C.Centrality in social networks conceptual clarification[J]Social Networks,1978,1(3):215−239.

7 CORLEY H W,SHA D Y.Most vital links and nodes in weighted networks[M].Operations Research Letters,1982,1(4):157−160.

8谭跃进,吴俊,邓宏钟.复杂网络中节点重要度评估的节点收缩方法[J].系统工程理论与实践,2006(11):79-83.

9 YU H,KIM P M,SPRECHER E,et al.The importance of bottlenecks in protein networks:correlation with gene essentiality and expression dynamics[J].PLOS Computational Biology,2007,3(4):0713−0720.

10 LIN C Y,CHIN C H,WU H H,et al.Hubba:hub objects analyzer–a framework of interactome hubs identificatio for network biology[J].Nucleic Acids Research,2008,36(Web Server issue):W438−W443.

11杨汀依.复杂网络关键节点识别技术研究[D].南京:南京理工大学,2011.

12 BRIN S,PAGE L.The anatomy of a large-scale hypertextual web search engine[J].Computer Networks and ISDN Systems,1998,30(1−7):107−117.

13何建军.复杂网络节点重要性评价研究[D].长沙:湖南大学,2010.

14李德毅,王新政,胡钢锋.网络化战争与复杂网络［J］.中国军事科学,2006,19(3):111−119.

15胡晓峰,李志强,贺莜媛,等.复杂网络:战争复杂系统建模仿真新途径［J］.装备指挥技术学院学报,2009,20(2):1−7.

16卢厚清,宋以胜,付成群.复杂网络是军事科学研究的一种新方法［J］.解放军理工大学学报(综合版),2009,10(4):72−74.

17李茂林,龙建国,张德群.基于复杂网络理论的作战体系节点重要性分析[J].指挥控制与仿真,2010,32(3):15−17.

18金鑫,毕义明,李瑛.卫星信息支援对作战效能影响度评估方法研究[J].系统仿真学报,2008(19):5066−5070.

19俞杰,王伟,张国宁.基于复杂网络的联合作战指挥体系研究[J].火力与指挥控制,2011,36(2):5−10.

20张强,李建华,沈迪,等.基于复杂网络的作战体系网络建模与优化研究[J].系统工程与电子技术,2015,37(5):1066−1071.

21杰夫凯尔斯,JeffCares,凯尔斯,等.分布式网络化作战:网络中心战基础[M].北京:北京邮电大学出版社,2006.

22 CARES J R,INCORPORATED A.An information age combat model[J].Paper for ICCRTS,2004,27(404):103−105.

23 DEKKER A.Applying social network analysis concepts to military C4ISR architectures1[J].Connections,2002,24(3):93−103.

24王运明,崔怀健,陈波,等.基于边连接策略的指控网络模型研究[J].指挥与控制学报,2016,2(1):40−46.

25权良涛.基于复杂网络理论的作战体系网络建模研究[D].西安:西安电子科技大学,2012.

26卞泓斐,杨根源,陈榕.舰艇编队网络化防空体系中节点重要度评估[J].兵器装备工程学报,2015,36(8):15−19.

27姜志鹏,张多林,王乐,等.多维约束下指挥网络节点重要度的评估方法[J].解放军理工大学学报(自然科学版),2015(3):294−298.

28鲁大剑.面向作战推演的博弈与决策模型及应用研究[D].南京:南京理工大学,2013.

29鲍鲜鲲.基于复杂网络的作战同步建模与分析[D].长沙:国防科学技术大学,2009.

30贺磊,王直杰.基于复杂网络的供应链网络效率研究[J].计算机仿真,2012,29(8):183−186.

31 DODDS P S,WATTS D J,SABEL C F.Information exchange and the robustness of organizational networks[J].Proceedings of the National Academy of Sciences of the United States of America,2003,100(21):16−21.