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

Wei Wei, Yuting Liu and Weidong Yang

Reliability Engineering and System Safety, 2023, vol. 232, issue C

Abstract: 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.

Keywords: Network robustness; Pruned tree-cut mapping; Shielding; Large-scale network; Connectivity (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0951832022006974
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:reensy:v:232:y:2023:i:c:s0951832022006974

DOI: 10.1016/j.ress.2022.109082

Access Statistics for this article

Reliability Engineering and System Safety is currently edited by Carlos Guedes Soares

More articles in Reliability Engineering and System Safety from Elsevier
Bibliographic data for series maintained by Catherine Liu ().