A memetic algorithm for determining the nodal attacks with minimum cost on complex networks

• Published in: Physica A 2018-08, Vol.503, p.1041-1053
• Main Authors: Yang, Zhirou, Liu, Jing
• Format: Article
• Language: English
• Subjects: Attack cost; Complex network; Network robustness; Nodal attack; Scale-free network
• ISSN: 0378-4371; 1873-2119
• DOI: 10.1016/j.physa.2018.08.132

Many real-world networks are exposed in complicated environments and may be destroyed easily by various kinds of attacks and errors. With no doubt it is of great significance to promote the anti-attack ability of systems. Besides, analyzing attack models is also of significance. The existing studies about network robustness conducted on weighted or unweighted networks have drawn the conclusion that scale-free networks are fragile under malicious attacks, where the precondition is that the cost of removing a node is equal. In fact, the cost of attacking different nodes is far from equal, thus, the removal cost should be taken into consideration when conducting attacks. In this paper, a malicious attack model considering the cost of attacking nodes, termed as Nodal Attack with Cost (NAC), is first proposed to depict the tolerance of networks. Furthermore, the limitation of resources drives us to design an optimization algorithm based on memetic algorithm (MA), termed as MA-NAC, to search for the optimal combination of nodes with the minimum cost which can destroy networks to the desired degree. The experimental results show that networks perform robust under the high degree adaptive (HDA) attack when there is a great difference between hub nodes and leaf nodes in the attack cost, yet the results are similar to previous studies on the condition that the attack cost gap is minor. In addition, MA-NAC is efficient in finding a relatively small attack cost. Based on the study of cost-optimized network structure and features of attacked nodes obtained by MA-NAC, we find that MA-NAC selects the target nodes by taking into account their effect on network structure, which contributes to the good optimization ability of MA-NAC. •Practical attacks make networks fragmented rather than make each node isolated.•An attack model considering the cost of attacking nodes is designed accordingly.•A memetic algorithm MA-NAC is proposed to find the relatively low attack cost.•The good performance of MA-NAC is validated on various networks.