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

Employing the cluster of node cut sets to improve the robustness of the network measured by connectivity

Author

Listed:
  • Wei, Wei
  • Sun, Guobin
  • Li, Peng
  • Zhang, Qinghui

Abstract

Protection of critical nodes or edges can help defend networks from failures caused by natural disasters or intended attacks. Node protection becomes the only way when edge protection is not possible, where node connectivity is usually used to measure network robustness due to its effectiveness. Although simple, node connectivity-oriented node consolidation optimization is still NP-hard, especially when dealing with large numbers of nodes. To address the problem, by leveraging the mapping between nodes and traversal trees, per-node cluster of node cut sets is used to identify nominee nodes, which are then conditionally consolidated through a extended dual tree-based selection process. Experimental results show that in small graphs with tens of nodes where the optimal algorithm is applicable, an acceleration ratio of more than 105 (at most 106) is observed at the expense of about 6% extra cost. In large graphs with millions of nodes, the proposed algorithm can help promote node connectivity of more than 99.9% of node pairs, which is far better than commonly used heuristics. Its inherent ready-for-paralleling capability paves the way for more speedups.

Suggested Citation

  • Wei, Wei & Sun, Guobin & Li, Peng & Zhang, Qinghui, 2025. "Employing the cluster of node cut sets to improve the robustness of the network measured by connectivity," Reliability Engineering and System Safety, Elsevier, vol. 254(PA).
    • Handle: RePEc:eee:reensy:v:254:y:2025:i:pa:s0951832024006835
    DOI: 10.1016/j.ress.2024.110612
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0951832024006835
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ress.2024.110612?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. 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).
    2. He, Zhidong & Navneet, Kumar & van Dam, Wirdmer & Van Mieghem, Piet, 2021. "Robustness assessment of multimodal freight transport networks," Reliability Engineering and System Safety, Elsevier, vol. 207(C).
    3. Diao, Xiaoxu & Zhao, Yunfei & Smidts, Carol & Vaddi, Pavan Kumar & Li, Ruixuan & Lei, Hangtian & Chakhchoukh, Yacine & Johnson, Brian & Blanc, Katya Le, 2024. "Dynamic probabilistic risk assessment for electric grid cybersecurity," Reliability Engineering and System Safety, Elsevier, vol. 241(C).
    4. Wandelt, Sebastian & Xu, Yifan & Sun, Xiaoqian, 2023. "Measuring node importance in air transportation systems: On the quality of complex network estimations," Reliability Engineering and System Safety, Elsevier, vol. 240(C).
    5. Cui, Pengshuai & Zhu, Peidong & Wang, Ke & Xun, Peng & Xia, Zhuoqun, 2018. "Enhancing robustness of interdependent network by adding connectivity and dependence links," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 497(C), pages 185-197.
    6. Ouyang, Min & Liu, Chuang & Xu, Min, 2019. "Value of resilience-based solutions on critical infrastructure protection: Comparing with robustness-based solutions," Reliability Engineering and System Safety, Elsevier, vol. 190(C), pages 1-1.
    7. Wei, Wei & Wang, Pengpeng & Zhang, Qinghui, 2023. "Optimal pruned tree-cut mapping-based fast shielding for large-scale networks," Chaos, Solitons & Fractals, Elsevier, vol. 170(C).
    8. Feng, Jian Rui & Zhao, Mengke & Yu, Guanghui & Zhang, Jiaqing & Lu, Shouxiang, 2023. "Dynamic risk analysis of accidents chain and system protection strategy based on complex network and node structure importance," Reliability Engineering and System Safety, Elsevier, vol. 238(C).
    9. 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).
    10. 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).
    11. 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).
    Full references (including those not matched with items on IDEAS)

    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. 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).
    2. Wei, Wei & Sun, Guobin & Zhang, Qinghui, 2024. "Large-scale robustness-oriented efficient edge addition through traversal tree-based weak edge identification," Chaos, Solitons & Fractals, Elsevier, vol. 179(C).
    3. Jiang, Wenjun & Li, Peiyan & Fan, Tianlong & Li, Ting & Zhang, Chuan-fu & Zhang, Tao & Luo, Zong-fu, 2024. "Scalable rapid framework for evaluating network worst robustness with machine learning," Reliability Engineering and System Safety, Elsevier, vol. 252(C).
    4. Zhang, Hai-Feng & Wang, Hao-Ren & Xiang, Bing-Bing & Wang, Huan, 2024. "Robustness study of hybrid hypergraphs," Reliability Engineering and System Safety, Elsevier, vol. 252(C).
    5. 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).
    6. Li, Jian & Yang, Zhao & He, Hongxia & Guo, Changzhen & Chen, Yubo & Zhang, Yong, 2024. "Risk causation analysis and prevention strategy of working fluid systems based on accident data and complex network theory," Reliability Engineering and System Safety, Elsevier, vol. 252(C).
    7. Hongli Zhou & Mingxuan Yang, 2023. "Towards Evaluating the Robustness of the Open-Source Product Community under Multiple Attack Strategies," Sustainability, MDPI, vol. 15(17), pages 1-19, August.
    8. Deng, Ye & Wang, Zhigang & Xiao, Yu & Shen, Xiaoda & Kurths, Jürgen & Wu, Jun, 2025. "Spatial network disintegration based on spatial coverage," Reliability Engineering and System Safety, Elsevier, vol. 253(C).
    9. 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).
    10. Huo, Xiaosen & Yin, Yuan & Jiao, Liudan & Zhang, Yu, 2024. "A data-driven and knowledge graph-based analysis of the risk hazard coupling mechanism in subway construction accidents," Reliability Engineering and System Safety, Elsevier, vol. 250(C).
    11. Wang, Ning & Gao, Ying & He, Jia-tao & Yang, Jun, 2022. "Robustness evaluation of the air cargo network considering node importance and attack cost," Reliability Engineering and System Safety, Elsevier, vol. 217(C).
    12. Song, Zhiting & Zhu, Jianhua & Chen, Kun, 2025. "Robustness analysis of smart manufacturing systems against resource failures: A two-layered network perspective," Reliability Engineering and System Safety, Elsevier, vol. 253(C).
    13. Wang, Ziqi & Pei, Yulong & Liu, Jing & Liu, Hehang, 2023. "Vulnerability analysis of urban road networks based on traffic situation," International Journal of Critical Infrastructure Protection, Elsevier, vol. 41(C).
    14. Liu, Qi & Sun, Ke & Liu, Wenqi & Li, Yufeng & Zheng, Xiangyu & Cao, Chenhong & Li, Jiangtao & Qin, Wutao, 2025. "Quantitative risk assessment for connected automated Vehicles: Integrating improved STPA-SafeSec and Bayesian network," Reliability Engineering and System Safety, Elsevier, vol. 253(C).
    15. Yang, Guizhen & Qi, Xiaogang & Liu, Lifang, 2020. "Research on network robustness based on different deliberate attack methods," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 545(C).
    16. 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).
    17. Zhang, Xi & Wang, Qin & Bi, Xiaowen & Li, Donghong & Liu, Dong & Yu, Yuanjin & Tse, Chi Kong, 2024. "Mitigating cascading failure in power grids with deep reinforcement learning-based remedial actions," Reliability Engineering and System Safety, Elsevier, vol. 250(C).
    18. Alexander Shiroky & Andrey Kalashnikov, 2021. "Mathematical Problems of Managing the Risks of Complex Systems under Targeted Attacks with Known Structures," Mathematics, MDPI, vol. 9(19), pages 1-11, October.
    19. Wang, Jie & Zhang, Yangyi & Li, Shunlong & Xu, Wencheng & Jin, Yao, 2024. "Directed network-based connectivity probability evaluation for urban bridges," Reliability Engineering and System Safety, Elsevier, vol. 241(C).
    20. Marc-Antoine Faure & Bárbara Polo Martin & Fabio Cremaschini & César Ducruet, 2024. "Shipping Trade and Geopolitical Turmoils: The Case of the Ukrainian Maritime Network," EconomiX Working Papers 2024-24, University of Paris Nanterre, EconomiX.

    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:254:y:2025:i:pa:s0951832024006835. 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.