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

A novel algorithm for the generalized network dismantling problem based on dynamic programming

Author

Listed:
  • Feng, Zhidan
  • Song, Huimin
  • Qi, Xingqin

Abstract

For an undirected network G=(V,E) with removal cost on each node, the generalized network dismantling problem is to find a node subset S⊆V with the minimum overall removal cost, such that the size of each connected component in G−S is not larger than a given integer K. This issue has wide applications at network destruction (e.g., combating crime network) or network defense (e.g., strengthening the infrastructure), and has gained growing attentions from various research fields. In graph theory, cut nodes play important roles in ensuring network connectivity, which could of course be regarded as potential removal candidates for this network dismantling problem. This paper is primarily dedicated to this point. Here, having the aid of an auxiliary block-cut tree, we transform the network dismantling problem into a relatively simple problem −− tree dismantling problem, and then design a bottom-up dynamic programming algorithm (abbreviated as DPA) to dismantle this auxiliary tree by removing cut nodes with minimum overall removal costs. This DPA dismantling strategy has been tested on both synthetic networks and real-world networks, and numerical experiments demonstrate the superiority of this method. Our results shed light on more explorations of network structure from the cut-node perspectives.

Suggested Citation

  • Feng, Zhidan & Song, Huimin & Qi, Xingqin, 2024. "A novel algorithm for the generalized network dismantling problem based on dynamic programming," Chaos, Solitons & Fractals, Elsevier, vol. 180(C).
    • Handle: RePEc:eee:chsofr:v:180:y:2024:i:c:s096007792400136x
    DOI: 10.1016/j.chaos.2024.114585
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S096007792400136X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.chaos.2024.114585?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. Duncan J. Watts & Steven H. Strogatz, 1998. "Collective dynamics of ‘small-world’ networks," Nature, Nature, vol. 393(6684), pages 440-442, June.
    2. Hai-Jun Zhou, 2013. "Spin glass approach to the feedback vertex set problem," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 86(11), pages 1-9, November.
    3. Flaviano Morone & Hernán A. Makse, 2015. "Correction: Corrigendum: Influence maximization in complex networks through optimal percolation," Nature, Nature, vol. 527(7579), pages 544-544, November.
    4. G. Paul & T. Tanizawa & S. Havlin & H. Stanley, 2004. "Optimization of robustness of complex networks," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 38(2), pages 187-191, March.
    5. Réka Albert & Hawoong Jeong & Albert-László Barabási, 2000. "Error and attack tolerance of complex networks," Nature, Nature, vol. 406(6794), pages 378-382, July.
    6. Flaviano Morone & Hernán A. Makse, 2015. "Influence maximization in complex networks through optimal percolation," Nature, Nature, vol. 524(7563), pages 65-68, August.
    7. Ash, J. & Newth, D., 2007. "Optimizing complex networks for resilience against cascading failure," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 380(C), pages 673-683.
    8. Xiao-Long Ren & Niels Gleinig & Dijana Tolić & Nino Antulov-Fantulin, 2018. "Underestimated Cost of Targeted Attacks on Complex Networks," Complexity, Hindawi, vol. 2018, pages 1-15, January.
    9. Liang Tian & Amir Bashan & Da-Ning Shi & Yang-Yu Liu, 2017. "Articulation points in complex networks," Nature Communications, Nature, vol. 8(1), pages 1-9, April.
    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. Wandelt, Sebastian & Lin, Wei & Sun, Xiaoqian & Zanin, Massimiliano, 2022. "From random failures to targeted attacks in network dismantling," Reliability Engineering and System Safety, Elsevier, vol. 218(PA).
    2. Li Zeng & Changjun Fan & Chao Chen, 2023. "Leveraging Minimum Nodes for Optimum Key Player Identification in Complex Networks: A Deep Reinforcement Learning Strategy with Structured Reward Shaping," Mathematics, MDPI, vol. 11(17), pages 1-13, August.
    3. Alexandru Topîrceanu, 2022. "Benchmarking Cost-Effective Opinion Injection Strategies in Complex Networks," Mathematics, MDPI, vol. 10(12), pages 1-16, June.
    4. Ping Pei & Haihan Zhang & Huizhen Zhang & Chen Yang & Tianbo An, 2024. "Network Synchronization via Pinning Control from an Attacker-Defender Game Perspective," Mathematics, MDPI, vol. 12(12), pages 1-17, June.
    5. Xiao-Long Ren & Niels Gleinig & Dijana Tolić & Nino Antulov-Fantulin, 2018. "Underestimated Cost of Targeted Attacks on Complex Networks," Complexity, Hindawi, vol. 2018, pages 1-15, January.
    6. Gangwal, Utkarsh & Singh, Mayank & Pandey, Pradumn Kumar & Kamboj, Deepak & Chatterjee, Samrat & Bhatia, Udit, 2022. "Identifying early-warning indicators of onset of sudden collapse in networked infrastructure systems against sequential disruptions," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 591(C).
    7. Li, Sheng & Liu, Wenwen & Wu, Ruizi & Li, Junli, 2023. "An adaptive attack model to network controllability," Reliability Engineering and System Safety, Elsevier, vol. 235(C).
    8. Zhang, Dayong & Men, Hao & Zhang, Zhaoxin, 2024. "Assessing the stability of collaboration networks: A structural cohesion analysis perspective," Journal of Informetrics, Elsevier, vol. 18(1).
    9. Sun, Peng Gang & Che, Wanping & Quan, Yining & Wang, Shuzhen & Miao, Qiguang, 2022. "Random networks are heterogeneous exhibiting a multi-scaling law," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 587(C).
    10. Xinyu Huang & Dongming Chen & Dongqi Wang & Tao Ren, 2020. "MINE: Identifying Top- k Vital Nodes in Complex Networks via Maximum Influential Neighbors Expansion," Mathematics, MDPI, vol. 8(9), pages 1-25, August.
    11. Shriram Ashok Kumar & Maliha Tasnim & Zohvin Singh Basnyat & Faezeh Karimi & Kaveh Khalilpour, 2022. "Resilience Analysis of Australian Electricity and Gas Transmission Networks," Sustainability, MDPI, vol. 14(6), pages 1-20, March.
    12. Vitor H. P. Louzada & Fabio Daolio & Hans J. Herrmann & Marco Tomassini, "undated". "Smart rewiring for network robustness," Working Papers ETH-RC-14-004, ETH Zurich, Chair of Systems Design.
    13. Jiang, Wenjun & Fan, Tianlong & Li, Changhao & Zhang, Chuanfu & Zhang, Tao & Luo, Zong-fu, 2024. "Comprehensive analysis of network robustness evaluation based on convolutional neural networks with spatial pyramid pooling," Chaos, Solitons & Fractals, Elsevier, vol. 184(C).
    14. Yu, Yang & Deng, Ye & Tan, Suo-Yi & Wu, Jun, 2018. "Efficient disintegration strategy in directed networks based on tabu search," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 507(C), pages 435-442.
    15. Han, Jihui & Zhang, Ge & Dong, Gaogao & Zhao, Longfeng & Shi, Yuefeng & Zou, Yijiang, 2024. "Exact analysis of generalized degree-based percolation without memory," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 642(C).
    16. Yibo Dong & Jin Liu & Jiaqi Ren & Zhe Li & Weili Li, 2023. "Protecting Infrastructure Networks: Solving the Stackelberg Game with Interval-Valued Intuitionistic Fuzzy Number Payoffs," Mathematics, MDPI, vol. 11(24), pages 1-18, December.
    17. Kovalenko, K. & Romance, M. & Vasilyeva, E. & Aleja, D. & Criado, R. & Musatov, D. & Raigorodskii, A.M. & Flores, J. & Samoylenko, I. & Alfaro-Bittner, K. & Perc, M. & Boccaletti, S., 2022. "Vector centrality in hypergraphs," Chaos, Solitons & Fractals, Elsevier, vol. 162(C).
    18. Fink, Christian G. & Fullin, Kelly & Gutierrez, Guillermo & Omodt, Nathan & Zinnecker, Sydney & Sprint, Gina & McCulloch, Sean, 2023. "A centrality measure for quantifying spread on weighted, directed networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 626(C).
    19. Zhu, Qian & Zhu, Zhiliang & Wang, Yifan & Yu, Hai, 2016. "Fuzzy-information-based robustness of interconnected networks against attacks and failures," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 458(C), pages 194-203.
    20. 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).

    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:180:y:2024:i:c:s096007792400136x. 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.