Optimizing Spectral Energy of Graphs by an Evolutionary Edge Rewiring

Abstract

Robustness is considered as one of the important and vital features in today’s complex networks and advanced infrastructures and has become a popular and growing research field in the recent years. This research field seeks to find solutions and mechanisms to improve the connectivity of networks against random failures and systematic attacks. Until now, various different measures have been suggested for measurement and assessment of robustness and resilience of complex networks. An important part of these measures is dedicated to the algebraic graph theory and the study and examination of the spectrum of the graph’s adjacency matrix (graph spectrum). The energy of any simple graph is the sum of the absolute values of its eigenvalues. In this paper, it is first shown that the energy of any network has a strong correlation with its robustness, then; a rewiring mechanism for optimization of a graph’s energy measure is presented. Using an evolutionary algorithm (genetic), we try to find that rewiring which set of edges causes the most energy increase compared to the original graph. By answering this question, we can decide about finding an optimal solution to optimize the energy and connectivity of complex networks in different areas of complex and social networks, and; as a result, increase their robustness and resilience. The numerical results derived from simulations provide us with knowledge of the location and number of edges that should be rewired to gain a maximal increase in energy, and; as a result, a maximal increase in robustness.