针对随机网络设计高效节点破坏算法，提升系统韧性评估效率。
Heuristic algorithms for the stochastic critical node detection problem
- 提出启发式与基于学习的算法应对边存在概率的不确定性
- 在不同规模图上均实现高精度破坏效果，且启发式方法更高效
- 适合大规模网络脆弱性分析，尤其适用于交通与生物网络
给定一个网络，关键节点检测问题旨在寻找一组节点，其移除会破坏网络连通性。由于许多现实系统天然可建模为图结构，评估网络脆弱性至关重要，应用涵盖交通系统、交通预测、疫情控制和生物网络。本文研究一种随机版本的关键节点检测问题，其中边的存在由特定概率决定。我们提出启发式与基于学习的方法，并与现有算法进行对比。在从小到大规模的随机图上进行实验，边存活概率来自不同分布，结果表明所提方法有效：启发式方法通常表现最佳且具有高可扩展性，而基于学习的方法在网络规模和密度增长时推理时间几乎恒定。
原文摘要 · Abstract (English)
Given a network, the critical node detection problem finds a subset of nodes whose removal disrupts the network connectivity. Since many real-world systems are naturally modeled as graphs, assessing the vulnerability of the network is essential, with applications in transportation systems, traffic forecasting, epidemic control, and biological networks. In this paper, we consider a stochastic version of the critical node detection problem, where the existence of edges is given by certain probabilities. We propose heuristics and learning-based methods for the problem and compare them with existing algorithms. Experimental results performed on random graphs from small to larger scales, with edge-survival probabilities drawn from different distributions, demonstrate the effectiveness of the methods. Heuristic methods often illustrate the strongest results with high scalability, while learning-based methods maintain nearly constant inference time as the network size and density grow.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。