基于改进融合算法的交通网络节点重要性评估

孙兴龙，李亚雄，邱艳粉

（火箭军工程大学作战保障学院，西安 710025）

0 引言

对于网络化目标体系，目标的价值主要体现在个体目标固有价值和作为网络节点的目标体系价值。固有价值与目标节点周围的资源配置有关，且固有价值与目标网络体系价值的评价方法不同。本文只对目标的网络体系价值作出研究。

交通体系网络模型包括公路网、铁路网、航空网组成，是典型的多层复杂网络模型。目前，对于评估多层交通网络节点重要性，很少有考虑边的权重，事实上每条路径的运载能力区别很大，权重不可忽略。对于多层复杂网络的研究分为两个方面。一是分析网络的统计特性，包括聚类系数、特征向量、度中心性、介数中心性；二是对复杂网络进行建模［1-2］，寻找网络关键节点以及失去关键节点产生的连锁反应或者网络损失［3］。

由于对多层复杂网络的研究刚刚兴起，因此，对于多层复杂网络评估方法较少，目前比较成熟的是随机游走介数评估和邻接中心性评估［4-5］。但是这两种方法在评估的过程中忽略了节点对网络全局的影响，很难准确反映不同节点之间的连接价值，导致最终评估结果的偏差，而且对于节点数和层数较多的网络，难以反映节点间的细小差距，节点评估准确性难以保证。此外，还有人提出余弦相似度的评估方法［6］，然而这种方法忽略了复杂网络中不同节点之间的权重信息，导致评估模型与实际网络符合度相距甚远。

2）构建距离矩阵。在拆解过程中，逐一计算每个单层网络的距离矩阵。

3）构建关联矩阵。根据两两节点之间的关联关系和路径权重系数按照一定算法得到关联矩阵。

4）构建基本概率分配矩阵。根据计算规则得到任意两个节点的基本概率分配函数（Basic Probability Assignment Functions 简称BPA）。

5）融合各层基本概率分配函数。将各层BPA矩阵利用D-S 证据理论（不确定性证据理论）进行数据融合。

6）BPA 概率转换。运用赌博概率转换算法（Pignistic Probability Ttansformation，简称PPT 算法）最终得到节点重要度指标。

该算法框架如图1 所示。

1 基于融合算法的网络节点评估方法

1.1 模型建立的步骤

针对以上问题，本文提出一种考虑权重和网络整体影响融合算法对加权多层交通网络节点重要性进行评估，该方法步骤如下：

1）将多层网络拆解为多个单层网络。根据多层复杂网络结构组成关系将其拆解为多个单层网络。

图1 融合算法流程图

交通网络包含公路网、铁路网、航空网，是一类典型的各层节点相同，每层节点的连接关系不同的多层网络，是NON 网络（Network of Networks）的一种。

图2 交通网络拆解过程

图2 中所示的即为多层交通网络的示意图。图（a）所示的局部交通网络拆解结构图，不同网络层的相同节点互相连接，图（b）是整个多层网络示意图，图（c）、图（d）、图（e）是拆解后的单层复杂网络。

1.2 构建距离矩阵

对于一个具有n 个节点的多层网络，可得一个多层网络拆解后的每个单层网络的距离矩阵D 具体如下：

其中，dij表示节点i 与节点j 的最短路径长度。对于现实交通网络，其网络结构十分复杂，一般不存在不相连的两个节点。

1.3 构建关联度矩阵

关联度矩阵的构建是节点评估准确性的关键。本文提出了一种基于关联度矩阵的基本概率分配构建方法。网络中节点间的关联度矩阵S 定义如下：

定义节点i 与节点j 的直接关联度sij为节点i与节点j 之间的最短路径dij在整个网络的价值。而网络中节点i 与节点j 之间的关联度sij不仅与两个节点之间的最短路径dij相关，还与网络中其他节点相关。例如，当dij的某一部分是节点m 和n 的最短路径dmn的子集，失去节点i 与节点j 之间最短路径dij后，会对网络中节点m 和n 的最短路径产生影响，可能会导致最短路径变大或者不存在连通路径。

此外，关联度还与节点之间的信息传递能力有关，对于公路网络信息传递能力就是运载能力。例如，高速公路和普通路的运载能力是不同的，路宽车道也是不同的，这些因素对于连通价值影响很大。

根据复杂网络邻接矩阵的定义，在一个具有n个节点的加权网络中，邻接矩阵权重wij为：

对于不同的交通网络其网络中节点之间的运送效率有着显著的区别，在多层交通网络中任意两节点i 与j 之间运输效率由每层节点i 与j 之间边共同决定，运输效率主要由时间成本、经济成本、运载能力等因素构成。考虑到这些因素在交通网络中定义邻接连通矩阵权重为：

其中，运载能力定义为pij是根据邻接节点的交通情况而定，相关数据可根据交通网站查询得到。pmax为单层网络中运载能力的最大值。特别地，当节点i 与j 在网络中不相连时，wij为0。

节点i 与节点j 在最短路径上的关联度sij为：

其中，N 是最短路径数量。

以上分析是基于分解后的单层网络，对于实际多层网络，不同层级之间的交叉影响也不可忽略，这也是目前对多层网络分析被忽略的敌方。本文考虑了不同单层网络之间的交叉影响，更符合实际网络特点。

