Optimal Cost-Based Strengthening of Complex Networks

Qingnan Rong, Jun Zhang, Xiaoqian Sun*, Sebastian Wandelt, Massimiliano Zanin, Liang Tian

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review


Most real-world complex systems are extremely vulnerable to targeted attacks, making their immunization an important yet challenging task. One of the most effective attack strategies is targeting articulation points specifically. In this study, we first propose a generalized definition of network robustness. Then we address the problem of strengthening network robustness with the minimum cost by exploiting the intuition behind the attack strategy based on articulation points, that is proven to be NP-hard. Accordingly, we propose a heuristic for solving this problem, subject to a cost function whose choice determines the obtained network regime. Experiments on both random and real-world networks show that our algorithm strengthens the robustness by using significantly cheaper edge additions than state-of-the-art methods. Moreover, our algorithm excels against general attack strategies by revealing the essence of strengthening network robustness, that is, increasing the size of the giant connected component optimally in the process of node removal. While considering the realistic problem, our algorithm also provides a reasonable scheme to add edges at a low cost.

Original languageEnglish
Pages (from-to)1117-1127
Number of pages11
JournalIEEE Transactions on Network Science and Engineering
Issue number3
Early online date6 Dec 2021
Publication statusPublished - May 2022

Scopus Subject Areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Computer Networks and Communications

User-Defined Keywords

  • cost
  • heuristic
  • Network robustness
  • strengthening problem
  • targeted attacks


Dive into the research topics of 'Optimal Cost-Based Strengthening of Complex Networks'. Together they form a unique fingerprint.

Cite this