EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Distance-based critical node detection and its application to network vulnerability assessment

Yangming Zhou, Di Zhao, Gezi Wang, Mengchu Zhou

ENGINEERING Management · 2026-06 · 13 (2) · 490-514

DOI: 10.1007/s42524-026-5349-2 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ENGINEERING Management, online erschienen am 01.06.2026. Verfasst von Yangming Zhou und 3 weiteren Autor:innen. Die Arbeit nennt 36 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A popular strategy for network vulnerability assessment is to identify critical nodes, whose deletion maximally degrades the connectivity of the original network. Decision makers usually have information about the network structure they intend to obtain, but do not know the number of nodes to target. In this context, we study a distance-based critical node problem with unknown budget, known as the β-distance-based vertex disruptor problem. To solve it, we first derive three integer linear programming formulations, i.e., recursive, triangular connectivity-based, and reduced path-based ones. They are then solved using the CPLEX solver. To approximately solve large instances that an exact solver fails to solve, we propose a simple and effective integrated strategic oscillation search that combines hill climbing and strategic oscillation. It examines a large neighborhood by alternating between a tabu-enhanced destruction procedure and a random order-based improving construction procedure. Extensive experiments on both real-world and synthetic benchmark instances demonstrate the advantages of the proposed formulations and heuristic. In particular, the reduced path-based formulation outperforms both recursive and triangular connectivity-based ones. The proposed heuristic is significantly faster than exact and state-of-the-art algorithms. Finally, we perform a case study on air transportation networks to gain insights into the impacts of COVID-19.

Zitieren

APA

Zhou, Y., Zhao, D., Wang, G., & Zhou, M. (2026). Distance-based critical node detection and its application to network vulnerability assessment. ENGINEERING Management, 13(2), 490-514. https://doi.org/10.1007/s42524-026-5349-2

Vancouver

Zhou Y, Zhao D, Wang G, Zhou M. Distance-based critical node detection and its application to network vulnerability assessment. ENGINEERING Management. 2026;13(2):490-514. doi:10.1007/s42524-026-5349-2

BibTeX
@article{Zhou2026,
  author = {Zhou, Yangming and Zhao, Di and Wang, Gezi and Zhou, Mengchu},
  title = {Distance-based critical node detection and its application to network vulnerability assessment},
  journal = {ENGINEERING Management},
  year = {2026},
  volume = {13},
  number = {2},
  pages = {490--514},
  doi = {10.1007/s42524-026-5349-2}
}
Kostenlos starten →