Cost-efficient Algebraic Connectivity Optimisation of Backbone Networks

Abstract

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.

Department(s)

Electrical and Computer Engineering

Sponsor(s)

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)

1573-4277

Electronic OCLC #

740974881

Print OCLC #

61878277

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2014 Elsevier, All rights reserved.

Publication Date

01 Jan 2014

Link to Full Text

Share

 
COinS