Shiyn LIU, Zhenfu LI, Jilong ZHONG, Dqing LI

a College of Transportation Engineering, Dalian Maritime University, Dalian 116026, China

b School of Reliability and Systems Engineering, Beihang University, Beijing 100083, China

c Science and Technology on Reliability and Environmental Engineering Laboratory, Beijing 100083, China

d Equipment Management and UVA Engineering College, Air Force Engineering University, Xi’an 710051, China

KEYWORDS

Abstract The air transportation system has a critical impact on the global economy.While the system reliability is essential for the operational management of air traffic, it remains challenging to understand the network reliability of the air transportation system. This paper focuses on how the global air traffic is integrated from local scale along with operational time.The integration process of air traffic into a temporally connected network is viewed as percolation process by increasing the integration time constantly. The critical integration time TP which is found during the integration process can measure the global reliability of air traffic. The critical links at TP are also identified, the delay of which will influence the global integration of the airport network. These findings may provide insights on the reliability management for the temporal airport network.

1. Introduction

For modern society, air transportation has become increasingly important.1It has been observed that an efficient air transportation system can improve regional economy by facilitating labor mobility and fostering local industries. However,with the rapid growth of air transportation demand,air traffic is becoming unevenly distributed and more congested, which has an adverse effect on the efficiency of the whole system.The total cost of all air transportation delays in the United States in 2007 has been estimated at $31.2 billion.2In 2016,nearly one million flights arrived at the gate at least 15 minutes behind schedule in US, and of those flights nearly 116,000 flights arrived at least 2 hours late,impacting more than 9 million passengers.3Therefore, it is critical to further understand the complexity and emergent failure behavior of the air transportation system.

The air transportation system has been extensively studied based on complex network theory from topology analysis to functional analysis. As for the topology analysis, previous studies mainly include basic topology structure, community structure and the identification of critical airports and flights.Jia and Jiang built the US airport network and found its scale-free property and small-world property.4Zhang et al.built Chinese air route network and examined its structural heterogeneity.5Guimera et al. explained the community structure of the world airport network according to geographical and political considerations.6Gurtner et al. studied the European air transportation by detecting the communities of the navigation point network,the airport network,and the sector network, respectively.7Lordan et al. proposed a criterion on the base of Bonacich power centrality to detect the important airports of the global airport network.8As for the functional analysis, the following problems have been studied. In terms of the prediction of passenger flow, Ryczkowski et al.predicted passenger flows of the global air transportation network through the gravity model.9Besides, many researchers explored the role of air transportation system in epidemic propagation.10–15

The reliability of the air transportation network has become a bottleneck for its operation and management. As for the topology approach, researchers measure how the connectivity of the airport network changes after deleting nodes(such as airports) or links (such as flights). The strategies of nodes removal and links removal are mainly based on betweenness centrality,8degree centrality,16flight flow and failure centrality.17,18The connectivity of the airport network has also been estimated by different methods, such as size of the largest cluster,19,20clustering coefficient,8average shortest path,21efficiency,8average degree,8algebraic connectivity,22average edge betweenness and Laplacian energy.23,24As for the functional approach, the practical operation of the air transportation system has been considered. In terms of flight delay, researchers studied the mechanisms to spread delays and the congestion transition of air traffic.25–28Ar?kan et al.considered the total propagated delay from previous flights and built stochastic models to explore how structures and schedules affect the reliability of airline network.29Voltes-Dorta et al. studied the network vulnerability and node criticality based on the delays in disrupted passengers.30Paleari et al. studied the effective mobility of the air traffic networks in different regions based on the travel times of passengers.31Cardillo et al.focused on the passengers re-scheduling problem and found that the resilience of the air transportation system was reduced by considering the multi-layer structure.32Janic′estimated the cost of affected flights due to the disruptive event.33Fleurquin et al. quantified the level of the airport network congestion by measuring the size of congested airport clusters.26Ezaki and Nishinari considered the ground congestion of the airport and explored the stability of air traffic according to the density-flux relationship.27A recent study has proposed ‘‘traffic percolation” in the road network,34and critical percolation properties of city traffic have been carefully studied.35,36

