IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v12y2024i8p1215-d1377902.html
   My bibliography  Save this article

Deep Reinforcement Learning for Network Dismantling: A K-Core Based Approach

Author

Listed:
  • Tianle Pu

    (College of Systems Engineering, National University of Defense Technology, Changsha 410073, China)

  • Li Zeng

    (College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
    School of International Business and Management, Sichuan International Studies University, Chongqing 400031, China)

  • Chao Chen

    (College of Systems Engineering, National University of Defense Technology, Changsha 410073, China)

Abstract

Network dismantling is one of the most challenging problems in complex systems. This problem encompasses a broad array of practical applications. Previous works mainly focus on the metrics such as the number of nodes in the Giant Connected Component (GCC), average pairwise connectivity, etc. This paper introduces a novel metric, the accumulated 2-core size, for assessing network dismantling. Due to the NP-hard computational complexity of this problem, we propose SmartCore, an end-to-end model for minimizing the accumulated 2-core size by leveraging reinforcement learning and graph neural networks. Extensive experiments across synthetic and real-world datasets demonstrate SmartCore’s superiority over existing methods in terms of both accuracy and speed, suggesting that SmartCore should be a better choice for the network dismantling problem in practice.

Suggested Citation

  • Tianle Pu & Li Zeng & Chao Chen, 2024. "Deep Reinforcement Learning for Network Dismantling: A K-Core Based Approach," Mathematics, MDPI, vol. 12(8), pages 1-12, April.
    • Handle: RePEc:gam:jmathe:v:12:y:2024:i:8:p:1215-:d:1377902
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/12/8/1215/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/12/8/1215/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Deng, Ye & Wu, Jun & Tan, Yue-jin, 2016. "Optimal attack strategy of complex networks based on tabu search," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 442(C), pages 74-81.
    2. Li, Hanwen & Shang, Qiuyan & Deng, Yong, 2021. "A generalized gravity model for influential spreaders identification in complex networks," Chaos, Solitons & Fractals, Elsevier, vol. 143(C).
    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. 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.
    5. Volodymyr Mnih & Koray Kavukcuoglu & David Silver & Andrei A. Rusu & Joel Veness & Marc G. Bellemare & Alex Graves & Martin Riedmiller & Andreas K. Fidjeland & Georg Ostrovski & Stig Petersen & Charle, 2015. "Human-level control through deep reinforcement learning," Nature, Nature, vol. 518(7540), pages 529-533, February.
    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.
    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. 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.
    2. 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.
    3. 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).
    4. Fan, Dongming & Sun, Bo & Dui, Hongyan & Zhong, Jilong & Wang, Ziyao & Ren, Yi & Wang, Zili, 2022. "A modified connectivity link addition strategy to improve the resilience of multiplex networks against attacks," Reliability Engineering and System Safety, Elsevier, vol. 221(C).
    5. Wang, Jingjing & Xu, Shuqi & Mariani, Manuel S. & Lü, Linyuan, 2021. "The local structure of citation networks uncovers expert-selected milestone papers," Journal of Informetrics, Elsevier, vol. 15(4).
    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. Yin, Haofei & Zhang, Aobo & Zeng, An, 2023. "Identifying hidden target nodes for spreading in complex networks," Chaos, Solitons & Fractals, Elsevier, vol. 168(C).
    8. Qi, Mingze & Tan, Suoyi & Chen, Peng & Duan, Xiaojun & Lu, Xin, 2023. "Efficient network intervention with sampling information," Chaos, Solitons & Fractals, Elsevier, vol. 166(C).
    9. 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).
    10. James Flamino & Alessandro Galeazzi & Stuart Feldman & Michael W. Macy & Brendan Cross & Zhenkun Zhou & Matteo Serafino & Alexandre Bovet & Hernán A. Makse & Boleslaw K. Szymanski, 2023. "Political polarization of news media and influencers on Twitter in the 2016 and 2020 US presidential elections," Nature Human Behaviour, Nature, vol. 7(6), pages 904-916, June.
    11. Almeira, Nahuel & Perotti, Juan Ignacio & Chacoma, Andrés & Billoni, Orlando Vito, 2021. "Explosive dismantling of two-dimensional random lattices under betweenness centrality attacks," Chaos, Solitons & Fractals, Elsevier, vol. 153(P1).
    12. Wu, Rui-Jie & Kong, Yi-Xiu & Di, Zengru & Zhang, Yi-Cheng & Shi, Gui-Yuan, 2022. "Analytical solution to the k-core pruning process," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 608(P1).
    13. 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).
    14. 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).
    15. Sun, Peng Gang & Wu, Xunlian & Quan, Yining & Miao, Qiguang, 2022. "Influence percolation method for overlapping community detection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 596(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. Ye, Yucheng & Xu, Shuqi & Mariani, Manuel Sebastian & Lü, Linyuan, 2022. "Forecasting countries' gross domestic product from patent data," Chaos, Solitons & Fractals, Elsevier, vol. 160(C).
    18. Zhang, Jiarui & Tang, Bin & Duan, Yuxian & Huang, Jian, 2023. "Percolation phase transition in the heterogeneous multi-coupled interdependent network," Chaos, Solitons & Fractals, Elsevier, vol. 174(C).
    19. Quan M. Tran & Hien D. Nguyen & Tai Huynh & Kha V. Nguyen & Suong N. Hoang & Vuong T. Pham, 2022. "Measuring the influence and amplification of users on social network with unsupervised behaviors learning and efficient interaction-based knowledge graph," Journal of Combinatorial Optimization, Springer, vol. 44(4), pages 2919-2945, November.
    20. Massimiliano Turchetto & Michele Bellingeri & Roberto Alfieri & Ngoc-Kim-Khanh Nguyen & Quang Nguyen & Davide Cassi, 2023. "Random Walks-Based Node Centralities to Attack Complex Networks," Mathematics, MDPI, vol. 11(23), pages 1-20, November.

    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:gam:jmathe:v:12:y:2024:i:8:p:1215-:d:1377902. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    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.