An Evolutionary-based Link Addition Approach for Improving Robustness of Complex Networks

A link addition method to enhance the robustness of a network, based on Genetic Algorithms, is proposed. The approach optimizes the effective graph resistance of a network, a measure of robustness derived from the field of electric circuit analysis, that can be computed as a cumulative sum of the eigenvalues of the Laplacian matrix associated with the network. Specialized variation operators allow the method to find a solution almost always coinciding with that obtained by an exhaustive search. Experiments on synthetic and real life networks show that the approach outperforms heuristic strategies extensively investigated, by giving the exact solution in a high percentage of the considered networks.