0 概述

信息化条件下的指挥控制网络通过物理通信网络连接形成各种非线性逻辑关系, 网络结构具有非线性、层次性及适应性等复杂网络特征^[1]。瞬息万变的复杂战场环境对于指挥控制网络的抗毁性提出了更高的要求^[2]。目前, 指挥控制网络大多通过保护关键节点来提高网络抗毁性, 没有考虑关键边的作用。而关键边是作战单元之间信息传输的主要通道, 也成为敌方攻击的重点目标^[3]。关键边一旦被摧毁, 信息传输将会遭受重大破坏, 导致整个网络瘫痪, 从而影响作战进程, 甚至可以决定战争的胜负。因此, 识别关键边已成为提高指挥控制网络抗毁性的一个研究方向。

目前, 已有部分学者对复杂网络中边的重要性进行了基本研究, 但在利用关键边来提高网络抗毁性方面的文献仍相对较少。

在网络关键边重要性评估方面, 文献[4]提出一种节点度和介数相关的边权重模型, 通过调整2种指标占边权的比重, 增强边对额外负载的承载能力。文献[5]在社团网络拓扑结构划分中, 提出基于边介数的边重要性评估方法。文献[6]提出一种基于复杂理论的作战网络关键边评估方法, 但方法只是将节点的度与介数进行算术计算, 并未考虑网络的拓扑性。

在网络桥接属性方面, 文献[7]综合考虑了节点的邻居数量及其与邻居间的拓扑结构, 利用节点的度属性和桥接属性计算节点约束系数, 但该文章并未考虑边的桥接属性。文献[8]提出一种寻找连接不同社区间的桥接边的方法, 用于判断网络中的边是属于社团内部还是属于社团外部, 该算法考虑了网络的局部拓扑信息, 但算法复杂度较高。文献[9]以社团结构为基础, 为弥补以往经典指标不能识别网络桥节点的重要性, 引入了邻居节点规模。文献[10]研究众多真实复杂网络的桥接结构, 证明了真实网络的桥接现象, 从度分布的角度出发, 重新定义了桥系数bridgeness, 给出了计算桥边重要性的深度优先算法。

上述研究多以节点自身属性来评估边的重要性, 研究重点均以边两端节点的度或边介数为出发点, 未考虑边两端节点的邻居节点之间也相互连接对该边信息流转造成衰减的影响。基于此, 本文从桥边的两端节点之间可达的二级和三级路径出发, 提出一种基于桥接系数的指挥控制网络桥边识别方法。

1 桥接系数

复杂网络的结构和功能特征使得某些相似节点汇集在一起, 形成簇或社团, 如科学家合作网、指挥控制网络等^[11]。网络中的边按其不同作用可分为2类:一类边用于提高局部连通性, 比如社团内部的边; 另一类边用于保持全局连通性, 比如社团之间的边, 这类边通常会对网络中的信息流转起着至关重要的作用, 称之为桥边^[12]。桥边对整个网络的连通性和可靠性具有重要的影响。

1.1 网络桥接现象

网络的关键边不仅与边两端节点直接相关, 还与节点的共同邻居节点相关, 如图 1所示。

节点v₄与节点v₆之间存在边e_{4, 6}, 节点v₄的度为5, 节点v₆的度为6, 节点v₄与节点v₆公共邻居节点为节点v₅。度值越高且共同邻居节点的数量越少, 或者度值越高且两端节点的邻居节点之间的连边数越少, 则边的关键度就越高, 所以边e_{4, 6}的关键度较高。为了更加全面地描述边的桥接性, 引入桥接系数来考虑端节点的邻居节点之间也互连的情况。

1.2 桥接系数定义

指挥控制网络按各作战单元的不同功能, 可以分为侦察单元、指挥控制单元、火力打击单元等^[13]。将作战单元描述为节点, 构成各作战单元之间信息传输的链路描述为边, 利用复杂网络理论建立指挥控制网络模型。指挥控制网络可定义为由节点集V=(v₁, v₂, …, v_n)和边集E=(e₁, e₂, …, e_m)构成的网络G=(V, E)。为便于定义桥接系数, 首先给出节点的度和邻接矩阵的定义。

1) 节点的度

