Scholarlink

<p>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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年6月1日

查看全文
  • Yangming Zhou,
  • Di Zhao,
  • Gezi Wang,
  • Mengchu Zhou

摘要

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.