在单层网络不连通的节点可以通过多层网络转换线路得到连通路径或者缩短路径距离。因此，在图2 网络（b）中，任意两个节点之间有至少一条路径连通，则合并成一条通路，如（f）所示，然后只把合并后的网络中两个节点路径距离比任意单层网络（c）（d）（e）中距离都近的路径保留，得到网络（g）。例如，对于图2 中，在任意一个单层网络中节点1和8 的最短路径都不小于3，但在多层网络中可以在（c）中经节点2 在通过（d）到达节点8，其距离比单层网络小得多，尤其对于路径很长的网络，多层网络之间的转换有利于提高运输效率。但是对于不同交通方式的转换同样会消耗时间和成本，路径距离越长这种转换的影响会越低。本文假设转换一次运输效率减少为合并路径效率的一半。

1.4 基本概率分配的构建

在融合算法计算的过程中，基本概率分配矩阵的构建十分关键。目前主要有基于模糊集合［7-8］的方法，基于K-NN 分类器［9］的方法，基于神经网络的方法等。针对交通系统多层网络评估的模型，本文运用了一种基于关联度矩阵的基本概率分配构建方法［10］，构建方法定义如下：

对于一个n×n 的关联度矩阵S，n 是网络中节点的数量，该研究背景下命题的辨识框架为：

在该命题上的辨识框架的幂集为：

其中，Y 代表两节点相关，N 代表两节点无关，Y，N代表着不确定相关性。

其中，Sij代表节点i 与j 的关联度，min（S）是最小值。

由此得到整个网络的基本概率分配矩阵MBPA：

其中，

其中，

1.5 基于BPA 矩阵的数据融合

其中，

2）将tij与cij用同样方法融合，结果为lij：

将3 个矩阵中的所有元素按照上述方法融合得到最终BPA 矩阵MNON如下：

其中，

1.6 概率转换算法

为了对多层交通网络体系进行准备评估，需要将最终的BPA 矩阵MNON转换为关联度矩阵。这里运用上述PPT 算法，该算法计算过程如下：

转化后的关联度矩阵RNON为：

其中，rij的转换如下：

最终计算每个节点与其他各节点的关联度Si：

2 实例分析

下面通过对局部多层交通网络模型图2 中的节点评估过程进行实例分析。

根据D-S 证据理论的组合规则，得到融合后的基本概率分配矩阵，利用PPT 算法，将融合后所得到的BPA 矩阵进行概率转换，最终得到多层交通网络的关联度矩阵RNON：

最后计算关联度矩阵RNON每一行的元素之和，即为该节点在多层交通网络的关联度Ic：

图4 是4 种不同方法得到的该交通网络节点重要度的柱状图，可以看出度中心性算法、临近中心性算法、随机游走介数算法得出的节点重要度区间范围很小，而改进的融合算法相对区间范围较大。

表1 4 种方法重要度评估结果

表2 4 种方法评估节点重要度排序

图4 4 种方法节点评估重要度

从图4 中4 种算法所得节点重要度的柱状图可以看出，临近中心算法和度中心性算法的结果极差较小，对节点重要性评估结果不敏感，误差较大。通过图4 对比可以看出，随机游走介数算法与改进的融合算法结果各节点总体相对重要程度相似，但如表2 所示，随机游走算法同样极差区间过小，对节点的相对重要性体现不明显，随着网络节点的增加，随机游走介数算法评估准确性也会不断降低，而本文改进的融合算法能够体现节点之间的差别，区分精度更高。

对比其他算法，本文的融合算法将节点8 和3的价值评价较高，而节点6 和7 的价值较低，与其他算法区别较大。为了验证本文算法的有效性，引入网络效率的概念。

在实际网络中，信息以网络的边为载体进行节点之间的信息交换。对于交通网络，信息代表着运输的货物，传输的效率主要与节点之间距离和运载能力有关，满足关系可以表示如下：

其中，eij是节点i 和j 之间的传输效率，取值范围是［0，1］，dij是节点i 和j 的距离，pij是两点之间运载能力，k 是常数系数。根据此式可以定义网络的全局效率是网络中所有节点之间传输效率的平均值：

多层网络的全局效率可理解为网络中所有节点货物运输效率的平均值，如果移除网络中的某个节点会导致全局网络效率的变化，而且节点的重要度越高，对网络全局效率的影响越大，因此，可以通过逐个移除网络中某个节点，计算网络全局效率的变化来验证算法的有效性，具体结果如表3 所示。

表3 节点对网络效率的影响排序

如表3 所示，Ec、Ed、Ee、Eg分别是单层网络（c）（d）（e）（g）的效率，Eb是多层网路（b）的效率。节点对网络全局影响度排序与表2 中不同方法节点重要度排序结果相比可以发现，影响度排序结果与本文的基于信息融合算法节点重要度非常相似，其中节点4、5、3、2、6、7 的顺序与本文价值排序的方法一致，而与其他算法差别比较明显。通过网络全局效率的计算再次说明本文算法的有效性。

3 结论

本文考虑了多层交通网络的路径权重和节点之间的连接关系对多层网络整体影响，并运用数据融合算法对多层交通网络的关联矩阵进行融合，最终得到多层网络节点关联度，通过对局部多层交通网络实例的建模计算，并与已有的其他3 种方法进行对比。结果显示，本文所建立的多层交通网络模型符合实际，并且运用改进的融合算法，能够有效对多层交通网络目标体系的节点网络价值进行准确评估，对于下一步目标选择具有一定借鉴意义。