FUNC: Finding critical nodes in uncertain networks through deep reinforcement learning

The problem of Finding Critical Nodes (FCN) is a classic challenge in network science, which aims to find the optimal sequence of nodes with the greatest network impact. It has been widely applied in various fields such as rumor suppression and epidemic containment. However, in real-world scenarios, the existence probability of edges depends on external conditions, and most networks are therefore uncertain. Traditional FCN methods typically assume that the network is deterministic, neglecting the impact of uncertainty on the critical node sequence. To address this issue, we propose a end-to-end deep reinforcement learning-based framework for Finding Uncertain Network Critical-nodes (FUNC), which can be trained on small-scale networks and generalized to unseen ones. Specifically, we first propose a Multi-head Attention-based Node Embedding to capture network structure, edge existence probabilities, and node cost features. Then, due to the high stochasticity of rewards in uncertain networks, we propose a Sequential Confidence Interval-based Monte Carlo Simulation to achieve stable reward computation with a low number of simulations. Finally, we present an Accumulated Normalized Network Performance-based reward calculation method, enabling the generation of high-quality solutions under various constraint types (e.g., additive and multiplicative). Extensive experiments on realistic/synthetic networks, across multiple uncertainty distributions, and different constraint types demonstrate that FUNC outperforms several state-of-the-art baseline methods in terms of accuracy, generalization, and efficiency.