Cost-efficient algebraic connectivity optimisation of backbone networks

Backbone networks are prone to failures due to targeted attacks or large-scale disasters. Network resilience can be improved by adding new links to increase network connectivity and robustness. However, random link additions without an optimisation objective function can have insignificant connectivity improvement. In this paper, we develop a heuristic algorithm that optimises a network by adding links to achieve a higher network resilience by maximising algebraic connectivity and decreasing total cost via selecting cost-efficient links. We apply our algorithm to five different backbone topologies and measure algebraic connectivity improvement and the cost incurred while adding new links. For evaluation, we apply three centrality node attacks to the non- and optimised networks and show the network flow robustness while nodes are removed. Our results show that optimised graphs with higher algebraic connectivity values are mostly more resilient to centrality-based node attacks.