IDEAS home Printed from https://ideas.repec.org/a/eee/reensy/v232y2023ics0951832022006974.html
   My bibliography  Save this article

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

Author

Listed:
  • Wei, Wei
  • Liu, Yuting
  • Yang, Weidong

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.

Suggested Citation

  • Wei, Wei & Liu, Yuting & Yang, Weidong, 2023. "PTUM: Efficient shielding of large-scale network through pruned tree-cut mapping," Reliability Engineering and System Safety, Elsevier, vol. 232(C).
    • Handle: RePEc:eee:reensy:v:232:y:2023:i:c:s0951832022006974
    DOI: 10.1016/j.ress.2022.109082
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0951832022006974
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ress.2022.109082?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Wang, Shuliang & Lv, Wenzhuo & Zhang, Jianhua & Luan, Shengyang & Chen, Chen & Gu, Xifeng, 2021. "Method of power network critical nodes identification and robustness enhancement based on a cooperative framework," Reliability Engineering and System Safety, Elsevier, vol. 207(C).
    2. Fan, Dongming & Lin, Jing & Cai, Baoping & Liu, Bin, 2021. "Robustness of maintenance support service networks: attributes, evaluation and improvement," Reliability Engineering and System Safety, Elsevier, vol. 210(C).
    3. Wang, Shuliang & Gu, Xifeng & Chen, Jiawei & Chen, Chen & Huang, Xiaodi, 2023. "Robustness improvement strategy of cyber-physical systems with weak interdependency," Reliability Engineering and System Safety, Elsevier, vol. 229(C).
    4. Wandelt, Sebastian & Shi, Xing & Sun, Xiaoqian, 2021. "Estimation and improvement of transportation network robustness by exploiting communities," Reliability Engineering and System Safety, Elsevier, vol. 206(C).
    5. Lv, Changchun & Yuan, Ziwei & Si, Shubin & Duan, Dongli, 2021. "Robustness of scale-free networks with dynamical behavior against multi-node perturbation," Chaos, Solitons & Fractals, Elsevier, vol. 152(C).
    6. Liu, Hao & Chen, Xin & Huo, Long & Zhang, Yadong & Niu, Chunming, 2022. "Impact of inter-network assortativity on robustness against cascading failures in cyber–physical power systems," Reliability Engineering and System Safety, Elsevier, vol. 217(C).
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Wei, Wei & Hu, Qiuyuan & Zhang, Qinghui, 2024. "Improving node connectivity by optimized dual tree-based effective node consolidation," Reliability Engineering and System Safety, Elsevier, vol. 242(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Hao, Yucheng & Jia, Limin & Zio, Enrico & Wang, Yanhui & He, Zhichao, 2024. "A network-based approach to improving robustness of a high-speed train by structure adjustment," Reliability Engineering and System Safety, Elsevier, vol. 243(C).
    2. Xu, Mengqiao & Deng, Wenhui & Zhu, Yifan & LÜ, Linyuan, 2023. "Assessing and improving the structural robustness of global liner shipping system: A motif-based network science approach," Reliability Engineering and System Safety, Elsevier, vol. 240(C).
    3. Dong, Zhengcheng & Tian, Meng & Li, Xin & Lai, Jingang & Tang, Ruoli, 2022. "Mitigating cascading failures of spatially embedded cyber–physical power systems by adding additional information links," Reliability Engineering and System Safety, Elsevier, vol. 225(C).
    4. Ding, Xiao & Wang, Huan & Zhang, Xi & Ma, Chuang & Zhang, Hai-Feng, 2024. "Dual nature of cyber–physical power systems and the mitigation strategies," Reliability Engineering and System Safety, Elsevier, vol. 244(C).
    5. Hao, Yucheng & Jia, Limin & Zio, Enrico & Wang, Yanhui & He, Zhichao, 2023. "A multi-objective optimization model for identifying groups of critical elements in a high-speed train," Reliability Engineering and System Safety, Elsevier, vol. 235(C).
    6. Kurmankhojayev, Daniyar & Li, Guoyuan & Chen, Anthony, 2024. "Link criticality index: Refinement, framework extension, and a case study," Reliability Engineering and System Safety, Elsevier, vol. 243(C).
    7. Li, Siping & Zhou, Yaoming & Kundu, Tanmoy & Sheu, Jiuh-Biing, 2021. "Spatiotemporal variation of the worldwide air transportation network induced by COVID-19 pandemic in 2020," Transport Policy, Elsevier, vol. 111(C), pages 168-184.
    8. Wandelt, Sebastian & Sun, Xiaoqian & Zhang, Anming, 2023. "Towards analyzing the robustness of the Integrated Global Transportation Network Abstraction (IGTNA)," Transportation Research Part A: Policy and Practice, Elsevier, vol. 178(C).
    9. Lu, Qing-Chang & Zhang, Lei & Xu, Peng-Cheng & Cui, Xin & Li, Jing, 2022. "Modeling network vulnerability of urban rail transit under cascading failures: A Coupled Map Lattices approach," Reliability Engineering and System Safety, Elsevier, vol. 221(C).
    10. Chen, Gaolin & Zhou, Shuming & Li, Min & Zhang, Hong, 2022. "Evaluation of community vulnerability based on communicability and structural dissimilarity," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 606(C).
    11. Feng, Xiao & He, Shiwei & Li, Guangye & Chi, Jushang, 2021. "Transfer network of high-speed rail and aviation: Structure and critical components," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 581(C).
    12. Yu, Yun-Chi & Gardoni, Paolo, 2022. "Predicting road blockage due to building damage following earthquakes," Reliability Engineering and System Safety, Elsevier, vol. 219(C).
    13. Wang, Ziqi & Pei, Yulong & Zhang, Jianhua & Dong, Chuntong & Liu, Jing & Zhou, Dongyue, 2024. "Vulnerability analysis of public transit systems from the perspective of the traffic situation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 634(C).
    14. Zhang, Mingyuan & Yang, Xiangjie & Zhang, Juan & Li, Gang, 2022. "Post-earthquake resilience optimization of a rural “road-bridge†transportation network system," Reliability Engineering and System Safety, Elsevier, vol. 225(C).
    15. Shen, Jingwei & Zong, Huiming, 2023. "Identification of critical transportation cities in the multimodal transportation network of China," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 628(C).
    16. Wentao Wu & Shihai Wang & Bin Liu, 2024. "Software Fault Localization Based on Weighted Association Rule Mining and Complex Networks," Mathematics, MDPI, vol. 12(13), pages 1-21, July.
    17. Zizhen Xu & Shauhrat S. Chopra, 2023. "Interconnectedness enhances network resilience of multimodal public transportation systems for Safe-to-Fail urban mobility," Nature Communications, Nature, vol. 14(1), pages 1-11, December.
    18. Wandelt, Sebastian & Sun, Xiaoqian & Zhang, Anming, 2023. "AI-driven assistants for education and research? A case study on ChatGPT for air transport management," Journal of Air Transport Management, Elsevier, vol. 113(C).
    19. Li, Xianxiong & Lan, Xinbo & Mirzaei, A & Aghdam Bonab, Mohammad Jalilvand, 2022. "Reliability and robust resource allocation for Cache-enabled HetNets: QoS-aware mobile edge computing," Reliability Engineering and System Safety, Elsevier, vol. 220(C).
    20. Xiaoqian Sun & Sebastian Wandelt, 2021. "Robustness of Air Transportation as Complex Networks:Systematic Review of 15 Years of Research and Outlook into the Future," Sustainability, MDPI, vol. 13(11), pages 1-19, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:reensy:v:232:y:2023:i:c:s0951832022006974. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: https://www.journals.elsevier.com/reliability-engineering-and-system-safety .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.