Different from road network with static structure,air traffic network is a typical temporal network, while its network reliability during the temporal integration has rarely been considered. Recently, the temporal characteristics of real-life networks in different fields have been studied.37,38The airport network has temporal characteristics because the existence of flight between any airport pair changes over time under the influence of many factors such as flight schedules, weather and policies. The temporal characteristics of the airport network have been studied mainly in structural features. Pan and Saramaki defined the temporal path to measure distances of temporal networks and applied the methods to the American airport network.39Based on this, Ito and Nishinari proposed two temporal distance indexes by considering the behavior of passengers to explore the effect of burstiness in the air transportation network.40From a larger time scale,Zhang et al. studied Chinese air transportation system based on complex network theory and investigated its evolution from 2002 to 2009.41Jia et al. built the US air traffic network and explored its evolution characteristics in 20 years.42Meanwhile,it still remains unclear how the temporal characteristics affect the reliability of the whole airport network. Here we view the integration process of air traffic into a temporally connected network as percolation process and regard the critical integration time during the integration process as a measurement of global reliability of air traffic. Furthermore, we identify the critical links, the delay of which will influence the global integration of the airport network.

2. Methods

2.1. Dataset

Data is collected from the airline on-time performance data,which is accessible at the US Bureau of Transportation Statistics.3Airlines that exceed 1%of the total domestic revenue for scheduled-service passengers are required to report on-time data. From this dataset, we collect the actual departure time and arrival time of each flight on July 8, 2017 and on July 9,2017. There are three preprocessing steps for the data collected. First, we remove the flights that are diverted or cancelled. Second, we convert the time of each flight to be expressed in Eastern Standard Time (EST), from the presence of local time in the dataset.Third,we limit the area of the airport to 48 contiguous states excluding Alaska and the Hawaiian Islands. The data show that during the 48 h, the U.S.domestic airport system has in total 28564 flights,269 airports,and 1896 airport pairs between which at least one flight occurred.

2.2. Construction of temporal airport network

In the temporal airport network, nodes represent airports and links are defined if there is a flight between two airports in a particular time period. Here we use a 4-tuples (i,j,tdep,tarr)to represent the flight that occurred from airportito airportj, with departure timetdepand arrival timetarr. As shown in Fig.1(a), for a given time window [t0,t0+T], if a flight withtdep≥t0andtarr＜t0+Toccurs between airportiand airportj,we consider that these two airports are connected during this time window. By this means, a temporal airport network can be built for any time window[t0,t0+T], which becomes denser as the value of the integration timeTincreases.

3. Results

3.1. Network reliability of airline operation

Fig.1 Graphic representation of network construction for air traffic.

To observe how the global traffic appears during one day from a given starting timet0, we increase the integration timeTby 5 min each time untilTequals 1440 min (24 h), and study the changing process of the temporal airport network evaluated by the size of weakly connected components.For a certainT,traffic network can be constructed in the way that only flights withtdep≥t0andtarr＜t0+Tare considered as a link. As shown in Fig.1(a),for a given time window[t0,t0+T],the flight[i,j,tdep1,tarr1]withtdep1≥t0andtarr1＜t0+Tshows that airportiis connected to airportjduring this time window, but the flight[k,l,tdep2,tarr2]withtdep2＜t0cannot represent that airportkis connected to airportlduring[t0,t0+T].In addition,we can vary the time window [t0,t0+T] by changing the values oft0andT.The number of flights is increasing from 05:00 AM in Fig.1(b), which will in turn increase the number of links. The flight duration is mostly concentrated more than 1 h in Fig.1(c).WhenTis 0 h,there is no flight in the network and all airport nodes are isolated.WhenTis 24 h,the one-day temporal airport network is globally connected.The size of the largest cluster grows as the integration timeTincreases, and covers the main area of the country when the integration time is just above the critical thresholdTP,which is defined as theTvalue when the second-largest cluster reaches its maximum size.

TPrepresents a critical time point at which the whole air traffic network is integrated from local scale to global scale,according to percolation theory.43,44In other words, only when the considered time span is larger thanTPcan air traffic span over the whole network scale,otherwise air traffic will be disconnected in small isolated clusters.Hence,TPmeasures the minimum integration time required for air traffic to cover the whole network scale,which reflects the global operational reliability of the air traffic.

