《表5 Kleinberg (|V|=16, |E|=47) 网络实验结果》
为了验证模型的鲁棒性,本文选取了多种连接结构的网络图进行实验,包括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启发式算法在大部分实验情况下均取得了较好实验效果。
图表编号 | XD0069559400 严禁用于非法目的 |
---|---|
绘制时间 | 2019.08.01 |
作者 | 江成、张军、卢山 |
绘制单位 | 首都经济贸易大学信息学院、首都经济贸易大学信息学院、首都经济贸易大学信息学院 |
更多格式 | 高清、无水印(增值服务) |