Optimal Cost-Based Strengthening of Complex Networks

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.