Heuristic algorithms for the stochastic critical node detection problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912740785782784 |
|---|---|
| author | Bayarsaikhan, Tuguldur Chinchuluun, Altannar Arulselvan, Ashwin Pardalos, Panos |
| author_facet | Bayarsaikhan, Tuguldur Chinchuluun, Altannar Arulselvan, Ashwin Pardalos, Panos |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_01497 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Heuristic algorithms for the stochastic critical node detection problem Bayarsaikhan, Tuguldur Chinchuluun, Altannar Arulselvan, Ashwin Pardalos, Panos Discrete Mathematics Machine Learning 90C27, 90C15, 90C59 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. |
| title | Heuristic algorithms for the stochastic critical node detection problem |
| topic | Discrete Mathematics Machine Learning 90C27, 90C15, 90C59 |
| url | https://arxiv.org/abs/2512.01497 |