Cost-Efficient network improvement to achieve maximum path diversity

Communication networks are prone to failures due to targeted attacks or large-scale disasters. Networks can be improved to withstand challenges using mechanisms such as diversity, which can simply be improved by adding links, however achieving maximum resilience is not feasible due to limited budget. Therefore, algorithms that improve the diversity of networks cost-efficiently are necessary. In this paper, we present a heuristic algorithm that adds links to improve the diversity of the graph while minimizing the cost of link addition. We analyze the flow robustness of non- and improved graphs against targeted attacks. Our results indicate that path-diversity-improved graphs are more resilient to attacks than graphs improved by adding links to the lowest degree nodes.