3.2. Percolation process on temporal airport network

When the starting timet0is 8:00 AM, forT=1.33 h, only small airport clusters emerge(Fig.2(a))and the air traffic cannot span over the whole network. As the value ofTincreases to 3.67 h, a giant cluster including most of airports is formed(Fig.2(c)). WhenT=1.92 h, the second-largest cluster reaches the maximum size (Fig.2(b)), which signifies the integration of the temporal network,43,44and air traffic will be integrated from local scale to global scale in the next 5 min.Therefore,TP, the phase transition point, of the integration process starting from 8:00 AM is 1.92 h. We show this whole integration process in Fig.2(d). During the whole integration process,both the largest clusterGand the second-largest clusterGSincrease as the integration timeTincreases from the beginning. WhenT=1.92 h,GSstarts to decrease from 35 to less than 5,due to the merge of clusters.This usually marks the integration of the whole temporal network.

As the starting timet0changes during the day,TPis found rather stable as shown in Fig.2(e), except whent0is between 0:00 AM and 3:30 AM with fewer departing flights (Fig.1(b)). Whent0is between 5:00 AM and 9:30 PM, values ofTPare about 2 h, which means that the temporal air network is connected statistically in 2 h. This is possibly due to the spatio-temporal coordination of flights for the emergence of global traffic. Whent0is between 0:00 AM and 3:30 AM, values ofTPare mostly more than 3 h. As time here is expressed in EST,there are few flights over the East Coast from 0:00 AM to 3:30 AM.Besides,the number of airports is relatively low in the West Coast,where flights during this period are mainly distributed due to the time difference.Therefore,longer time span is needed to increase the number of flights, insuring the air traffic span over the whole network.

3.3. Identification of critical links during percolation process

As we view the integration process of air traffic as percolation process, it is suggested that the links appearing early during this process tend to form clusters, which are backbones for the integration process. Therefore, for each starting timet0,bridging links can be considered as critical links because their appearance time determines the value ofTP.Here we define the appearance time of a link as the earliest arrival time of corresponding flights. We identify the critical links by comparing the temporal airport networks around the critical thresholdTP. Figs. 3(a) and (b) demonstrate the links added before and after the criticalityTP, showing that the giant cluster is integrated from local clusters by connection of them. Some of these links are very important for bridging unconnected airport clusters and are thus considered as critical links.

To study how the critical links affect the global reliability,we delay the appearance time of critical links and calculate the newTPof the changed integration process.Here we define the appearance time of a link as the earliest arrival time of corresponding flights. Fig.3(c) shows thatTPis significantly increased by only delaying the appearance time of the critical linkA, which cannot be achieved by delaying the appearance time of the linkB. It is suggested that only linkAplays an important role in bridging different traffic clusters, instead of linkBappearing by chance near the critical point of traffic percolation. Furthermore, delay of one random link or the link with the highest betweenness can neither change the critical integration time of the whole temporal air traffic network.Results show that the critical links identified by our method are not random and neither with the highest betweenness,which is usually considered as a main criterion for measuring the importance of links in the network.45–47

Fig.2 Percolation of temporal airport networks.

Fig.3 Critical links of airport network during one integration process (t0=7:15 AM).

In addition, we measure the appearance time of the top 10 links with the highest betweenness in the one-day integrated airport network (t0=7:15 AM). It can be seen in Fig.3(d)that links with the highest betweenness appear mostly later than the critical links. Especially, for link with the highest betweenness, the arrival time of the first flight between these two airports is over 15 h after 7:15 AM, which is far behind the critical integration time,i.e.09:10 AM.It is suggested that this link does not play a role in bridging different clusters for 13 h later than the integration time point.

Different from fixed static critical links found by structural analysis, the critical links found here evolve with the starting timet0and are usually different in different integration processes.We further identify the critical links in temporal airport networks integrated from all starting times, which are plotted and marked in Fig.4(a)and(c).In Fig.4(c),the width of links is proportional to occurrence times.Notice that the occurrence distribution of critical links is not even, that is, a few critical links are with high occurrence times and most of the critical links are with low occurrence times. It can be seen in Fig.4(c) that the most frequent critical link connects Minneapolis–Saint Paul International Airport and Stapleton International Airport.This small group of the critical links with high occurrence times will provide the optimization target for the traffic reliability management.

