Vital node searcher: find out critical node measure with deep reinforcement learning. Issue 1 (31st December 2022)

• Record Type: Journal Article
• Authors: Du, Guanting; Zhu, Fei; Liu, Quan
• Is Part Of: Connection science. Volume 34:Issue 1(2022)
• Page Start: 1519
• Page End: 1539
• Publication Date: 2022-12-31
• Subjects: reinforcement learning -- deep reinforcement learning -- critical node -- network -- graph embedding; Neural computers -- Periodicals; Artificial intelligence -- Periodicals; Cognitive science -- Periodicals; Connectionism -- Periodicals; 006.3
• DOI: 10.1080/09540091.2021.2025210
• Languages: English
• ISSNs: 0954-0091

Abstract

Abstract : How to find the critical nodes in the network structure quickly and accurately is a topic of network science. Various algorithms for critical nodes already exist, of which, however, some are with high time complexity and the rest are limited in application range. To solve this problem, an algorithm, referred to as Vital Node Searcher (VNS), is proposed, which discovers critical nodes from a network based on deep reinforcement learning. The VNS method first takes advantage of the Graph Embedding to downscale the feature information of the target network, and then uses the deep Q network method to extract the critical node sequence. A Long-Short Term network module is designed and applied to fully exploit historical information that is contained in the sequence data. Moreover, a duelling Q network module is developed to enhance the precision of prediction. Both in terms of time complexity and performance, the VNS method is superior compared with other methods, which are validated by experiments of real world datasets. Moreover, VNS method has strong generalisation performance and can be applied to different types of critical node problems. The VNS method performed experiments on four datasets and obtained ANC scores that outperformed the other models respectively. The experiment results demonstrated that the VNS method had a stable and effective performance on finding out the critical node sequence.