基于有限节点集的网络毁伤最大化问题研究
CSTR:
作者:
作者单位:

(1. 空军预警学院预警情报系,武汉430019;2. 国防科技大学信息通信学院,武汉430010)

作者简介:

通讯作者:

E-mail: fengzeng_liu@126.com.

中图分类号:

TP393

基金项目:

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


Network damage maximization based on finite node set
Author:
Affiliation:

(1. Department of Early-Warning Intelligence, Air Force Early-Warning Academy,Wuhan430019,China;2. College of Information and Communication,National University of Defense Technology,Wuhan430010,China)

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    When attacking the network, people hope to get the maximum damage effect under the limited resources, and the node sorting strategy cannot achieve the maximum damage. In view of this situation, the network damage maximization problem of attacking a finite node set is defined, and an approximate algorithm for solving the problem is given. Due to the high computational complexity of the approximate algorithm, a greedy algorithm based on important nodes(GABIN) is proposed. Experiments on scale-free networks show that the GABIN algorithm can effectively reduce computing time, and its effect is close to the approximate algorithm. When the degree exponent of scale-free networks is greater than or equal to 2.5, the GABIN algorithm is better than sorting algorithms, and more than 30% of the nodes in the node set are different from sorting algorithms. The damage experiments on the Power grid show that the GABIN algorithm is suitable for large-scale real networks, and its effect is significantly better than sorting algorithms such as degree, betweenness, closeness and deleting nodes. The experiment shows that the key node set obtained by using the GABIN algorithm contains a large number of non-central nodes, which provides a new idea for network attack or network protection.

    参考文献
    相似文献
    引证文献
引用本文

刘凤增,肖兵,金宏斌,等.基于有限节点集的网络毁伤最大化问题研究[J].控制与决策,2020,35(4):937-942

复制
相关视频

分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2020-03-03
  • 出版日期:
文章二维码