PTUM: Efficient shielding of large-scale network through pruned tree-cut mapping

As one realistic way to improve the robustness of network, the protection of critical links will help build resilient link structure to defend against random link failure, especially in sparse network where few simultaneous broken links can divide it into disconnected parts. There are several ways to select the set of links to shield, where selecting links by graph cuts is a practical one. However, due to the computational complexity of cut enumeration, the existing algorithms cannot handle large-scale networks in acceptable time. Fortunately, between the pruned trees and cuts, we found an efficient mapping schema to enumerate small cuts, which can help select the candidate links quickly in large-scale sparse network, and the link set will be further refined to find the set with minimal shielding cost. The experimental results show that compared with the existing optimal algorithm, the acceleration ratio of 5 orders of magnitude can be obtained easily with little excess cost, and the shielding solution can protect more than 99.9% vulnerable node pairs. Furthermore, the time can be reduced to tens of seconds by parallelization for the ready-to-parallelize algorithm.