Empirical Evaluation of Network Optimization Via Graph Spectra and Energy
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.
R. E. Snyder et al., "Empirical Evaluation of Network Optimization Via Graph Spectra and Energy," Proceedings of the 9th International Workshop on Resilient Networks Design and Modeling (2017, Alghero, Italy), Institute of Electrical and Electronics Engineers (IEEE), Sep 2017.
The definitive version is available at https://doi.org/10.1109/RNDM.2017.8093020
9th International Workshop on Resilient Networks Design and Modeling, RNDM 2017 (2017, Sep. 4-6, Alghero, Italy)
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)
Article - Conference proceedings
© 2017 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.