Robustness analysis metrics for worldwide airport network:A comprehensive study

Sun Xiaoqian,Volker Gollnick,Sebastian Wanelt,*

aSchool of Electronic and Information Engineering,Beihang University,100083 Beijing,China

bBeijing Key Laboratory for Network-based Cooperative ATM,Beijing 100083,China

cBeijing Laboratory for General Aviation Technology,Beijing 100083,China

dInstitute of Air Transportation Systems,German Aerospace Center,Blohmstrasse 18,21079 Hamburg,Germany

Robustness analysis metrics for worldwide airport network:A comprehensive study

Sun Xiaoqiana,b,c,Volker Gollnickd,Sebastian Wandelta,b,c,*

aSchool of Electronic and Information Engineering,Beihang University,100083 Beijing,China

bBeijing Key Laboratory for Network-based Cooperative ATM,Beijing 100083,China

cBeijing Laboratory for General Aviation Technology,Beijing 100083,China

dInstitute of Air Transportation Systems,German Aerospace Center,Blohmstrasse 18,21079 Hamburg,Germany

Air transportation systems resilience;Airport network;Attacking strategy;Robustness measure

Robustness of transportation networks is one of the major challenges of the 21st century.This paper investigates the resilience of global air transportation from a complex network point of view,with focus on attacking strategies in the airport network,i.e.,to remove airports from the system and see what could affect the air traffic system from a passenger’s perspective.Specifically,we identify commonalities and differences between several robustness measures and attacking strategies,proposing a novel notion of functional robustness:unaffected passengers with rerouting.We apply twelve attacking strategies to the worldwide airport network with three weights,and evaluate three robustness measures.We find that degree and Bonacich based attacks harm passenger weighted network most.Our evaluation is geared toward a unified view on air transportation network attack and serves as a foundation on how to develop effective mitigation strategies.

1.Introduction

Air transportation is one critical network infrastructure for a nation and it is becoming extremely important for public policy considerations.Disruptions of air transportation systems,either due to extreme weather conditions or terrorist attacks,can lead to huge economic losses.The eruption of Eyjafjallajoekull volcano in 2010 caused airline losses of approximately 1.7 billion US dollars and more than 10 million passengers were affected.1An overnight snowstorm on March 12,2013 disrupted the transport across northwestern Europe;in particular,Frankfurt airport was closed and airlines canceled about 700 flights.In order to avoid such high socio-economic costs,it is extremely critical to assess the robustness of air transportation systems against natural or intentional disruptions.

Complex network theory2provides powerful tools to understand the structures and dynamics of air transportation systems.Airport networks have often been analyzed,where nodes are airports and links exist between two airports if there are flight connections.3–7Several research focused on how delay is propagated in airport networks.8–10Based on fuzzy soft sets,Ref.11evaluated the airport importance and network efficiency with US and China’s airport networks as case studies,and the vulnerability of these two networks was also compared.Ref.12showed that the vast majority of all Intra-European passengers travel direct and the directness of the overall system increased from 2002 to 2012.Ref.13studied the robustness of USairport network,using attacking strategies based on betweenness,closeness,hyperlink induced topic search(HITS),and degree,with giant component as robustness measure.Ref.14studied the resilience of European air transport network against random flight failures,based on a multiplex network formalism,where the set of flights for each airline is considered as an interdependent network.Robustness of Australian network,based on degree,betweenness,strength,and random attacks,with giant component and network reachability robustness measures was investigated.15The worldwide airport network was studied under random attacks as well as degree and betweenness-based attacks with the shortest average path length and giant component as robustness measures.16

