Computationally efficient attack design for robustness analysis of air transportation networks

Abstract

Maintaining robustness is a key challenge for present and future air transportation. The analysis of network robustness is a time-demanding task, whose complexity increases with the size of networks. Accordingly, network attacks are often built on network metrics, for instance, attacking the nodes in decreasing order of their degree or betweenness. Albeit the results can be insightful, there is no guarantee regarding the quality or optimality of these attacks. In this paper, we propose a new exploration/exploitation search technique for a computationally efficient attacking model, adapted from general game playing. We propose an incremental solution for the efficient computation of robustness measures, by exploiting the network similarity before and after executing an attack, and thus, avoiding redundant computations. We define four tasks in the attacking model: Static attack, interactive attack, dynamic attack, and finding the best attack. The analysis of real-world air transportation networks reveals that commonly used network metric-based attacking strategies are already suboptimal for short attacks of length two. Our computationally efficient attacking model contributes to scalable analysis of robustness, not only for air transportation, but also for networks in general.

Keywords:

• network robustness
• attacking strategy
• scalable analysis
• air transportation

Acknowledgements

The authors would like to thank Sabre Airport Data Intelligence (ADI) and Beihang University for providing the data in this study. The authors would like to particularly acknowledge Klaus Luetjens and Niclas Dzikus from German Aerospace Center (DLR) for the discussion about the data.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This research is partly supported by the Foundation for Innovative Research Groups of the National Natural Science Foundation of China [Grant No.61221061].