Minimizing security cost in large-scale networks under regional failures via tree-based cut computation

Regional failures caused by extreme weather or malicious attacks pose serious risks to the stability of communication networks. To address this issue, we propose an optimization algorithm based on edge protection that enhances network robustness by improving edge connectivity without altering network topology. The algorithm iteratively constructs spanning trees to precisely compute cut values and identify vulnerable edges with minimal protection costs. Experiments are conducted on Erdos–Renyi and scale-free networks. In small-scale graphs, the algorithm achieves target edge connectivity for nearly all node pairs, while being up to five orders of magnitude faster than optimal methods. In large-scale scenarios, the algorithm maintains high robustness with a run time under 200 s, which can be further reduced to under 10 s through parallelization. The results demonstrate the proposed method’s efficiency, scalability, and practical applicability for improving robustness in large-scale networks under regional failures.