In air transportation networks,random failures correspond to the closure of an airport(node failure)or the cancellation of a flight(link failure)randomly,while targeted attacks correspond to the closure of an airport or the cancellation of a flight based on certain criteria.For instance,Beijing Capital International Airport(PEK)has the largest number of passengers(77531486)in 2013 in the whole world(Data source:http://www.airdi.net).Such hub nodes are critical for the structure of air transportation and they are inherently priorities for targeted attacks.One might think that airline routes are impermanent and links come and go all the time,and therefore robustness analysis is less important for this type of network than for other types of network with a more static structure,e.g.,electricity or road networks.However,it is a long process to establish a new route for an airline.Before setting up a new route,the airline network planning department needs to spend considerable amount of time to analyze the profitability of the new route.17Several factors need to be considered,for instance,market demand forecasting18,19,competitor analysis20,21,aircraft capacity planning,and passenger spill model.22,23Ultimately,the reason for studying the resilience of the system resides in the time frame associated with an attack to an airport.It is true that,if a route is closed(for instance because of adverse weather),alternative solutions can be found fast.Nevertheless,an attack to an airport may have long-term important consequences as in the recent case of 2016 Brussels bombings.It is thus important to prevent such attacks.In this research,we perform a systematic robustness analysis for the worldwide airport network against random failures and targeted attacks,with focus on several attacking strategies and robustness measures.

Several research on the robustness of the worldwide airport network has been conducted in the past years.Lordan et al.presented a methodology for the detection of critical airports in the worldwide airport network,and the network robustness was measured by the size of giant component.24The airports are isolated based on several node selection criteria,and especially a novel criterion,Bonacich power centrality,has been tested.Wei et al.introduced the flight route addition/deletion problem and compared three different methods to optimize the robustness of the airport network,with algebraic connectivity as the robustness measure;the Virgin America network was used as a case study with the link failure probability as weight.25Wang et al.compared the behavior of two real networks and two synthetic networks under degree based attacks using the size of giant component.26Louzada et al.proposed to reroute a series of flights within certain distances of original destination airports in order to improve the robustness of the worldwide airport network under degree targeted attacks,where robustness is measured by an estimation of the number of stranded passengers in the giant component.27Verma et al.analyzed the resilience of the worldwide airport network and revealed that it is a redundant and resilient network for long distance air travel,otherwise it breaks down completely due to removal of short insignificant connections.28Woolley-Meza et al. investigated the eruption of Eyjafjallajoekull volcano,September 11th terrorist attacks,and geographical disruptions in the worldwide airport network;effective distance was used to quantify the impact of disasters on the network.29Wuellner et al.analyzed the individual structures of seven US largest passenger airline networks and examined the networks’resilience to random/degree/betweenness targeted node deletion.30Lordan et al.also analyzed the robustness of three major airline/alliances route networks.31,32Wei et al.also studied the optimization of the robustness of the airport network,with algebraic connectivity as the robustness measure.33,34The effective distance is based on the idea that a small fraction of traffic is effectively equivalent to a large distance,and vice versa.35The size of giant component and travel cost in the giant component were used to quantify the network performance under various deletion processes.Moreover,the design of a robust hub network has also been studied.36Kotegawa et al.measured the robustness of airline service route network topology under random and targeted disruptions.37Closely related works are summarized in terms of robustness measures,attacking strategies,and network weights in Table 1.

In this research,which was motivated by the work of Ref.38,we extract data from the Sabre Airport Data Intelligence(ADI)(http://www.airdi.net)to build the worldwide airport network,and an excerpt is shown in Fig.1.Each node is one airport,and the size of a node is proportional to its degree,which is weighted by the number of passengers.In this figure,we only show the links which have more than 100,000 passengers travelling per year.Note that spherical links are not always drawn as the shortest connection,but go through the center of the projected map.We consider the network as directed and weighted;two different weights are used for this study:geographical distances and the number of passengers travelling between two airports.Given a consistent view on the worldwide airport network,the goal of this research is to make clear,through comparison,which attacking strategy harms the network most and which robustness measure is more appropriate for the network under disruptions.

We are interested in the robustness of air transportation systems under disruption from the function point of view38–41:transferring passengers from their origins to destinations.We use unaffected passengers with rerouting as a baseline measure from the passenger stakeholder’s perspective:if an airport is closed due to convective weather or intentional human disruptions,how many passengers can still make their journeys?We compare ourbaselinemetric to threeother robustness measures:the size of giant component,algebraic connectivity,and survived links.Formal definitions of these robustness measures can be found in Section 2.3.We consider twelve different attacking strategies:targeted attacks based on six network metrics(degree,betweenness,closeness,eigenvector,Bonacich,and damage)in descending and ascending order.

In our research,we only consider the robustness of the worldwide airport network as single mode transportation,i.e.,passengers are not allowed to take any alternative transportation means,such as buses or trains.We think that it is necessary to understand this single mode case first.Another important reason for this hypothesis is that working with the world network,alternative transportation means are not usually available.For instance,if a passenger has to go from Europe to China and the flight is canceled,a bus is not really an option in this case.Previous research on the robustness of airport networks mainly focused on topological robustness measures,for instance,the size of giant component and algebraic connectivity.Furthermore,a multitude of attacking strategies were proposed based on different network metrics.Given a consistent view on the worldwide airport network(related work techniques were evaluated on largely different datasets),our research aims at presenting an overview of the state-of-theart in single mode air transportation robustness and provides the starting point for future research on the robustness of multi-modal air transportation.

This paper is organized as follows.Section 2 presents our methodology to assess the robustness of air transportation systems,and German airport network is used as a small running network example to explain our methodology.In Section 3,we present the results of robustness analysis for the whole worldwide airport network.Finally,conclusions are drawn in Section 4.

Table 1 Summary of related works and proposed approach on robustness of worldwide airport network.

Fig.1 Worldwide airport network in 2013.

2.Methodology

In this section,we describe how airport networks can be attacked.We formally define the notation of weighted networks and the attack on weighted networks in Section 2.1.In Section 2.2,we present several attacking strategies in our attack model.We define a set of appropriate robustness measures in Section 2.3.In each section,we use the German airport network as a running example,since it is helpful to explain our methodology using an example based on a smaller network.We report on our evaluation for the worldwide airport network in Section 3.

2.1.Attacks on airport networks

One can distinguish two types of passenger weights:number of passengers from direct flights and number of passengers from flight intentions(OD pairs).The first type is considered from the physical network point of view:the number of passengers travelling between any two airports;passengers with multiple intermediate stops are counted for each connecting airport separately.The latter type is considered from the function point of view:the number of passengers travelling between origin/destination airports;passengers with multiple intermediate stops are not counted for the connecting airports.

If an airport is closed down,all direct flight connections from/to this airport are directly affected.However,the conclusion that all these passengers will not travel anymore is wrong.In Fig.3,we show a simple example for the German airport network:a passenger travels from HAM to STR,via two connecting airports FRA and MUC.Although this example might look unrealistic,since Lufthansa offers a direct flight from HAM to STR,six passengers booked this kind of travel with Lufthansa in January 2013.We suppose that MUC closes down because of an attack,and then one will conclude from direct flight passenger data that six passengers cannot travel from FRA to MUC and six more passengers cannot travel from MUC to STR.This conclusion is misleading for two reasons.First,the passengers can still travel from HAM to STR(via another direct flight,FRA,or any other scheduled airport connection).Second,if one really wants to assume that these passengers cannot travel anymore,one also needs to remove the six passengers for the flight from HAM to FRA.

Fig.2 German airport network in January 2013.

Therefore,in this paper we use the number of passengers from direct flights as the link weight,while we use the unaffected number of passengers from origin-destination pairs as a baseline measure for the robustness of the worldwide airport network.With flight intentions,the unaffected passenger problem boils down to the question whether two airports are still connected via another scheduled flight.

Fig.3 One example of an origin-destination pair with passengers travelling through two connecting airports.

In order to design an attack on a network,one can follow different strategies.A very simple strategy is a so-called random attack,where the sequence of removed nodes is chosen randomly.The effectiveness of such an attack(measured in the degradation of the network performance,see below)is usually rather low on average.One heuristic is to select the sequence of removed nodes based on certain network metrics.We discuss such attacks in Section 2.2.

Intuitively,one can distinguish two types of attacks in a network:strong attacks and weak attacks.Strong attacks refer to attacking important nodes first,while weak attacks refer to attacking unimportant nodes first.Strong attacks often require more knowledge about the targeted network:not only concerning topological properties,but also the traffic.

2.2.Attacking strategies

In addition to attacking a network randomly,attacks can also be based on the values of network metrics.In the following,we briefly review six chosen standard network metrics.

(1)Weighted degree.The degree of a node u is the sum of all weights for the incoming and outgoing links of u.

(4)Eigenvector centrality.It is the eigenvector of the largest eigenvalue of the adjacency matrix.This metric measures the influence of a node in the network.Nodes with high eigenvector centrality also connect to other nodes which have high eigenvector centrality.

Each of these metrics can be exploited as a strategy for attacking a network by either removing nodes in the order of descending metric values or ascending metric values.A common practice is,for instance,to attack nodes in decreasing order of degree.The intuition is that nodes with a high degree-often called hubs-are important for the network structure and therefore the removal of high-degree nodes harms the network most.In our study,we provide a complete picture of possibleattacks:randomattacks,strongattacks(descendingvalues of metrics),and weak attacks(ascending values of metrics).

Table 2 shows the top 10 ranked nodes in the German airport network based on the descending order of the six network metrics.Two different weights are used:geographical distances between two airports and the number of passengers travelling between two airports.All of the metric orders yield a different ranking.Therefore,it is interesting to further investigate which attacking strategy harms the network most.

?

2.3.Robustness measures

In this section,we use the unaffected passengers with rerouting as a baseline measure for the robustness of air transportation systems.Further,we introduce another robustness measure:survived links.For the purpose of comparison,we also briefly review two existing robustness measures:giant component48and algebraic connectivity.49

The unaffected passengers with rerouting(UPR)captures how many passengers still can travel when an airport is closed,with the reallocation of the passengers taken into account;this is denoted as dynamic robustness in Ref.50Note that our analysis focuses on the connectivity of the airports:passengers between certain OD pairs can still make their trips as long as the OD airports are connected via other airports from the original schedule.

The survived links(SL)is the number of remaining connections between airports after an attack on the network.

Fig.4 Number of passengers versus revenue in worldwide airport network in 2013.

We generated 1000 complete random attacks for the German airport network.For each of these attacks,we computed the attack traces:robustness measures compared to the percentage of removed nodes during an attack.The results are shown in Fig.5(a).

In order to visualize the commonalities of these random attacks,e.g.data points which occur frequently and independently of the chosen attack,we show the two-dimensional kernel density estimation for the percentage of removed nodes against the robustness measures in Fig.5(b).White areas indicate infrequent/unused points and darker areas represent commonalities.We draw the following conclusions:

(1)UPR is the baseline for the robustness measure.It calculates the percentage of passengers who can still travel after an attack took place.The attack traces are widespread.While some attacks are very successful(if important nodes are removed early),under other attacks the network keeps robust(with robustness of 80%)even if 50%of the nodes are removed.The two-dimensional kernel density of UPR shows the commonalities among random attack traces,which can be summarized as follows:(1)if only a few nodes are removed,the network remains robust(dark area in the top-left of the chart)and(2)if more than 60–70%of the nodes are removed,the network’s robustness is very low(dark area in the bottom-right of the chart).Intuitively,this is correct,since for the range between(say 1–70%),the random attacks do not have anything else in common.

Fig.5 Comparison of robustness measures for 1000 random attacks on German airport network.

(2)GC-robustness curves are either on or closely below the diagonal line.For most of the time,each attack can reduce the size of giant component of a network by one or zero,depending on whether the removed node was in the giant component before.Note that there are some cases that an attack can reduce the size of giant component more than one.We consider a network composed of two communities and connected by a central node.If that central node is deleted,the size of giant component would be greatly reduced.Since the size of giant component cannot be larger than the number of remaining nodes,the upper-right triangle of the attack trace area is unused.The two-dimensional kernel density suggests that for GC most of the random attacks have very similar properties(black diagonal).This conclusion contradicts the observation from UPR.

(3)A robustness measure should be monotonically descending.However,AC-robustness is increasing with the number of removed nodes.This shows that AC is inappropriate,if node removal is taken into account.AC was originally proposed as an edge-based robustness measure,where the number of nodes remains unchanged.In our attack scenario,AC yields unusable results.Therefore we will disregard AC below.The other three measures are monotonically descending.

(4)SL robustness curves are quite similar to UPR robustness curves.Compared to GC,SL also(1)allows to represent attack traces above the diagonal line and(2)does not(wrongly)suggestvery strong commonalities between random attacks.

3.Results

When a network is attacked,it is open how to select the order in which the nodes should be removed.48In this study,we apply twelve different attacking strategies to the worldwide airport network with three different weights(unweighted,distance weighted and passenger weighted):removing nodes based on six network metrics(degree,betweenness,closeness,eigenvector,Bonacich and damage)in descending and ascending order separately.We use three robustness measures to detect the decrease of the network performance caused by these attacks.In total we have 108 attacking scenarios(3 weights,12 attacking strategies and 3 robustness measures).We are interested to find out which attacking strategy harms the network most.We introduce the database in Section 3.1.Section 3.2 presents the results of several attacking strategies to the worldwide airport network with different robustness measures.

3.1.Database

For the application and analysis of the metrics,recent data from 2013 ADI was obtained.53The OD Market Section in ADI provides the details of the passenger itineraries:the total number of passengers and the total revenue between the origin and destination airports.For each OD pair,up to three connecting airports are recorded.

From this database,we select the origin and destination airports with at least 72 passengers travelling per year(i.e.,6 passengers travelling per month).Note that there is no standard threshold for the number of passengers or the number of flights between two airports when the airport network is constructed.For instance,Lehner selected the links with at least 600 flights per year(50 flights per month)in the European airport network.38Kotegawa et al.selected the links with at least 365 flights per year(i.e.,airports are required to have an average of at least one operation per day)in the U.S.airport network.54In this study,to our best knowledge,our threshold(72 passengers travelling per year)has the finest granularity.

We consider the worldwide airport network as directed and weighted;three different weights are used:unweighted,geographical distances,and the number of passengers travelling between two airports.In total,there are 3885 nodes and 228,080 links.The unweighted worldwide airport network has an average path length of 2.946 and an average clustering coefficient of 0.645.These values are comparable with the worldwide airport network constructed in Ref.24:average path length 3.94 and an average clustering coefficient 0.64.On average,there are 11845 passengers per airport connection.The minimum number of passengers is 73 and the maximum is 4418200(CJU:Jeju International Airport,South Korea-GMP:Gimpo International Airport,South Korea).The median number of passengers is 592 and standard deviation is 61986.

The average values of the six metrics in the worldwide airport network with three different weights are presented in Table 3.Each of these metrics is exploited as a strategy to attack the network.

3.2.System analysis of robustness for worldwide airport network

We perform system analysis of the robustness for the worldwideairportnetwork withthreedifferentweights(unweighted,distance weighted and passenger weighted)measured by UPR,GC and SL under attacks,respectively.The comparison of different attacking strategies is presented in Section 3.2.1,while the computational efficiency is compared in Section 3.2.2.

Table 3 Average values of six metrics in worldwide airport network using different weights with 3885 nodes and 228080 links.

3.2.1.Comparison of attacking strategies

Intuitively,one is more interested in strong attacks(descending order of metric values),since they are more harmful to the network than weak attacks(ascending order of metric values).Fig.6 presents the robustness measures(UPR,GC and SL)in the passenger weighted worldwide airport network under strong attacks.When UPR is used as the robustness measure,attacks based on Bonacich power centrality and degree are equally most harmful to the network.Bonacich power centrality is better for the initial phase of an attack(up to 7%of removed nodes)and degree is slightly better when more than 7%of the nodes are removed.With comparable attacking effectiveness,the computation of degree is 1–2 orders of magnitude faster than the computation of Bonacich.Since the computation time is often the bottle-neck for large-scale networks,degree is a very good candidate for an effective and lightweight attacking strategy,especially in the case of interactive attacks on large-scale networks.

On the other hand,the attack based on closeness is least harmful to the network.One explanation is that closeness of a node is the reciprocal of the sum of the shortest path distances from this node to all other nodes in the network,and since we use the number of passengers as link weight in the shortest path calculation,the closeness metric might become less meaningful.Regarding GC and SL,Bonacich power centrality is slightly better than degree,while eigenvector is the worst attacking strategy.

Note that there may be no ‘best” robustness measure or‘best” attacking strategy,and results may depend on the objective of a study.The objective of our study is to evaluate the robustness of air transportation systems from passengers’perspective,and we propose to use the unaffected passengers with rerouting as a baseline measure.In opposition to graphtheoretic metrics,this measure directly expresses the impact of airport failure on the traffic-not on(theoretical)properties of the graph.

In order to further investigate the correlation between UPR and other robustness measures,Fig.7 plots the robustness values of UPR against SL and GC for all six network metrics.The dashed diagonal grey line represents perfect correlation;the red line shows the dependency between pairs of robustness measures.The overlapping of the two curves indicates strong similarity between two robustness measures.We can observe that UPR and GC are least similar;SL is closer to the diagonal line and it is more similar to UPR than GC.

Table 4 presents the most successful targeted attacks based on node degree,where the first 40 attacked nodes(out of 3885 nodes,less than 1.1%)are listed.These attacks reduce the robustness of the network from 100%down to 50%,i.e.,50%of the passengers cannot travel any more although rerouting is enabled.The first attacked node is PEK,and PEK has the highest weighted degree in the passenger weighted worldwide airport network.Among 3885 airports,when we use the attacking strategy based on weighted degree,one only needs to attack 11 nodes(out of 3885 nodes,less than 0.3%),and then the performance of the network can be degraded to 80%.Especially,there are 7 Asian airports among these 11 attacked nodes.This shows the importance of Asia for the functioning of global air transportation systems.

Fig.6 Cross-comparison among three robustness measures(UPR,GC and SL)in passenger weighted worldwide airport network with targeted attacks based on descending order of six network metrics.

Fig.7 UPR versus robustness measures(GC and SL)in worldwide airport network with number of passengers as weight.

3.2.2.Comparison of computational efficiency

During our experiments,we noticed that the computation time of attacking strategies was rather different ranging from seconds,minutes to hours.Our initial hypothesis was that longer computation time might generate more effective attacking results.Therefore,we compare the computational efficiency of different attacking strategies and robustness measures.The run time for computing the attacking strategies is shown in Fig.8,while the run time for evaluating the robustness measures is shown in Fig.9.Note that different scales(seconds,minutes and hours)are used for measuring run time.Computing degree and eigenvector takes only a few seconds,while computing betweenness,closeness and Bonacich takes up to several minutes.The run time for SL is less than 0.2 s.The slowest attacking strategy(computation-wise)is damage,which takes up to three complete days when applied to the initial worldwide network.

In our 108 attacking scenarios,damage did not provide an effective attacking performance,although it took the longest time to compute.We think this counter-intuitive finding should draw more attention.Especially in the context of interactive simulations with larger networks,e.g.,what happens in case of any change to the network(node/link addition/deletion25),the computational time required for finding interesting(harming)attacks becomes more important.

On the other hand,calculating UPR is the most timeconsuming operation.For the initial network,it takes 3–4 s to evaluate the robustness.The more nodes are removed,the much time is spent on the rerouting process(up to ten seconds).Only when few nodes are left,the rerouting process speeds up recognizably and the run time decreases.Evaluating GC takes three seconds for the initial network and the run timeis decreased when more nodes are removed(because less nodes have to be analyzed for finding the giant component).The fastest robustness measure is SL,which is 1–2 orders of magnitude faster than the other two measures.This is an interesting property in the case of interactive attacks in future research.

Table 4 Description of the most successful targeted attack based on node degree to worldwide airport network with number of passengers as weight.

Fig.8 Run time for computing attacking strategies regarding six network metrics.

Fig.9 Run time for three different robustness measures when partial attacks are executed on worldwide network.

4.Conclusions

The safety and reliability of complex air transportation systems are vital for the society.In this study,we performed system analysis for the robustness of air transportation systems,with unaffected passengers with rerouting as a baseline measure.Given the most complete dataset available,we identify commonalities and differences between several robustness measures and attacking strategies for the worldwide airport network.The contributions of the paper are as follows:

(1)We applied twelve different attacking strategies(degree,betweenness,closeness,eigenvector,Bonacich and damage in ascending and descending order)to the worldwide airport network with three different weights(unweighted,distance and passenger)and evaluated three different robustness measures(UPR,GC and SL).All experiments were evaluated on the same dataset and give a consistent view on attacking airport networks.In total,we investigated 108 attacking scenarios.

(2)We find that GC is a rather bad robustness measure,since(1)it cannot represent weak attacks appropriately,and (2)it overestimates robustness for very strong attacks.SL is an alternative which solves(1),and reduces the effects of(2)).Furthermore,SL is 1–2 orders of magnitude faster to compute than GC,which is an interesting property in the case of interactive attacks.

(3)The attacking strategies:degree and Bonacich are the best methods for attacking the worldwide airport network with passenger weights using UPR.Bonacich is better for the initial phase of an attack(up to 7%of removed nodes)and degree is slightly better when more than 7%of the nodes are removed.With comparable attacking effectiveness,the computation of degree is 1–2 orders of magnitude faster than the computation of Bonacich.Since the computation time is often the bottle-neck for large-scale networks,degree is a very good candidate for an effective and lightweight attacking strategy,especially in the case of interactive attacks on large-scale networks.Furthermore,closeness is the worst strategy for the robustness measure UPR.For GC/SL,Bonacich is slightly better than degree.Eigenvector is the worst attacking strategy.In our experiments,damage took the longest time to compute,but did not provide effective attacking performance.

(4)Our analysis shows that knowledge of an attacker significantly influences the effectiveness of attacking strategies.When the attacker is aware of the number of passengers travelling on routes(passenger-weighted network),the attack is more successful than that conducted by less informed attacker(unweighted or distanceweighted network).

(5)We analyze the computational resources required for each attacking technique on the same airport network.While these resources are often neglected in related work,we show that the time to compute an attack is sometimes orders of magnitude faster/slower,while providing similar results.Given that many graph problems are not efficiently solvable,i.e.solutions do not scale up with the size of the graph,we advocate the use of simple,yet efficient attacking strategies for future robustness analysis of air transportation networks.41In particular,running interactive robustness analysis on large networks is only feasible with short response time,if the attacking strategies can be computed efficiently.

In this study,we analyzed the robustness of the worldwide airport network under node random failure and targeted attacks with several attacking strategies and robustness measures.Our research provides a unified view on attacking air transportation networks and serves as a starting point to further explore effective mitigation strategies to defend against disruptions.55,56

In the following,we discuss some limitations of our initial study,which can be addressed in future work.(1)While our research focused on static attack generators,in practice,attacks can also have a dynamic nature.Thus,future work should take into account the iterative calculation of metric values:after each single-node attack to a network,the network metric is recomputed for the remaining nodes and the node with the highest/lowest value is removed next,since it was shown that this recalculation of metrics can be more effective than the pre-computation of a static attack.48(2)One assumption of our study is that intentional failures in airports can happen all over the world,which is impossible to coordinate in practice,if many airports have to be affected.Therefore,future research could investigate other attacking scenarios,where local regions are affected,instead of widely distributed nodes.(3)Similarly,we neglect the effect of regional airport system,where multiple airports serve the same metropolitan regions.We did not consider the case of multi-modal transportation in a sense that passengers could connect to other airports by other means of transportation,e.g.,using train or bus connections.We would like to address this problem in future work.(4)Furthermore,our analysis relied on the connectivity of the airports:passengers between certain OD pairs can still make their trips as long as the OD airports are connected via other airports from the original schedule.Capacity constraints should be taken into account in future work.(5)Rerouting passengers after a global air transport failure assumes that all passengers still want to travel.Experiences with past terrorist attacks indicate that the passengers often cancel their travel plans.Analyzing and modeling such psychological effects can further help to understand and improve the robustness of the network.

Acknowledgements

This study was supported by the National Natural Science Foundation of China(Nos.61650110516,61601013 and 61521091).The authors would like to thank Sabre Airport Data Intelligence(ADI)and German Aerospace Center(DLR)for providing the data in this study.The authors would like to particularly acknowledge Klaus Luetjens and Niclas Dzikus for providing us with the way to download the data from ADI.The authors also thank Stephan Lehner for the initial discussion on robustness in air transportation systems.

1.Wilkinson SM,Dunn S,Ma S.The vulnerability of the European air traffic network to spatial hazards.Nat Hazards2012;60(3):1027–36.

2.Newman M.Networks-an Introduction.Oxford:Oxford University Press;2010.

3.Sun XQ,Wandelt S,Linke F.Temporal evolution analysis of the European air transportation system air navigation route network and airport network.Transportmetrica B2015;3(2):153–68.

4.Zanin M,Lillo F.Modelling the air transport with complex networks:a short review.Eur Phys J Special Top2013;215(1):5–21.

5.Sun XQ,Wandelt S.Network similarity analysis of air navigation route systems.Transport Res E-Log2014;70:416–34.

6.Wandelt S,Sun XQ.Evolution of the international air transportation country network from 2002 to 2013.Transport Res ELog2015;82:55–78.

7.Cong W,Hu M,Dong B,Wang Y,Feng C.Empirical analysis of airport network and critical airports.Chin J Aeronaut2016;29(2):512–9.

8.Fleurquin P,Ramasco J,Eguiluz V.Data-driven modeling of systemic delay propagation under severe meteorological conditions.Tenth USA/Europe air traffic management research and development seminar;2013.p.1–10.

9.Baumgarten P,Malina R,Lange A.The impact of hubbing concentration on flight delays within airline networks:An empirical analysis of the(US)domestic market.Transport Res E-Log2014;66(1):103–14.

10.Zou B,Hansen M.Flight delay impact on airfare and flight frequency:A comprehensive assessment.Transport Res E-Log2014;69(3):54–74.

11.Li S,Xu X.Vulnerability analysis for airport networks based on fuzzy soft sets:from the structural and functional perspective.Chin J Aeronaut2015;28(3):780–8.

12.Lehner S,Koelker K,Luetjens K.Evaluating temporal integration of European air transport.29th Congress of the international council of the aeronautical sciences(ICAS);2014 Sep 7–12;St.Petersburg,Russia.2014.p.1–10.

13.Yang Y,Li Z,Chen Y,Zhang X,Wang S.Improving the robustness of complex networks with preserving community structure.PLoS One2015;10(2):e0116551.

14.Cardillo A,Zanin M,Gomez-Gardenes J,Romance M,Garcia del Amo AJ,Boccaletti S.Modelling the multi-layer nature of the European air transport network:resilience and passengers rescheduling under random failures.Eur Phys J Special Top2013;215(1):23–33.

15.Hossain M,Alam S,Rees T,Abbass H.Australian airport network robustness analysis:a complex network approach.Australasian Transport Research Forum;2013.p.1–10.

16.Frohn R.Robustness in the air transportation network.Amsterdam:University of Amsterdam;2012.

17.Fan TPC,Tan ATL,Geng X.Rapid capacity expansions and failure:a trap for new airline entrants?Transport Res E-Log2014;61(1):176–91.

18.Airbus.Global market forecast;Toulouse:Airbus Press Room;2014.

19.Boeing.Current market outlook;Chicago:Boeing;2014.

20.Adler N,Smilowitz K.Hub-and-spoke network alliances and mergers:price-location competition in the airline industry.Transport Res B-Meth2007;41(4):394–409.

21.Adler N.Hub-spoke network choice under competition with an application in a hub-and-spoke network.Transport Sci2005;39(1):58–72.

22.Hsiao CY,Hansen M.A passenger demand model for air transportation in a hub-and-spoke network.Transport Res ELog2011;47(6):1112–25.

23.Wang DD,Klabjan D,Shebalov S.Attractiveness-based airline network models with emmbedded spill and recapture.J Airline Airport Manage2014;4(1):1–25.

24.Lordan O,Sallan JM,Simo P,Gonzalez-Prieto D.Robustness of the air transport network.Transport Res E-Log2014;68:155–63.

25.Wei P,Chen L,Sun D.Algebraic connectivity maximization of an air transportation network.Transport Res E-Log2014;61:13–27.

26.Wang H,Huang J,Xu X,Xiao Y.Damage attack on complex networks.Physica A2014;408(408):134–48.

27.Louzada V,Arajo N,Verma T,Daolio F,Hermann H,Tomassini M.Critical cooperation range to improve spatial network robustness.Plos One 2015;10(3):e0118635.

28.Verma T,Arau′jo NA,Herrmann HJ.Revealinig the structure of the world airline network.Sci Rep2014;4:5638.

29.Woolley-Meza O,Grady D,Thiemann C,Bagrow JP,Brockmann D.Eyjafjallajo¨kull and 9/11:the impact of large-scale disasters on worldwide mobility.PLoS One2013;8(8):e69829.

30.Wuellner DR,Roy S,D’Souza RM.Resilience and rewriting of the passenger airline networks in the United States.Phys Rev E2010;82(5):056101.

31.Lordan O,Sallan JM,Simo P,Gonzalez-Prieto D.Robustness of airline alliance route networks.Commun Nonlinear Sci Numer Simul2015;22(1):587–95.

32.Lordan O,Sallan JM,Escorihuela N,Gonzalez-Prieto D.Robustness of airline route networks.Physica A2016;445:18–26.

33.Wei P,Spiers G,Sun D.Algebraic connectivity maximization for air transportation networks.IEEE Trans Intell Transp Syst2014;15(2):685–98.

34.Wei P,Sun D.Weighted algebraic connectivity:an application to airport transportation network.WorldCongress2011;18(1):13864–9.

35.Brockmann D,Helbing D.The hidden geometry of complex,network-driven contagion phenomena.Science2013;342(6164):1337–42.

36.Shahabi M,Unnikrishnan A.Robust hub network design problem.Transport Res E-Log2014;70(C):356–73.

37.Kotegawa T,Fry D,DeLaurentis D,Puchaty E.Impact of serve network topology on air transportation efficiency.Transp Res Pt C-Emerg Technol2014;40(1):231–50.

38.Lehner S.Complex networks IV.Berlin,Heidelberg:Springer;2013.

39.Criado R,Romance M.Handbook of optimization in complex networks,springeroptimizationanditsapplications.New York:Springer;2012.p.3–36.

40.Lehner S,Gollnick V.Function-structure interdependence of passenger air transportation:Application of a systemic approach.14th AIAA Aviation Technology,Integration,and Operations Conference;2014 June 16–20,Atlanta,USA.Reston:AIAA;2014.

41.Wandelt S,Sun XQ,Cao XB.Computationally efficient attack design for robustness analysis of air transportation networks.Transportmetrica A2015;11(10):939–66.

42.Freeman LC.Centrality in social networks conceptual clarification.Soc Networks1978;1(3):215–39.

43.Brandes U,Fleischer D.Centrality measures based on current flow.Lecture Notes Comput Sci2005;3404:533–44.

44.Bonacich P.Power and centrality:a family of measures.Am J Soc1987;92(5):1170–82.

45.Rodan S.Choosing the b parameter when using the Bonacich power measure.J Soc Struct2011;12(4):1–23.

46.Bonacich P,Rodan S.Comment&response on choosing the ‘b’.J Soc Struct2011;12:1–11.

47.Latora V,Marchiori M.Vulnerability and protection of critical infrastructures.Phys Rev E2015;71:015103R.

48.Holme P,Kim BJ,Yoon CN,Han SK.Attack vulnerability of complex networks.Phys Rev E2002;65(2):056109.

49.Jamakovic A,Van Mieghem P.On the robustness of complex networks by using the algebraic connectivity.NETWORKING 2008 Ad Hoc and sensor networks,wireless networks,next generation internet;2008.p.183–94.

50.Lordan O,Sallan JM,Simo P.Study of the topology and robustness of airline route networks from the complex network approach:a survey and research agenda.J Transp Geogr2014;37:112–20.

51.Janson S,Knuth DE,Luczak T,Pittel B.The birth of the giant component.Random Struct Algorithms1993;4(3):231–358.

52.Fiedler M.Algebraic connectivity of graphs.Czech Math J1973;23(2):298–305.

53.www.airdi.net.Airport data intelligence(ADI)[Internet].Texas:Sarbre;2013.[cited 2016 June 13].Available from:http://www.airdi.net.

54.Kotegawa T,DeLaurentis D,Noonan K,Post J.Impact of commercial airline network evolution on the U.S.air transportation system.Ninth USA/Europe air traffic management research and development seminar;2011.

55.Arnold H,Masad D,Pagani GA,Schmidt J,Stepanova E.Complex networks V.Berlin,Heidelberg:Springer;2014.

56.Caschili S,Reggiani A,Medda F.Resilience and vulnerability of spatial economic networks.Netw Spat Econ2015;15(2):1–6.

14 June 2016;revised 9 September 2016;accepted 24 November 2016

Available online 16 February 2017

*Corresponding author at:School of Electronic and Information Engineering,Beihang University,100191 Beijing,China.

E-mail address:wandelt@buaa.edu.cn(S.Wandelt).

Peer review under responsibility of Editorial Committee of CJA.