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

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

Network damage maximization based on finite node set

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.