控制与决策

作者：刘凤增,肖兵,金宏斌,李浩

单位：空军预警学院预警情报系，武汉430019;国防科技大学信息通信学院，武汉430010,,空军预警学院预警情报系，武汉430019,,空军预警学院预警情报系，武汉430019,,空军预警学院预警情报系，武汉430019,

关键词：毁伤最大化;有限节点集;节点重要性;贪婪算法;复杂网络;计算复杂度

基金：国家自然科学基金项目(61502522).

对网络实施攻击时,人们希望在有限的资源下获得最大的毁伤效果,而节点排序策略并不能实现毁伤最大.针对这种情况,定义攻击有限节点集的网络毁伤最大化问题,并给出问题的近似求解算法.由于近似求解算法计算复杂度较高,进一步提出基于重要节点的贪婪算法(greedy algorithm based on important nodes,GABIN).对无标度网络的实验表明:GABIN算法能够有效地减少计算时间,且效果接近于近似求解算法;当无标度网络的度指数$\gamma\geqslant2.5$时,GABIN算法的效果明显优于排序算法,所得节点集中超过30%的节点不同于排序算法.对Power网络的毁伤实验表明,GABIN算法适用于较大规模的实际网络,且效果显著优于度、介数、接近度、删除节点等排序算法.实验发现,利用GABIN算法获得的关键节点集包含大量的非中心性节点,这为网络攻击或网络防护提供了一个新的思路.

来源：2020年第4期

《控制与决策》期刊编辑部

查看控制与决策杂志2020年第4期