第二节 基于节点删除的连通性度量指标——相对连通系数

为了寻找合适的连通性度量指标，以提取出对应急物流配送路径分析最重要的元素，需要对路径搜索的过程进行分析，以了解网络中的元素在搜索中所起的作用。

路径搜索的过程可看作由许多节点间的转移组成的，因此只需考察其中某一个单步转移的过程即可。为方便分析，这里所说的单步转移不是指只通过一条边的节点间跳转，而是更广泛的通过网络中某条路径的跳转，此路径可能由多条边组成。

在导航程序进行单步跳转时，由于搜索应用程序事先并没有关于路径优劣的先验知识，因此只能认为下一步转移的路径选择是随机的，与当前节点相连的任何一条路径都有相同的概率被选中进入结果路径。

现在面临的问题是如何最小化网络中元素的减少对搜索过程的影响。很明显应该尽量保留搜索时可能会选中的路径，从而使网络分解前后搜索程序所面对的路径选择变化最小。但哪些路径是搜索时会用到的呢？路径分析必然有目标节点，有时是一个目标节点集，将搜索的起点也看作目标节点集的一员，所有以这些目标节点为终点的路径都是搜索时必然会涉及的；另外，假设有一条路径在搜索时被选中，那么由它出发的搜索步骤必然也会到达某一目标节点。将这两步搜索合并，形成的路径仍是一条以某目标节点为终点的路径，即上述搜索过程等价于选择经由一条以目标节点为终点的路径的单步跳转。综合以上两方面可知，以目标节点为终点的路径集合蕴涵了搜索时所有可能的选择，即为所求搜索时会用到的路径集合。

进一步来看，与目标元素相关的连通关系到任一元素上的投影可用经由元素以目标节点（集）为终点的路径组成的集合来量化，其基数大小即表征了网络中任一元素对目标节点（集）在路径分析求解方面影响的大小。

由此可见，经由某一元素以目标节点（集）为终点的路径条数，直接表征了该元素在路径搜索时对路径选择的影响，描述了其对目标节点（集）在路径分析方面的重要性，能够恰当地量化元素之间的连通关系，是一个符合需要的合适的指标。

直接求经由某一元素以目标节点（集）为终点的路径条数比较困难，关键在于“经由某一元素”这一条件验证起来比较复杂，需要耗费大量的计算时间。因此，本书引入节点删除的方法，通过统计指定节点删除前后网络中以目标节点（集）为终点的路径数的差异来求得该节点对目标节点（集）连通路径数的影响。这也符合突发事件中道路网络节点常常因次生衍生灾害损毁无法通行、应急物流配送路网道路节点常常动态变化这一实际情况。

为简单起见，先考虑单目标节点的情况：假设元素a为所关心的目标点，考虑元素i对其连通性的影响。设从图中任何一个元素出发，可引Rj条路径到达a点，N0为图中所有元素到元素a连通路径的集合，那么图中所有元素到元素a连通路径的总条数为：

现在从图中删去元素i，设N1为此时图中所有元素到元素a连通路径的集合，再求图中所有元素到元素a连通路径的总条数为：

设Ni为从图中删去元素i后图中所有元素到元素a减少的连通路径的集合，综合前两个算式可以得到由于从图中删去元素i造成的到达a点的连通路径的减少数为：

由于｜Ni｜通常是一个很大的数，为了方便应用，只需取其数量级即可，由此可引入以下元素i对元素a连通性影响的度量指标的定义，称之为相对连通系数（Relative Connectivity Coefficient）：