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.
M. J. Alenazi et al., "Cost-efficient Algebraic Connectivity Optimisation of Backbone Networks," Optical Switching and Networking, no. Part 2, pp. 107 - 116, Elsevier, Jan 2014.
The definitive version is available at https://doi.org/10.1016/j.osn.2014.05.003
Electrical and Computer Engineering
National Science Foundation (U.S.)
Keywords and Phrases
Heuristic Algorithms; Robustness (Control Systems); Algebraic Connectivity; Back-Bone Network; Connectivity; Dependability; Network Optimisation; Resilience; Algebra
International Standard Serial Number (ISSN)
Electronic OCLC #
Print OCLC #
Article - Journal
© 2014 Elsevier, All rights reserved.
01 Jan 2014