Empirical Evaluation of Network Optimization Via Graph Spectra and Energy

Abstract

Attacks upon communication networks have become stealthier and more sophisticated, and hardening communication networks has become necessary to avoid service disruptions. While connectivity of networks can be improved by adding links, there are different strategies for such methods. We implement two link removal algorithms that remove links based on highest link-betweenness and nodal degree. We also implement two link addition algorithms that add links based on a heuristic to connect the lowest degree nodes and add links between the shortest Euclidian distance nodes. Our objective in this paper is to empirically evaluate how well the addition algorithms perform using the graph spectra and energy measurements. We analyze the graph spectra and energy of physical-level networks after link removals and additions. Our results indicate that graph spectra is not a granular measurement to evaluate optimizations. Among the adjacency, Laplacian, and normalized Laplacian graph energy levels we measure, adjacency energy is observed to be very useful in the empirical evaluation of optimization algorithms.

Meeting Name

9th International Workshop on Resilient Networks Design and Modeling, RNDM 2017 (2017, Sep. 4-6, Alghero, Italy)

Department(s)

Electrical and Computer Engineering

Keywords and Phrases

Graph theory; Heuristic algorithms; Laplace transforms; Adjacency; Attack; Back-bone network; Betweenness; Degree; Empirical evaluations; Graph energy; Graph spectra; Laplacians; Normalized Laplacian; Optimization; Backbone network

International Standard Book Number (ISBN)

978-1-5386-0671-1

Document Type

Article - Conference proceedings

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2017 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.

Publication Date

01 Sep 2017

Link to Full Text

Share

 
COinS