基于有限节点集的网络毁伤最大化问题研究

作者：刘凤增^*; 肖兵; 金宏斌; 李浩

来源：控制与决策, 2020, 35(04): 937-942.

DOI：10.13195/j.kzyjc.2018.0966

• 毁伤最大化
• 有限节点集
• 节点重要性
• 贪婪算法
• 复杂网络
• 计算复杂度

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

• 单位
  中国人民解放军空军预警学院; 国防科技大学