Reinforcement Learning-Based Network Dismantling by Targeting Maximum-Degree Nodes in the Giant Connected Component

Shixuan Liu (), Tianle Pu, Li Zeng, Yunfei Wang, Haoxiang Cheng and Zhong Liu
Additional contact information
Shixuan Liu: Laboratory for Big Data and Decision, College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
Tianle Pu: Laboratory for Big Data and Decision, College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
Li Zeng: Laboratory for Big Data and Decision, College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
Yunfei Wang: National Key Laboratory of Information Systems Engineering, College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
Haoxiang Cheng: Laboratory for Big Data and Decision, College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
Zhong Liu: Laboratory for Big Data and Decision, College of Systems Engineering, National University of Defense Technology, Changsha 410073, China

Mathematics, 2024, vol. 12, issue 17, 1-15

Abstract: Tackling the intricacies of network dismantling in complex systems poses significant challenges. This task has relevance across various practical domains, yet traditional approaches focus primarily on singular metrics, such as the number of nodes in the Giant Connected Component (GCC) or the average pairwise connectivity. In contrast, we propose a unique metric that concurrently targets nodes with the highest degree and reduces the GCC size. Given the NP-hard nature of optimizing this metric, we introduce MaxShot, an innovative end-to-end solution that leverages graph representation learning and reinforcement learning. Through comprehensive evaluations on both synthetic and real-world datasets, our method consistently outperforms leading benchmarks in accuracy and efficiency. These results highlight MaxShot’s potential as a superior approach to effectively addressing the network dismantling problem.

Keywords: complex networks; network dismantling; graph representation learning; reinforcement learning (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/17/2766/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/17/2766/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:17:p:2766-:d:1473097

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().