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

Large-scale robustness-oriented efficient edge addition through traversal tree-based weak edge identification

Author

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

Abstract

To build robust networks, a popular way is to add edges to existing networks, which can help defend against natural disasters or malicious attacks that randomly or intentionally break several key links at once. There is an urgent need to optimally add edges to improve robustness, e.g., measured by general metrics such as graph connectivity. However, although exhausting and connecting both sides of all small cuts is a sure way to achieve feasible solutions, since the number of possible edges to add is much more than the existing number of edges, even the problem instances in the small graphs are too complex to be solved efficiently, while applying heuristic algorithms to large-scale graphs can only achieve very inefficient results. Fortunately, we find an efficient way to represent all candidate cuts based on the mapping between trees and cuts, and find the near-optimal set of endpoints that cross both sides of all these cuts, and finally find the optimal number of edges reinforcing these cuts to improve edge connectivity. Experiments in representative Erdos–Renyi and scale-free graphs show that the proposed algorithm can achieve perfectly improved results as the optimal algorithm, and the computing speed can be at most 6 orders of magnitude faster than the optimal algorithm, at the expense of slightly increased edge count. The large graph results show the obvious advantage of the proposed algorithms in providing near-perfect results, while popular heuristic algorithms are almost useless in protecting these networks. The proposed algorithm can be further efficient by exploiting its ready-to-parallelize logics for further acceleration.

Suggested Citation

  • 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).
  • Handle: RePEc:eee:chsofr:v:179:y:2024:i:c:s0960077924000213
    DOI: 10.1016/j.chaos.2024.114470
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0960077924000213
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.chaos.2024.114470?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. 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. Dong, Shangjia & Gao, Xinyu & Mostafavi, Ali & Gao, Jianxi & Gangwal, Utkarsh, 2023. "Characterizing resilience of flood-disrupted dynamic transportation network through the lens of link reliability and stability," Reliability Engineering and System Safety, Elsevier, vol. 232(C).
    4. 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).
    5. 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.
    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. 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).
    2. 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).
    3. 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).
    4. 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).
    5. 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).
    6. 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).
    7. Liang, Zhenglin & Li, Yan-Fu, 2023. "Holistic Resilience and Reliability Measures for Cellular Telecommunication Networks," Reliability Engineering and System Safety, Elsevier, vol. 237(C).
    8. 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).
    9. Xu, Min & Ouyang, Min & Hong, Liu & Mao, Zijun & Xu, Xiaolin, 2022. "Resilience-driven repair sequencing decision under uncertainty for critical infrastructure systems," Reliability Engineering and System Safety, Elsevier, vol. 221(C).
    10. 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).
    11. Zhang, Wangxin & Han, Qiang & Shang, Wen-Long & Xu, Chengshun, 2024. "Seismic resilience assessment of interdependent urban transportation-electric power system under uncertainty," Transportation Research Part A: Policy and Practice, Elsevier, vol. 183(C).
    12. Cavalieri, Francesco & Franchin, Paolo & Giovinazzi, Sonia, 2023. "Multi-hazard assessment of increased flooding hazard due to earthquake-induced damage to the natural drainage system," Reliability Engineering and System Safety, Elsevier, vol. 237(C).
    13. Yu, Yun-Chi & Gardoni, Paolo, 2022. "Predicting road blockage due to building damage following earthquakes," Reliability Engineering and System Safety, Elsevier, vol. 219(C).
    14. 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).
    15. 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).
    16. Xu, Renjie & Liu, Jiahao & Li, Jichao & Yang, Kewei & Zio, Enrico, 2024. "TSoSRA: A task-oriented resilience assessment framework for system-of-systems," Reliability Engineering and System Safety, Elsevier, vol. 248(C).
    17. Dui, Hongyan & Zhang, Huanqi & Dong, Xinghui & Zhang, Songru, 2024. "Cascading failure and resilience optimization of unmanned vehicle distribution networks in IoT," Reliability Engineering and System Safety, Elsevier, vol. 246(C).
    18. Yin, Rongrong & Zhang, Kai & Ma, Xuyao & Wang, Yumeng & Li, Linhui, 2023. "Analysis of cascading failures caused by mobile overload attacks in scale-free networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 615(C).
    19. Ferrario, E. & Poulos, A. & Castro, S. & de la Llera, J.C. & Lorca, A., 2022. "Predictive capacity of topological measures in evaluating seismic risk and resilience of electric power networks," Reliability Engineering and System Safety, Elsevier, vol. 217(C).
    20. 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).

    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:chsofr:v:179:y:2024:i:c:s0960077924000213. 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: Thayer, Thomas R. (email available below). General contact details of provider: https://www.journals.elsevier.com/chaos-solitons-and-fractals .

    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.