Exploiting global information in complex network repair processes

Robustness of complex networks has been studied for decades, with a particular focus on network attack. Research on network repair, on the other hand, has been conducted only very lately, given the even higher complexity and absence of an effective evaluation metric. A recently proposed network repair strategy is self-healing, which aims to repair networks for larger components at a low cost only with local information. In this paper, we discuss the effectiveness and efficiency of self-healing, which limits network repair to be a multi-objective optimization problem and makes it difficult to measure its optimality. This leads us to a new network repair evaluation metric. Since the time complexity of the computation is very high, we devise a greedy ranking strategy. Evaluations on both real-world and random networks show the effectiveness of our new metric and repair strategy. Our study contributes to optimal network repair algorithms and provides a gold standard for future studies on network repair.