When Optimization Meets AI: An Intelligent Approach for Network Disintegration with Discrete Resource Allocation

Ruozhe Li, Hao Yuan, Bangbang Ren, Xiaoxue Zhang (), Tao Chen and Xueshan Luo
Additional contact information
Ruozhe Li: National Key Laboratory of Information Systems Engineering, National University of Defense Technology, Changsha 410073, China
Hao Yuan: National Key Laboratory of Information Systems Engineering, National University of Defense Technology, Changsha 410073, China
Bangbang Ren: National Key Laboratory of Information Systems Engineering, National University of Defense Technology, Changsha 410073, China
Xiaoxue Zhang: National Key Laboratory of Information Systems Engineering, National University of Defense Technology, Changsha 410073, China
Tao Chen: National Key Laboratory of Information Systems Engineering, National University of Defense Technology, Changsha 410073, China
Xueshan Luo: National Key Laboratory of Information Systems Engineering, National University of Defense Technology, Changsha 410073, China

Mathematics, 2024, vol. 12, issue 8, 1-20

Abstract: Network disintegration is a fundamental issue in the field of complex networks, with its core in identifying critical nodes or sets and removing them to weaken network functionality. The research on this problem has significant strategic value and has increasingly attracted attention, including in controlling the spread of diseases and dismantling terrorist organizations. In this paper, we focus on the problem of network disintegration with discrete entity resources from the attack view, that is, optimizing resource allocation to maximize the effect of network disintegration. Specifically, we model the network disintegration problem with limited entity resources as a nonlinear optimization problem and prove its NP-hardness. Then, we design a method based on deep reinforcement learning (DRL), Net-Cracker, which transforms the two-stage entity resource and network node selection task into a single-stage object selection problem. Extensive experiments demonstrate that compared with the benchmark algorithm, Net-Cracker can improve the solution quality by about 8∼62%, while enabling a 30-to-160-fold speed up. Net-Cracker also exhibits strong generalization ability and can find better results in a near real-time manner even when the network scale is much larger than that in training data.

Keywords: network disintegration; discrete resource allocation; deep reinforcement learning; combinatorial optimization (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/8/1252/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/8/1252/ (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:8:p:1252-:d:1379543

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 ().