Optimal pruned tree-cut mapping-based fast shielding for large-scale networks

Wei Wei, Pengpeng Wang and Qinghui Zhang

Chaos, Solitons & Fractals, 2023, vol. 170, issue C

Abstract: Random failure is a common threat to a network, where the failure of a few edges can disconnect a large-scale sparse network. To enhance the robustness of network, the shielding of important edges is a practical strategy, where the cut is a useful entity to help locate important edges in existing shielding methods. However, as there is no available way to quickly locate target cuts, the existing shielding algorithm is not efficient enough and can only be applied to small-scale backbone networks. Fortunately, by using the optimal pruned tree-cut mapping, we found an efficient and high-precision cut edge enumeration method, which can help quickly locate target cuts and their edges in a large-scale network, leading to a cost-effective shielding plan. Theoretical analysis indicates that more than 99% of candidate cuts can be found with a limited number of preprocessing passes, and experimental results in typical networks show that in small-scale networks, with little extra cost (< 6%), the serial implementation of the algorithm in an off-shelf computing node can be 6 orders of magnitude faster than the optimal method, while in large-scale sparse networks with a million nodes, it can also help defend at least 99.9% of random failures with only tens of seconds of preprocessing overhead.

Keywords: Tree-cut mapping; Network robustness; Left-most path; 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 (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0960077923003016
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:chsofr:v:170:y:2023:i:c:s0960077923003016

DOI: 10.1016/j.chaos.2023.113400

Access Statistics for this article

Chaos, Solitons & Fractals is currently edited by Stefano Boccaletti and Stelios Bekiros

More articles in Chaos, Solitons & Fractals from Elsevier
Bibliographic data for series maintained by Thayer, Thomas R. ().