第五节 算例与讨论

本书提出的相对连通系数作为一种全新的网络节点重要性指标，需要与已有的成熟指标性能进行对比。对于相同的算例，此指标得出的评价结果应该与已有的成熟指标相吻合，并且具备已有指标所不具备的特点，能够解决以前解决不了的问题，只有这样才能说明提出此指标的合理性和必要性。为此，本节将相对连通系数与常用的一些网络节点重要性指标进行算例对比。

图3-5为节点重要性文献中经常引用的一个经典案例，呈现了40个艾滋病患者的性关系网络，Poulin、Boily、Madsse、Stephenson、Zelen、Freeman、Bonacich、李鹏翔、席酉民等都用该网络进行过核心性指标的计算和比较工作。

在此需要说明，虽然相对连通系数在本书中主要应用于道路网络节点重要性的评价，但从前文其建立的过程中可以看出，此指标是在已有的成熟网络节点重要性指标基础之上改进得到的，其适用范围并不只局限于道路网络；而图3-5所呈现的经典案例中，蕴含了进行网络节点重要性评价时可能遇到的各种情况，较之一般道路网络数据，更能测试出网络节点重要性指标在极限情况下的性能。因此，为对比相对连通系数与其他常用指标的性能特点和适用范围，本节以此网络为例来计算其相对连通系数，并与其他常用指标进行对照。

一 求单目标节点的相对连通系数

1．首先将图3-5中网络以所选目标节点为根、按宽度优先搜索的顺序展开成一棵树，下面以17号节点为例展开（如图3-6所示）。

值得注意的是图中形成圈的地方会有共同的子树，例如28号节点和34号节点的情形，这时只需在第一次遇到时展开一次，然后在以后的节点中保存指向该子树根节点的指针即可。

2．递归估算网络节点相对所选目标节点的单点相对连通系数，在相对连通性系数近似定义中，表征节点对应子树形状的特征向量的计算具有递归嵌套的特点，由此可用子树中下一级节点已有的特征向量来计算上一级节点对应的特征向量。以17号节点为例的求解过程如表3-1所示。

二 求多目标节点的相对连通系数

1．利用前述方法求得网络中所有节点相对任一节点的相对连通系数，具体情况如表3-2所示。

2．选取目标节点集，构造目标节点集相对连通系数矩阵。例如这里选取节点17、26、33作为目标节点集，然后从上一步求得的单点相对连通系数中选取这三个节点对应的 RCC 形成矩阵，具体情况如表3-6所示。

3．调用Matlab对上面矩阵做主成分分析，得到图3-5所示网络中节点17、26、33相对连通系数矩阵主成分对应的奇异值和主成分向量，具体情况如表3-7、表3-8所示。

4．利用公式（3.20）求得针对节点17、26、33的多目标节点相对连通系数，如表3-9所示。

由于现有指标都是针对整个网络的，为与已有指标作一对比，这里利用上述方法求得节点相对整个网络的多目标节点相对连通系数（即RCC［1…40］），从这里也可以看出：针对整个网络的相对连通系数只是针对节点集的相对连通系数在节点集为网络中所有节点时的一个特例，将其与Poulin、Boily和Madsse等就此网络的计算结果对照列于表3-10中。

表3-10中，Rank表示根据节点指标数值排出的名次；CDeg、CCS、Cinf和CBon分别表示核心性的度指标、接近度指标、信息核心性指标和Bonacich的特征向量指标，CCN和CCN′是Poulin等提出的累计提名指标。CR是李鹏翔、席酉民等在文献提出的CR指标，RCC为本书提出的基于节点删除的重要性指标。节点编号和对应每个指标的计算结果列在表中。

从指标的分布模式来看，相对连通系数与度指标的相关性较强，但与度指标相比，它既考虑网络的局部连接特性也考虑与之相关联的网络整体特性，这又与李鹏翔、席酉民等提出的CR指标相似，这三种指标的模式分布情况如图3-7所示。

不同的指标是从不同的角度来探讨同一问题的，每个指标都有自己的优缺点和适用范围。接近度指标反映节点的居中程度，中介性指标反映节点对其他节点间沟通的控制能力，特征向量指标和累计提名指标反映的是节点的名望和地位特性，而相对连通系数指标则反映的是节点对保持整个网络的连通所起的作用。因此，当目标节点集是整个网络时，相对连通系数与前述指标相比并无明显优势，但当目标节点集动态变化时，相对连通系数就显示出其他指标所不具备的优越性，其能够根据所选目标节点集按需提取与之最相关的部分子网。例如，选取节点17、26、33作为目标节点集，利用前面计算所得的结果，滤掉RCC值为0的冗余节点，可得到与目标节点集密切相关的部分（如图3-8所示）。

这其中包含了与节点17、26、33相关的大部分路径，还有一些重要的关节点，这些都是有可能在路径搜索中用到的。

进一步将滤取阈值提高到10，得到与目标节点集更相关的部分（如图3-9所示）。

这时随着阈值的提高，周边的关节点和一些不重要的路径如20-19-28-26也被滤掉，保留的都是与目标节点集最相关的路径和节点。

在这里虽然网络规模较小，偶然因素造成的误差干扰较大，但结果已十分精确。这是因为在求相对连通系数的时候，不同的子树形状之间的差异是以指数的级别进行放大的，因此能够有效地把冗余节点、非关键节点、关键节点按梯级分开。如果应用在大规模的网络上，放大效果更加明显，筛选结果就更加精确。

从上面的算例讨论可以看出，利用相对连通系数指标可以根据所选目标节点集有效地提取网络中与目标节点集最相关的部分，获取与之相关的路径解空间信息。

这一点对于应急物流配送车辆导航尤其重要。在应急物流配送车辆导航路径搜索时，使用者并不需要了解节点对于整个网络的重要性，其关心的只是与出救任务行车目标密切相关的那一部分路网，其他的冗余部分只会分散驾驶员的注意力，消耗车载设备上有限的计算资源，因此需要根据所选目标节点集按需生成应急物流配送导航地图。但已有的节点重要性指标并未说明其重要性是针对哪些目标节点的，其重要性往往被默认是相对于整个网络来说的，如果要求相对于特定节点（集）的重要性指标，就得对指标做复杂的分解，再合成。这时相对连通系数就显示出其独有的优势：前述相对连通系数的求解过程，本身就是从单目标点过渡到多目标节点集的，因此我们可以很自然地根据选定的目标节点集提取相对于应急物流配送行车目标重要的部分。这就克服了已有指标的不足，对现有网络节点重要性理论是一种补充和完善。