节点的度表示为与该节点直接相连的边的个数之和。度值在一定程度上反映了节点的重要性, 即节点的度值越大, 该节点在网络中的影响力也就越大, 邻居节点对其依赖性也就越高, 节点也就越重要。节点的度k_i定义为:

$ {k_i} = \sum\limits_{i \ne j} {{\delta _{ij}}} $

(1)

若节点v_i和节点v_j之间存在连边, 则δ_ij=1;否则δ_ij=0。

假设网络中与边e_ij直接连接的2个节点v_i和v_j的邻居节点v′_i和v′_j的集合分别为M、N, 则节点v_i和v_j的度分别可以表示为k_i=|M|和k_j=|N|。

2) 邻接矩阵

邻接矩阵用于表示网络中各节点之间的直接连接关系, 网络G的邻接矩阵可表示为A={a_ij}_N×N, 各元素表示为:

$ {a_{ij}} = \left\{ {\begin{array}{*{20}{l}} {1, \left( {{v_i}, {v_j}} \right) \in E}\\ {0, \left( {{v_i}, {v_j}} \right) \notin E} \end{array}} \right. $

(2)

关键边在网络中往往起到桥梁作用, 考虑边两端节点的邻居节点之间的相互连接会对该边信息流转造成衰减影响, 边两端节点与其共同邻居节点之间组成三角形结构, 三角形结构越多, 对边信息流转造成的衰减就越强。根据上述假设, 可得桥接系数定义。

桥接系数:节点v′_i和v′_j之间的实际连边数量与节点v_i和v_j的公共邻居节点数量之和占其可能存在的总边数之积的比例为桥接系数, 如式(3)所示。

$ {Q_{ij}} = \frac{{\sum\limits_{m \in M} {\sum\limits_{n \in N} {{a_{mn}}} } + P}}{{(|M| + 1) \times (|N| + 1)}} $

(3)

其中, ${\sum\limits_{m \in M} {\sum\limits_{n \in N} {{a_{mn}}} } }$表示节点v_i的邻居节点与节点v_j的邻居节点直接连边的总个数, P表示以e_ij为边的三角形个数, 也就是节点v_i和节点v_j的共同邻居节点个数。三角形个数越多, 节点v_i和节点v_j之间的联系就越强, 而边e_ij的桥梁特性就越弱, 具体表示如式(4)所示。

$ P = |M \cap N| = \frac{{\sum\limits_{m \in M} {{a_{jm}}} + \sum\limits_{n \in N} {{a_{ni}}} }}{2} $

(4)

其中, ${\sum\limits_{m \in M} {{a_{jm}}} }$表示节点v_i与节点v_j的邻居节点相连的边个数, ${\sum\limits_{n \in N} {{a_{ni}}} }$表示节点v_j与节点v_i的邻居节点相连的边个数。

当与边e_ij直接相连的2个节点v_i和v_j没有共同邻居节点或v_i和v_j的邻居节点之间也互不相连, 会导致e_ij的桥接系数为0, 不符合客观实际。为保证桥接系数与边重要性正相关, 对桥接系数做进一步的处理, 得到边关键度X_ij, 如式(5)所示。

$ \begin{array}{l} {X_{ij}} = - \lg \left( {\frac{{\sum\limits_{m \in M} {\sum\limits_{n \in N} {{a_{mn}}} } + P}}{{(|M| + 1) \times (|N| + 1)}} + } \right.\\ \left. {\;\;\;\;\;\;\;\frac{\alpha }{{(|M| + 1) \times (|N| + 1)}}} \right) = - \lg \frac{{\sum\limits_{m \in M} {\sum\limits_{n \in N} {{a_{mn}}} } + P + \alpha }}{{(|M| + 1) \times (|N| + 1)}} \end{array} $

(5)

其中, α为调节参数。

由式(5)可知, 桥接系数Q_ij越小, 边关键度X_ij就越大, 节点v_i和v_j所组成的边就越关键, 在网络中的影响力也就越大。

对图 1所示简化模型, 计算网络中所有边的边关键度, 结果如表 1所示。

由表 1可以看出, 节点v₃和节点v₁₀之间的连边的边关键度最大, 节点v₄和节点v₆之间的连边次之, 由此可以做出以下判断, 边e_{3, 10}和边e_{4, 6}在网络中起着桥接作用, 即起着枢纽作用, 破坏这些边, 可以使网络结构得到最大破坏。结合图 1也可以直观地进行桥边识别, 其结果与表 1计算所得结论保持一致, 从而验证了桥接系数的正确性。

2 指挥控制网络桥边识别方法

本文提出一种基于桥接系数的指挥控制网络桥边识别方法, 通过加强桥边的保护, 可有效增强指挥控制网络的抗毁性。

在进行边关键度计算之前, 需要对各边进行初始化, 依据边的三角形结构和边的邻居节点之间互连的个数对初始边进行衰减, 通过计算指挥控制网络边信息衰减的多少, 判断边的重要性, 信息衰减越少, 则边越重要。

在进行算法描述之前, 先给出如下规则:

初始化规则:根据节点度值初始化网络节点的信息量为E_i=k_i+1, 如果节点v_x与v_y直接相连, 则流经边e_xy的最大信息量为E_x→y=E_x×E_y, 且E_x→y=E_y→x。

边信息量衰减规则:如果节点v_x与v_y有n个共同邻居节点, 则边信息量衰减n; 如果节点v_x的邻居节点与节点v_y的邻居节点之间有m条连接, 则边信息量衰减m, 两者衰减可叠加。

算法实现步骤如下:

步骤1  建立指挥控制网络模型, 构造网络节点邻接矩阵A=[a_ij]。

步骤2  根据初始化法则, 初始化网络的节点信息量和边信息量。

步骤3  抽取节点v_x与v_y的邻居节点, 分别与节点集N和M组成新的子图, 按行与列从原始邻接矩阵中抽取出新子图对应的邻接矩阵, 统计子图中连边的总个数, 将总边数减1(去除自身)得到边衰减量Δ_x→y。

步骤4  根据边信息量衰减规则, 结合桥系数定义, 进行边信息量衰减, 得到新的边信息量E′_x→y=E_x→y-ΔE_x→y。

步骤5  重复步骤3和步骤4, 直到网络中所有的边都被遍历完为止, 得到边信息衰减矩阵E′。

步骤6  根据边信息衰减矩阵E′对链路重要度进行排序, 得到关键链路。

3 仿真结果与分析

为了验证本文方法的有效性, 以典型防空指挥控制系统为例, 利用Gephi复杂网络分析软件建立防空指挥控制网络模型, 如图 2所示。构建的指挥控制网络模型, 节点数量为N=121, 边数量为256。

针对上述指挥控制网络模型, 利用Matlab仿真软件对度乘积、Jaccard系数、边介数和桥接系数4种方法分别进行仿真, 通过对比分析4种方法识别出的关键边的相似度来评估边的重要性。分别对边进行重要度排序, 结果如表 2所示(仅给出重要度排在前15的边)。

从表 2可以看出, 识别出的最重要的15条边中, 桥接系数方法与边介数方法识别出的桥边相似度达到50%以上(8条), 并且本文所提方法识别出的关键边的73%(11条)均被Jaccard系数和边介数方法识别。在度乘积和Jaccard系数的识别结果中出现了连续编号的重要边, 这是由于这2种方法自身的局限性, 即当某个节点的度值过大时, 与之相连的边的重要性也会随之变大。

本文根据网络中存在的桥接现象, 具体分析了网络的拓扑结构, 借助桥接系数从局部角度提出指挥控制网络桥边识别算法, 其算法复杂度为O(N²), 而边介数为全局测度, 其复杂度为O(N³); 在识别精度上, 桥接系数考虑到了关键边两端节点的邻居节点之间相互连接对边造成的衰减影响, 识别精度均优于其他3种方法。

在桥接系数定义中, 考虑到有些边的端节点的邻居节点之间存在互不连接的情况, 有可能造成桥系数为0, 从而使边失去权值。为此, 引入调节参数α, 避免边权重为0的情况, 同时, 为了不影响边权重, 调节参数α取值不应大于某一阈值。为了验证仿真调节参数α对网络性能的影响, 将α取不同的值进行反复测试, 采用谱距离测度对网络进行仿真验证, 谱距离反映的是网络遭到蓄意攻击之后任意节点间的距离疏远程度, 谱距离越大, 网络性能越差, 其仿真图如图 3所示。

由图 3可以看出, 随着删除边数的不断增加, 网络谱距离不断增大, 当α=0.8或α=1.0时, 网络谱距离变化较大, 说明调节参数过大已经对边重要度造成了影响。因此, 为了不影响边的权重值, 调节参数值不应过大。为了不失一般性, 本文后续仿真中均取α=0.4, 以保证关键边识别的可靠性。

指挥控制网络常遭受2种攻击策略^[14], 分别为随机攻击和蓄意攻击。随机攻击是指以一定概率对指挥控制网络中的节点(或边)进行攻击; 蓄意攻击是指按照节点(或边)重要性大小依次攻击节点。本文采用随机攻击策略和蓄意攻击策略对指挥控制网络边进行攻击, 通过网络平均效率来判断关键链路识别的准确性, 其中蓄意攻击策略选取桥接系数攻击策略, 其仿真图如图 4所示。

由图 4可以看出, 在蓄意攻击下, 网络平均效率下降速度明显比随机攻击下快, 这说明蓄意攻击对网络具有较大影响。

网络连通系数反映了抗毁性能与连通分支数的关系, 可以分析删除关键边后网络被分割情况, 网络连通系数越小, 则网络被分割得越严重, 抗毁性相应越差。网络连通系数定义如下:

$ C = \frac{1}{{\omega \sum\limits_{i = 1}^\omega {\frac{{{N_i}}}{N}} {l_i}}} $

(6)

其中, ω为网络的连通子图个数, N_i为第i个连通子图内部的节点个数, N为网络节点总数, l_i为第i个连通子图内部平均距离:

$ {l_i} = \frac{1}{{{N_i}\left( {{N_i} - 1} \right)}}\sum\limits_{m \ne n} {{d_{mn}}} $

(7)

任意连通子图的平均距离反映了该子图的抗毁程度, 平均距离越大, 抗毁性越差。

图 5为边删除过程中网络连通系数变化。由图 5可以看出, 按照以桥接系数方法识别出的关键链路删除边时, 网络连通系数下降最快, 说明本文方法能够最先找到网络中起到桥梁作用的边, 针对该边进行保护, 可以极大地增加指挥控制网络的抗毁性。

图 6为不同测度下识别出的关键链路受到蓄意攻击后, 网络中最大连通子图边数占指挥控制网络总边数的比值S的变化趋势。

$ S = \frac{{{E_m}}}{E} $

(8)

其中, E_m为最大连通子图的边数目, E为指挥控制网络边数总数。由图 6可以看出, 随着边的删除, 网络中最大连通子图的边数占比均呈下降趋势, 并且本文方法效果要好于其他3种方法, 网络最大连通子图的边数最先下降到初始网络总边数的20%以下, 说明桥接系数测度在关键边识别中具有较高的准确率。

网络平均效率Φ表示网络中任意两节点间距离倒数之和的平均值, Φ反映了网络中信息流的传输能力^[15], 从信息传输路径角度衡量网络的抗毁度, 当网络受到攻击时, 其平均效率效率越高, 网络抗毁性能越好, 可表示为:

$ \mathit{\Phi } = \frac{1}{{N(N - 1)}}\sum\limits_{i \ne j} {\frac{1}{{{d_{ij}}}}} $

(9)

网络平均效率在不同测度下随删边次数的变化结果如图 7所示。随着删边数量的增加, 网络平均效率均呈下降趋势, 在删除同样边数的情况下, 基于桥接系数的删边方法使得网络平均效率下降最快, 说明桥接系数测度相比其他测度在关键边识别方面具有更好的识别精度, 从而验证了桥接系数的优越性。通过对基于桥接系数识别出的关键边进行保护可以更好地提高指挥控制网络的抗毁性。

4 结束语

指挥控制网络的抗毁性研究通常围绕关键节点展开, 往往忽略了边在网络信息流转中的作用。本文提出一种基于桥接系数的指挥控制网络桥边识别方法, 通过计算网络中边两端节点之间可达的二级和三级路径, 比较两者之和与该边两端节点的增广度乘积之比来确定边的关键度, 利用边删除法对识别出的桥边进行按序删除, 通过观察网络连通系数、网络平均效率等参数的变化来进行桥边验证。仿真结果表明, 该方法能够有效识别指挥控制网络的桥边, 并且具有较高的识别精度。