《表1 0“911”恐怖袭击数据集（|V|=63, |E|=154）上的实验比较》

  提示：宽带有限、当前游客访问压缩模式

本系列图表出处文件名：随高清版一同展现

《复杂网络关键节点组识别问题模型和算法研究》

1. 获取 高清版本忘记账户？点击这里登录

1. 下载图表忘记账户？点击这里登录

为了验证模型的鲁棒性，本文选取了多种连接结构的网络图进行实验，包括Erdos-Renyi图[37]、Geometric图[38]、Sticky图[39]、Range因果图[40]和Kleinberg图[41]，并且每种类型网络都随机选取了不同的规模。虽然可以比较K≤|V|/2的结果，直至DF=1为止。但由于空间所限，此处仅针对Erdos-Renyi（|V|=14，|E|=36）列出全部结果，如表1所示。其余实验数据集仅列出K≤5的结果，如表2～表5所示。其中，K为所识别关键节点的个数，Obj为移除关键节点后的模型目标函数值，T为运算执行时间，度量时间为毫秒（ms) ，DF指标用来评价识别结果的好坏，上标“*”表示性能比较中占优的一方。以Erdos-Renyi图为例，从表1中可以看出，尽管本文利用松弛方法只求得QCQP问题的近似解，但在大部分情况下，求解的效果都好于传统的整数线性规划模型。例如，表1中第3行表示了一个具有14个节点和36条边的E-R随机网络，当关键节点个数为1时，ILP模型及其启发式算法得到的目标函数值均为79，相应的DF值是0.419 4和0.413 9；而本文提出的SDPR模型及QCQP启发式算法得到的目标函数值均为386，相应的DF值均为0.435 9。这说明SDPR模型和QCQP启发式所识别的关键节点，被移除后造成的网络离散程度更大，在识别效果上更为有效。当然，也存在ILP模型和启发式胜出的少数情形，这是由于本文所提出的近似求解方法只求得SDPR模型的近似解，在某些情况下会略逊于ILP模型求得的最优解。但从表1～表5的整体实验效果来看，SDPR模型和QCQP启发式算法在大部分实验情况下均取得了较好实验效果。