NP-hard

In this letters, a new measure called communication robustness (CR) for network robustness is presented from the standpoint of network structure, which not only confirms the dominant effect of the giant connected component on the network robustness, but captures the local communicability of all small connected components. Furthermore, we prove that the optimal edge-adding problem to improve the CR is NP-hard. To cope with the NP-hard problem, we propose a simulated annealing algorithm in terms of the proposed CR measure.