Cost-effectiveness Analysis of Structural Robustness in Complex Networks

As the robustness of network is mainly determined by the number of redundant paths in the network, many networks perform well in some robustness metrics just because of their large network sizes. It is well-known that edge addition can remarkably enhance the robustness of complex networks. However, more edges lead to more costs. Thus, it is an interesting and significant problem to obtain a cost-efficient network for robustness. In our recent work, the natural connectivity has been proposed as a spectral measure of robustness in complex networks as it has an intuitive physical meaning and a simple mathematical formulation, which has proved reliably in measuring structure robustness. In this paper, we propose to measure the cost-effectiveness ratio of network robustness using the concept of relative natural connectivity, which is defined as the ratio of the natural connectivity of a network to the natural connectivity of the referential Erdos-Renyi random graph with the same network size and edge density. Extensive numerical simulations confirm our method.