A reinforcement learning-enhanced meta-heuristic framework for network dismantling
Min Wu, Wu Jie Shi, Fengwei Guo, Bitao Dai, Jianhong Mou, Suoyi Tan, Xin Biao Lu, Chaomin Ou · Journal of Physics Complexity · 2025
Abstract Many real-world systems are characterized by extensive connectivity, resulting in redundant network structures that enhance overall robustness but also complicate the accurate identification of critical nodes. To address this challenge, we propose two novel dismantling algorithms—adaptive meta-heuristic (AMH) and meta-heuristic with reinforcement learning (MHRL)—both of which operate without relying exclusively on detailed topological information. Specifically, AMH employs an adaptive mechanism at each iteration to refine its search, whereas MHRL leverages reinforcement learning to automatically select the optimal operation based on the current state—together enhancing dismantling effectiveness. Extensive targeted attack experiments on both synthetic and empirical networks demonstrate that MHRL not only achieves faster reductions in the largest connected component but also significantly outperforms state-of-the-art methods, with improvements in Schneider R reaching up to 23.66%. Correlation analysis reveals that MHRL’s removal strategy exhibits the lowest similarity to existing benchmarks, implying that the new approach characterizes structural features that was not captured by benchmarks. Furthermore, MHRL demonstrates better convergence compared to conventional optimization algorithms like Tabu Search, highlighting the advantages of integrating meta-heuristics with reinforcement learning. Overall, MHRL shows strong potential for dismantling tasks in small and medium-scale networks.