In addition, we explore the critical links with high occurrence times (more than 5) when the starting timet0belongs to morning (5:00 AM-11:00 AM), afternoon (11:00 AM-5:00 PM),or evening(5:00 PM-11:00 PM),respectively.These critical links are plotted and marked in Fig.4(b) and (d). Notice that the critical links with high occurrence distribute differently during these three periods, and only two links appear in the three periods simultaneously. It can be found in Fig.4(d) that Stapleton International Airport has the most critical links connected with high occurrence when the starting timet0belongs to morning and afternoon, and both Kansas City International Airport and Dallas Fort Worth Regional Airport have the most critical links connected with high occurrence when the starting timet0belongs to evening. All these three airports locate in the central United States.

3.4. Comparison of percolation processes in air traffic network

To compare our results with the percolation processes on the static airport network, we explore how the sizes ofGandGSin the temporal and static airport networks change along withp,which represents a fraction of total links in the one-day airport network. Aspincreases, the sizes of bothGandGSincrease, and we define the critical value,pc, as thepvalue when the size ofGSreaches the maximum value.

Fig.4 Occurrence of critical links.

Fig.5 Evolution of G and GS in temporal and static airport networks along with p.

For example, for a typical starting time (t0=12:00 AM),we plot in Fig.5(a)the integration process of the temporal airport network, during which links are added based on their appearance time, and the value ofpcequals 0.126. Here we define the weight of the link as the number of flights between an airport pair. We also plot three integration processes of the corresponding one-day integrated static airport network,during which links are added randomly (Fig.5(b)), based on increasing rank of link weight (Fig.5(c)), and based on decreasing rank of link weight (Fig.5(d)), and the values ofpcequal 0.043, 0.012, and 0.033, respectively. Here we define the weight of the link as the number of flights between two airports.The critical value of the integration process on the temporal airport network is found much larger than that of the other three integration processes on the static airport network.This is possibly due to the correlation of appearance times of flights, leading to clustering effect of flights and slower percolation in the real integration process. As the starting timet0changes during the day,pcis found usually larger in the integration processes of the temporal airport network (shown in Fig.5(e)), than the random cases in Fig.5(f). In the real integration, the appearance of a flight is mostly limited by travel demand and flight cost.48At the beginning, flights with early departure time and short flight time emerge.These local flights may represent higher traffic demand and lower flight cost,which can coordinate and form different local clusters. This slows down the real integration process of airline network and emphasizes the role of bottleneck flights to integrate the whole network.

4. Conclusions

Researchers have studied the reliability of air transportation mainly from two aspects: (A) the passenger-centric metrics including the number of affected passengers under system failures32and the total delay of all disrupted passengers;30,31(B)the flight-centric metrics including the magnitude of delay propagation25,26and the percentage of delayed or canceled flights.33Instead of passenger or flight viewpoint, our reliability measurement considers in the network viewpoint how the temporal characteristics affect the integration of different air routes into a whole network.We regard the air transportation system as a temporal network, and study the evolution of the largest cluster along with operational time. We view the integration process of air traffic into a temporally connected network as percolation process, and focus on how long it takes to integrate local air traffic into global traffic. We regard the critical integration time as a measurement of the global reliability of air traffic based on percolation theory. Through this integration process, we can identify critical links bridging different airport clusters,and the delay of these critical links influences the network’s global reliability.In addition,we compare our results with three percolation processes of the corresponding static airport network,and find that the critical value of the integration process on the temporal airport network is much larger than that of the other three integration processes on the static airport network. Our findings may provide a new way to understand the reliability of air traffic as an integration process of temporal network. This can be used to understand the coordination effect of different flights,evaluate the reliability of the whole air network, and also identify the critical flights for the network reliability. For the air traffic operators,improving the critical flights identified by our methods can improve the reliability of air transportation system.

Acknowledgements

We acknowledge support from the National Natural Science Foundation of China (Nos. 71822101 and 71771009)and the Fundamental Research Funds for the Central Universities.