Large-scale robustness-oriented efficient edge addition through traversal tree-based weak edge identification

To build robust networks, a popular way is to add edges to existing networks, which can help defend against natural disasters or malicious attacks that randomly or intentionally break several key links at once. There is an urgent need to optimally add edges to improve robustness, e.g., measured by general metrics such as graph connectivity. However, although exhausting and connecting both sides of all small cuts is a sure way to achieve feasible solutions, since the number of possible edges to add is much more than the existing number of edges, even the problem instances in the small graphs are too complex to be solved efficiently, while applying heuristic algorithms to large-scale graphs can only achieve very inefficient results. Fortunately, we find an efficient way to represent all candidate cuts based on the mapping between trees and cuts, and find the near-optimal set of endpoints that cross both sides of all these cuts, and finally find the optimal number of edges reinforcing these cuts to improve edge connectivity. Experiments in representative Erdos–Renyi and scale-free graphs show that the proposed algorithm can achieve perfectly improved results as the optimal algorithm, and the computing speed can be at most 6 orders of magnitude faster than the optimal algorithm, at the expense of slightly increased edge count. The large graph results show the obvious advantage of the proposed algorithms in providing near-perfect results, while popular heuristic algorithms are almost useless in protecting these networks. The proposed algorithm can be further efficient by exploiting its ready-to-parallelize logics for further acceleration.