# Robustness Analysis of Air Route Network Based on Topology Potential and Relative Entropy Methods

Authors: Guangjian Ren
Journal: Journal of Advanced Transportation
 (2021)

---

## Abstract

Air route network (ARN) is the important carrier of air transport, and its robustness has important influence on the safety and stability of air transport. To analyze the robustness of ARN, in this paper, a topology potential relative entropy (TPRE) model is proposed, based on topology potential (TP) and relative entropy (RE) methods. Firstly, the TPRE model is established as the theoretical basis for the research. Secondly, an air route reduction network (ARRN) model is constructed according to real Chinese ARN. Besides, the basic topology features of ARRN are given by complex network theory. To prove the applicability, objectivity, and accuracy of the proposed method, attack strategies including random, degree, betweenness, closeness, eigenvector, and Bonacich are used to attack ARRN. Eventually, the performance of ARRN robustness is analyzed by network efficiency, size of giant component, and the proposed TPRE model. This conclusion has practical significance for optimizing ARN structure and improving airspace efficiency.


---

## Body

## 1. Introduction

Air route network (ARN) is one of the important parts of air traffic systems. In the air transportation, all the flights will fly along the ARN; namely, ARN manages and limits the flight trajectory. Therefore, the robustness of the ARN has important impact on the safety and efficiency of air transport. Due to the expansion of air transportation and the diversified development of air route requirements, ARN will become more and more complicated, and the bearing pressure is getting bigger, causing ARN to be more susceptible to external interference. So, robustness of transportation networks is one of the major problems that needs to be solved urgently.Essentially, the safety and smoothness of air traffic are inseparable from the integrity of the ARN. When an aircraft flies in airspace, it often encounters emergencies (such as bad weather and temporary closure of the route), which leads to the damage of the structure and the decrease of the traffic capacity of the route. To study the robustness of the route structure is to evaluate the rationality and anti-interference of the ARN and, at the same time, provide a scientific basis for the optimization of the route structure and the dynamic adjustment of the airspace. The relative entropy theory can evaluate the relative changes of two vectors, and it is sensitive to the changes of the robustness parameters of the route. Topological potential can describe the interaction between network nodes and characterize the difference in the topological position and the importance reflected by the node’s own attributes. Therefore, the combination of the two can effectively evaluate the robustness of the ARN.The paper is organized as follows. The literature review is in Section2. Section 3 introduces the basic concept of network topology potential (TP) and builds the matrix form of TP. In Section 4, a topology potential relative entropy (TPRE) model is proposed. In Section 5, a Chinese air route reduction network (ARRN) model is constructed, and the robustness of ARRN is analyzed by the proposed method. Finally, Section 6 concludes this paper and future work.


## 2. Literature Review

In general, the issue of air transportation network is investigated from the perspective of complex network. Zanin and Lillo [1] present a short review of the recent use of complex network methods for the characterization of the structure of air transport and of its dynamics, finding that most studies focus on the topological and metric properties of flight networks. The characteristics of American air transportation network are analyzed by complex network theory in [2]. Liu et al. [3] use complex network theory to model airline route networks and then propose an effective and efficient genetic algorithm to optimize airline route networks. Connectivity and concentration of Lufthansa’s network are studied by complex network theory in [4, 5]. Cai et al. [6] study the Chinese air route network (CARN) within the framework of complex networks and find that some topological features of CARN are obviously different from those of the Chinese airport network (CAN). In [7], Cardillo et al. study the dynamics of the European air transport network by using a multiplex network formalism, and the results show that multiplexity strongly affects the robustness of the European air network. The network structure and nodal centrality of individual cities in the air transport network of China (ATNC) are examined through a complex network approach in [8]. A novel network model is proposed with airports as nodes and the correlations between traffic flow of airports as edges, and then Cong et al. [9] investigated network properties to identify critical airports in the network by the model. The process of delay propagation is modelled by using complex networks in [10] to describe the structure underlying the phenomenon of delay propagation in the Chinese air transport system. Du and Liang et al. [11] analyze the robustness of Chinese air route network and identify the vital edges by a memetic algorithm.In addition, robustness analysis of transportation networks is also a hot issue to apply complex network theory. Zhang et al. [12] investigate the role of transportation network topology, and the topology’s characteristics, in a transportation system’s ability to analyze the resilience to disaster events. The air navigation route system of fifteen different countries from a consistent worldwide airspace database and these airspace structures are analyzed by using complex network theory in [13]. Shao [14] discusses the robustness and structure of networks studied under different attack strategies. Robust approach for concurrent aircraft design and airline network design is discussed in [15]. Lordan et al. [16] study the topology and robustness of airline route networks through complex network theory and propose a survey and research agenda. The topology and robustness of the network route of airlines following low cost carriers (LCCs) and full service carriers (FSCs) business models are studied in [17], and the results show that FSC hubs are more central than LCC bases in their route network. The robustness of the three major airline alliances’ (that is, Star Alliance, Oneworld, and SkyTeam) route networks is analyzed in [18]. Hossain et al. [19] present a complex network approach for measuring the performance and estimating the resilience of an airport network to study the Australian Airports Network (AAN). In [20], Wei et al. analyze and optimize the algebraic connectivity of the air transportation network to measure the network robustness. A new index called the relative area index (RAI) is proposed in [21] to analyze the robustness of European air traffic network. Yan et al. [22] put forward the average edge betweenness to assess vulnerability of complex transportation network and find out key factors in complex transportation network. Under different attack strategies in the airport network, the resilience of global air transportation is investigated from the perspective of complex networks [23]. Reggiani et al. [24] discuss the role of connectivity in the concept of resilience and vulnerability in transport research. The vulnerability of the European air transport network to major airport closures is studied in [25], from the perspective of the delays imposed to disrupted airline passengers.In recent years, the research on the robustness of complex networks has also received continuous attention from scholars. Bellingeri and Cassi [26] use both classic binary node properties and network functioning measure to analyze robustness of weighted networks; simultaneously, the response of real world and model networks to node loss accounting for links weight in the model is analyzed. The structural robustness of mammalian transcription factor networks is discussed in [27]. Bellingeri et al. [28] analyze the robustness of real-world complex weighted networks and find that the robustness of the real-world complex networks against nodes-links removal is negatively correlated with link weights heterogeneity. In [29], the robustness of six real-world complex weighted networks is discussed by the link removal strategies. Shang [30] discusses the subgraph robustness problem and puts forward a framework to investigate robustness properties of the two types of subgraphs under random attacks, localized attacks, and targeted attacks. Besides, a rewiring mechanism based on Shannon entropy concept is proposed in [31], to streamline the complex networks configuration in order to improve their resiliency.Based on the analysis above, the robustness of a Chinese air route reduction network (ARRN) model is analyzed in this paper, by using a proposed TPRE method. Results show that the proposed method performs well in measuring the ARRN robustness.


## 3. Network Topology Potential Model

### 3.1. Topology Potential

The network node potential is proposed based on the data field theory in physics. The network system is regarded as an abstract system containing multiple nodes and interactions of them. There are field effects around each node, and any node in the field will be influenced by the combined effect of other ones. The interaction and association of network nodes are described by a model named topology potential.In a given network,G=V,E, where V=vi|i=1,2,…,N is the set of nodes, N is the number of nodes, E=vi,vj|vi,vj∈V is the set of edges, and K=E is the number of edges.The topology potential (TP) of nodevi, denoted by φvi, is expressed as follows [32, 33]:(1)φvi=∑j=1Nmj×e−dij2/α,i,j∈1,2,…,N,where mj is the attributes, used to indicate the influence of node centrality, dij is the shortest distance between nodes vi and vj, and α represents the control (impact) parameter, which is used to regulate impact range of the nodes.Through further analysis above, the following formula is obtained:(2)φv1φv2φv3⋮φvN=m1e−d112/α+m2e−d122/α+m3e−d132/α,…,mNe−d1N2/αm1e−d212/α+m2e−d222/α+m3e−d232/α,…,mNe−d2N2/αm1e−d312/α+m2e−d322/α+m3e−d332/α,…,mNe−d3N2/α⋮m1e−dN12/α+m2e−dN22/α+m3e−dN32/α,…,mNe−dNN2/α=e−d112/αe−d122/αe−d132/α⋯e−d1N2/αe−d212/αe−d222/αe−d232/α⋯e−d2N2/αe−d312/αe−d322/αe−d332/α⋯e−d3N2/α⋮⋮⋮⋯⋮e−dN12/αe−dN22/αe−dN32/α⋯e−dNN2/α∗m1m2m3⋮mN.The network TP withN nodes can be expressed in matrix form, denoted by Φ:(3)Φ=ED∗M,where TP vector is(4)Φ=φv1,φv2,…,φvNT,matrix M is(5)M=m1,m2,…,mNT,and matrix ED is(6)ED=e−d112/αe−d122/αe−d132/α⋯e−d1N2/αe−d212/αe−d222/αe−d232/α⋯e−d2N2/αe−d312/αe−d322/αe−d332/α⋯e−d3N2/α⋮⋮⋮⋯⋮e−dN12/αe−dN22/αe−dN32/α⋯e−dNN2/α.The control parameterα is not related to the number of nodes N; actually, the value of matrix ED is determined by matrix dij and the control parameter α. Therefore, when the parameter α is determined, the TP is determined by the characteristics of the complex network.


### 3.2. The Control Parameter

The control parameterα has an important influence on the impact range of the nodes. Its value directly controls the scope of influence of the nodes. The study of TP is determined by the optimal parameter and the optimization analysis of control parameter, which depends on the change of the topological potential entropy.For a networkGV,E, the TP is φvi,i=1,2,…,N. The topological potential entropy, denoted by H, is(7)H=−∑i=1NφviZlogφviZ,where Z is the normalization factor, and it is expressed as(8)Z=∑i=1Nφvi.The topology potential entropyH is a function of the parameter α when the matrices M and dij are determined.The uncertainty of network is the smallest for the completely nonuniform network, and then the topology potential entropy obtains the minimum value; the topology potential of each node in the network is equal to a completely uniform network, and then the differences among the node attributes are the most stochastic, and the topology potential entropy is the maximum. Thus, the optimal parameter, denoted byαZ, is actually the corresponding parameter when the topology potential entropy is the minimum, that is minH⟶αZ.According to the analysis of the topology potential entropy, it can be known that whenα=0, φj⟶i approaches 0, and there is no effect between nodes vi and vj, then φvi=si=s, and the topology potential entropy approaches the maximum value Hmax=logN. When α⟶+∞, φj⟶i⟶sj; at this moment, the effect among any nodes is identical, and there is φvi=N⋅s. Meanwhile, the topology potential entropy also approaches Hmax=logN.The value of potential entropy reflects the uncertainty of the network. With the parameterα changing, the topology potential entropy reaches the maximum at both ends. The minimum exists in a certain part of the middle. At this point, the network has minimal uncertainty, and the control parameter reaches the optimal value. Topology potential entropy curve is shown in Figure 1.Figure 1
The curve ofH with the control parameter α.Through analysis, it can be seen that when the control parameter is determined, the topology potential is a function of network characteristics. Therefore, the study of the network topology potential can reflect the change of the network characteristics and further reflect the network robustness.


## 3.1. Topology Potential

The network node potential is proposed based on the data field theory in physics. The network system is regarded as an abstract system containing multiple nodes and interactions of them. There are field effects around each node, and any node in the field will be influenced by the combined effect of other ones. The interaction and association of network nodes are described by a model named topology potential.In a given network,G=V,E, where V=vi|i=1,2,…,N is the set of nodes, N is the number of nodes, E=vi,vj|vi,vj∈V is the set of edges, and K=E is the number of edges.The topology potential (TP) of nodevi, denoted by φvi, is expressed as follows [32, 33]:(1)φvi=∑j=1Nmj×e−dij2/α,i,j∈1,2,…,N,where mj is the attributes, used to indicate the influence of node centrality, dij is the shortest distance between nodes vi and vj, and α represents the control (impact) parameter, which is used to regulate impact range of the nodes.Through further analysis above, the following formula is obtained:(2)φv1φv2φv3⋮φvN=m1e−d112/α+m2e−d122/α+m3e−d132/α,…,mNe−d1N2/αm1e−d212/α+m2e−d222/α+m3e−d232/α,…,mNe−d2N2/αm1e−d312/α+m2e−d322/α+m3e−d332/α,…,mNe−d3N2/α⋮m1e−dN12/α+m2e−dN22/α+m3e−dN32/α,…,mNe−dNN2/α=e−d112/αe−d122/αe−d132/α⋯e−d1N2/αe−d212/αe−d222/αe−d232/α⋯e−d2N2/αe−d312/αe−d322/αe−d332/α⋯e−d3N2/α⋮⋮⋮⋯⋮e−dN12/αe−dN22/αe−dN32/α⋯e−dNN2/α∗m1m2m3⋮mN.The network TP withN nodes can be expressed in matrix form, denoted by Φ:(3)Φ=ED∗M,where TP vector is(4)Φ=φv1,φv2,…,φvNT,matrix M is(5)M=m1,m2,…,mNT,and matrix ED is(6)ED=e−d112/αe−d122/αe−d132/α⋯e−d1N2/αe−d212/αe−d222/αe−d232/α⋯e−d2N2/αe−d312/αe−d322/αe−d332/α⋯e−d3N2/α⋮⋮⋮⋯⋮e−dN12/αe−dN22/αe−dN32/α⋯e−dNN2/α.The control parameterα is not related to the number of nodes N; actually, the value of matrix ED is determined by matrix dij and the control parameter α. Therefore, when the parameter α is determined, the TP is determined by the characteristics of the complex network.


## 3.2. The Control Parameter

The control parameterα has an important influence on the impact range of the nodes. Its value directly controls the scope of influence of the nodes. The study of TP is determined by the optimal parameter and the optimization analysis of control parameter, which depends on the change of the topological potential entropy.For a networkGV,E, the TP is φvi,i=1,2,…,N. The topological potential entropy, denoted by H, is(7)H=−∑i=1NφviZlogφviZ,where Z is the normalization factor, and it is expressed as(8)Z=∑i=1Nφvi.The topology potential entropyH is a function of the parameter α when the matrices M and dij are determined.The uncertainty of network is the smallest for the completely nonuniform network, and then the topology potential entropy obtains the minimum value; the topology potential of each node in the network is equal to a completely uniform network, and then the differences among the node attributes are the most stochastic, and the topology potential entropy is the maximum. Thus, the optimal parameter, denoted byαZ, is actually the corresponding parameter when the topology potential entropy is the minimum, that is minH⟶αZ.According to the analysis of the topology potential entropy, it can be known that whenα=0, φj⟶i approaches 0, and there is no effect between nodes vi and vj, then φvi=si=s, and the topology potential entropy approaches the maximum value Hmax=logN. When α⟶+∞, φj⟶i⟶sj; at this moment, the effect among any nodes is identical, and there is φvi=N⋅s. Meanwhile, the topology potential entropy also approaches Hmax=logN.The value of potential entropy reflects the uncertainty of the network. With the parameterα changing, the topology potential entropy reaches the maximum at both ends. The minimum exists in a certain part of the middle. At this point, the network has minimal uncertainty, and the control parameter reaches the optimal value. Topology potential entropy curve is shown in Figure 1.Figure 1
The curve ofH with the control parameter α.Through analysis, it can be seen that when the control parameter is determined, the topology potential is a function of network characteristics. Therefore, the study of the network topology potential can reflect the change of the network characteristics and further reflect the network robustness.


## 4. Network Topology Potential Relative Entropy Model

### 4.1. Relative Entropy Theory

Relative entropy, also known as Kullback–Leibler divergence (KLD), is a basic conception in the probability theory and information theory. The relative entropy is an asymmetrical measure of the difference between two probabilities.LetPx and Qx be two discrete probability distributions of the value of x, and according to [34–36], the relative entropy is defined as(9)DPQ=∑PxlogPxQx,where DP‖Q is the relative entropy of Px to Qx.For continuous random variables, the relative entropy is expressed as(10)DPQ=∫PxlogPxQxdx.The relative entropy is a measure of asymmetry between the two probability distributionsP and Q, namely, DP‖Q≠DQ‖P. Therefore, it does not represent a true measure or distance. In the field of information theory, DP‖Q represents the information consumption generated when the true distribution P is fitted with the probability distribution Q, where P represents the true probability distribution and Q represents the fitting distribution. In addition, the value of relative entropy is nonnegative, that is DP‖Q≥0.When two probability distributions are similar, the relative entropy value is small, and as the difference between the two distributions increases, the relative entropy value also increases. Therefore, relative entropy can compare the similarity of different distributions and assess the relative changes in characteristics. In this paper, the relative entropy theory is used to analyze the relative change of network topology potential, when the air route network under different attack strategies. As a result, the robustness of air route network is analyzed.


### 4.2. Topology Potential Relative Entropy Model

Network robustness can be explained by the fact that when certain or random damage occurs in the network, and some or all of the subnets are affected and damaged by the outside world, the network can maintain and restore its performance and effectiveness to an acceptable level within a specified period of time. The influence of topology structure on the robustness of complex networks generally includes random failure and intentional failure of the network. In this section, intentional attacks and random attacks are performed on the air route network, and then the relative entropy of the network topology potential is studied to evaluate the robustness of the network. The network failure is shown in Figure2.Figure 2
Network failure schematic diagram.Assume that the value of air route network topology potential is distributed within the range ofφmin,φmax. The topology potential is averagely divided into n intervals, and each interval is denoted by xii=1,2,3,…,n; namely, X=xi|i=1,2,3,…,n is a set of intervals. The probability that the original network topology potential falls within each interval is Pxi=pii=1,2,3,…,n. When the network is subjected to a random attack, a certain node is randomly deleted. At this time, the probability that the network topology potential falls within each interval is Sxi=sii=1,2,3,…,n. When the network is deliberately attacked, the important nodes are deleted. In this case, the probability that the network topology potential falls within each interval is Txi=tii=1,2,3,…,n. The distribution law of the random variable x is as follows:(11)x1x2x3⋯xnp1p2p3⋯pns1s2s3⋯snt1t2t3⋯tn.From the relative entropy theory, we can get the following formulas:(12)DS=DPS=p1logp1s1+p2logp2s2+⋯+pnlogpnsn=∑i=1npilogpisi,DT=DPT=p1logp1t1+p2logp2t2+⋯+pnlogpntn=∑i=1npilogpiti.Comparing the two relative entropy values, it can be seen that whenDS>DT, the random attack has a greater impact on the air route network, and the network robustness is stronger under the intentional attack than under the random attack. When DS<DT, intentional attacks have a greater impact on the route network, and robustness is good in random attacks. Especially, when DS=DT, this indicates that the structural characteristics of the air route network are affected by the same degree of random attacks and intentional attacks, and the two attacks have similar impact on the network robustness.


## 4.1. Relative Entropy Theory

Relative entropy, also known as Kullback–Leibler divergence (KLD), is a basic conception in the probability theory and information theory. The relative entropy is an asymmetrical measure of the difference between two probabilities.LetPx and Qx be two discrete probability distributions of the value of x, and according to [34–36], the relative entropy is defined as(9)DPQ=∑PxlogPxQx,where DP‖Q is the relative entropy of Px to Qx.For continuous random variables, the relative entropy is expressed as(10)DPQ=∫PxlogPxQxdx.The relative entropy is a measure of asymmetry between the two probability distributionsP and Q, namely, DP‖Q≠DQ‖P. Therefore, it does not represent a true measure or distance. In the field of information theory, DP‖Q represents the information consumption generated when the true distribution P is fitted with the probability distribution Q, where P represents the true probability distribution and Q represents the fitting distribution. In addition, the value of relative entropy is nonnegative, that is DP‖Q≥0.When two probability distributions are similar, the relative entropy value is small, and as the difference between the two distributions increases, the relative entropy value also increases. Therefore, relative entropy can compare the similarity of different distributions and assess the relative changes in characteristics. In this paper, the relative entropy theory is used to analyze the relative change of network topology potential, when the air route network under different attack strategies. As a result, the robustness of air route network is analyzed.


## 4.2. Topology Potential Relative Entropy Model

Network robustness can be explained by the fact that when certain or random damage occurs in the network, and some or all of the subnets are affected and damaged by the outside world, the network can maintain and restore its performance and effectiveness to an acceptable level within a specified period of time. The influence of topology structure on the robustness of complex networks generally includes random failure and intentional failure of the network. In this section, intentional attacks and random attacks are performed on the air route network, and then the relative entropy of the network topology potential is studied to evaluate the robustness of the network. The network failure is shown in Figure2.Figure 2
Network failure schematic diagram.Assume that the value of air route network topology potential is distributed within the range ofφmin,φmax. The topology potential is averagely divided into n intervals, and each interval is denoted by xii=1,2,3,…,n; namely, X=xi|i=1,2,3,…,n is a set of intervals. The probability that the original network topology potential falls within each interval is Pxi=pii=1,2,3,…,n. When the network is subjected to a random attack, a certain node is randomly deleted. At this time, the probability that the network topology potential falls within each interval is Sxi=sii=1,2,3,…,n. When the network is deliberately attacked, the important nodes are deleted. In this case, the probability that the network topology potential falls within each interval is Txi=tii=1,2,3,…,n. The distribution law of the random variable x is as follows:(11)x1x2x3⋯xnp1p2p3⋯pns1s2s3⋯snt1t2t3⋯tn.From the relative entropy theory, we can get the following formulas:(12)DS=DPS=p1logp1s1+p2logp2s2+⋯+pnlogpnsn=∑i=1npilogpisi,DT=DPT=p1logp1t1+p2logp2t2+⋯+pnlogpntn=∑i=1npilogpiti.Comparing the two relative entropy values, it can be seen that whenDS>DT, the random attack has a greater impact on the air route network, and the network robustness is stronger under the intentional attack than under the random attack. When DS<DT, intentional attacks have a greater impact on the route network, and robustness is good in random attacks. Especially, when DS=DT, this indicates that the structural characteristics of the air route network are affected by the same degree of random attacks and intentional attacks, and the two attacks have similar impact on the network robustness.


## 5. Robustness Analysis of Air Route Reduction Network

### 5.1. Air Route Reduction Network Model

With the continuous development of the aviation industry, airspace resources are also becoming increasingly tense. As the main carrier of aircrafts, air routes are the important component of airspace. The continuous increase of traffic flow makes the traffic density in the air route network too large, which further highlights the irrationality of the air route network structure. As a result, the pressure on the air route continues to increase, the risk of air route failure increases, and the robustness plays an important role in the operation of the air route. The layout of Chinese air route network is shown in Figure3.Figure 3
The distribution of Chinese air route network.As shown in Figure3, the red dots represent air route waypoints such as airports, navigation points, route intersections, and reporting points. Simultaneously, the air route segments are depicted by the blue solid line and connected by a series of waypoints. In this section, an air route reduction network (ARRN) model is constructed to analyze the robustness of the network. The press of model building is as follows:(a)
An airport and its terminal area are collapsed into one node. Meanwhile, Navigation points, intersections, and important reporting points are reduced to nodes. If there is a route between two nodes, then add an edge.(b)
If there is a waypoint on the route, and it is not a convergence point such as an intersection and an inflection point, the point is fused to other nodes on the principle of proximity, and the original air route segment remains unchanged.(c)
When there are two or more air route segments between two nodes, multiple route segments are condensed to one edge. All of them constitute an undirected network model.Based on the theory mentioned above, the ARRN model is shown in Figure4.Figure 4
Air route reduced network model.In Figure4, red solid dots indicate the nodes that reduced by the waypoints of the air route network, and blue solid lines represent the edges between nodes. A series of nodes and edges are interconnected to form the ARRN model. At the same time, it is known that the distribution of nodes and edges is uneven; namely, the distribution of air routes in the airspace is extremely uneven.On the basis of the analysis of the network structure in Figure4, the basic topology features of the ARRN can be obtained in Table 1.Table 1
Basic topology features of the ARRN.
ParametersNodesEdgesAverage degreeClustering coefficientAverage shortest path lengthMixing coefficientARRN88117623.990.2110.03−0.029Table1 shows some basic network parameters of ARRN. The average degree of the network is about 4, indicating that each node is directly connected with 4 neighbors. The clustering coefficient and the average shortest path length of the network are 0.21 and 10.03, respectively, illustrating that the network has small-world properties to some degree. Mixing coefficient of the network is negative, which means that large-degree nodes are more likely to link the small-degree ones; that is, the network is disassortative.


### 5.2. Attack Strategies

Robustness has important theoretical and practical value for air route networks. Generally, complex networks face two attack strategies: random attack and intentional attack. Random attack is that a node or an edge has failed by being randomly attacked with a certain probability. Intentional attack is that the node or edge is attacked according to certain strategy and fails. Based on complex network theory, intentional attack strategies include degree, betweenness, closeness, eigenvector centrality, and Bonacich centrality.The degree of nodevi is defined as the number of edges connected to this node. Intuitively, the greater the degree of a node, the greater the importance of the node in a certain sense.The betweenness of nodevi is defined as the fraction of shortest paths between node pairs that pass through the node of interest, which reflects the role and influence of the node in the entire network. The betweenness of node vi, denoted by Bvi is [37, 38](13)Bvi=∑s≠i≠t∈Vnstvinst,where nst is the number of shortest paths between nodes vs and vt, and nstvi denotes the number of shortest paths between vs and vt, which pass through node vi.Based on [39, 40], closeness of node vi is defined as the reciprocal of the sum of geodesic distances to all other nodes of V, and it is calculated by the following formula:(14)Ccvi=1∑j=1,j≠idij,where dij is the geodesic distance between vi and vj. The greater the closeness of the node, the greater the centrality of the node, and the more important it is in the network.Dangalchev (2006) modified the definition to a general form, called residual closeness in [41]. Residual closeness is able to reflect the effects of node removal even if this removal does not result in disconnected components, and it is expressed as(15)CRvi=∑j=1,j≠i2−dij.Eigenvector centrality of nodevi, denoted as CEvi is computed by [42, 43](16)CEvi=λmax−1∑j=1Naijej,where λmax is the maximum eigenvalue of the adjacency matrix A and e=e1,e2,…,eNT is the corresponding eigenvector, aij is the connection between node vi and node vj:aij=1 when there is a connection existing, aij=0 otherwise.Bonacich centrality is defined as follows [44]:(17)Cδ,β=δI−βA−lA,where δ is a scaling constant, β reflects the effects of the centrality of its neighbors on a node’s centrality and β<1/λmax, I is an identity matrix, and l is a column vector of ones.According to the above attack strategies, the top-20 nodes of ARRN are obtained as shown in Figures5(a)–5(f) respectively.Figure 5
The top-20 nodes of ARRN ranked by random, degree, betweenness, closeness, eigenvector, and Bonacich metrics, respectively.
(a)(b)(c)(d)(e)(f)Figure5 shows the spatial distribution of top-20 nodes (see solid green dots) ranked by different strategies in ARRN, where Figure 5(a) shows one of the results of the random strategy. It is shown in Figure 5 that most of the top-20 nodes are located in Central-south and Southeast China. From Figures 5(c) and 5(d), we can see that the distributions based on betweenness and closeness are similar; meanwhile, the results of degree and Bonacich are extremely close (see Figures 5(b) and 5(f)). However, the eigenvector is different, and the distribution is extremely concentrated (see Figure 5(e)).


### 5.3. Network Topology Potential

In Section3.2, the key step in getting topology potential is to determine the optimal control parameter αZ. According to the ARRN model, the function curve of topology potential entropy H and control parameter α is obtained, and the result is shown in Figure 6.Figure 6
Topology potential entropyH changes with α.As depicted in Figure6, the topology potential entropy H decreases first and then increases. When α=1.0, H gets the minimum value Hmin. Therefore, the optimal control parameter αZ=1.0.Based on the topology potential theory, the nodes topology potential of the ARRN are achieved in Figure7.Figure 7
The distribution of ARRN nodes topology potential.The topology potential of ARRN nodes is averagely divided inton=7 intervals, and the results are shown in Figure 7. That is, the set of intervals is X=xi|i=1,2,…,7. From the theory in Section 3.2, we can get the distribution law of the random variable x and it is expressed as follows:(18)X0,55,1010,1515,2020,2525,3030,35Probability0.0800.2960.3840.1520.0520.0270.009.From the distribution law, the value range and probability distribution of the network topology potential can be clearly and directly observed. In the next section, the relative entropy of topology potential under different attack strategies will be discussed to analyze the robustness of the ARRN.


### 5.4. Robustness Analysis

In order to analyze the robustness of the ARRN, different attack strategies mentioned in Section4.2 are implemented on the network, and the top-20 nodes in Figure 5 are removed by the order of descending metric values. Then, some robustness measures including network efficiency, giant component, network topology potential, and topology potential relative entropy are applied to measuring performance of the network robustness. The results are shown in Figure 8.Figure 8
Comparison of robustness measures for different attacks on ARRN, and the top-20 nodes are removed by the order of descending metric values.
(a)(b)(c)(d)Figure8 presents the results of six attack strategies to ARRN with four different robustness measures. In Figure 8(a), network efficiency decreases as a function of the number of nodes removed in ARRN for each criterion. With the betweenness strategy, the rate of efficiency reduction is higher than that of others (see Figure 8(a)). Meanwhile, the line of efficiency in closeness is slightly above betweenness. However, degree and Bonacich have similar effects on ARRN efficiency, for their line almost overlaps as shown in Figure 8(a). The impact of attack with eigenvector strategy on ARRN efficiency is less than that of other intentional attacks, but higher than that of random attack.In Figure8(b), the size of ARRN giant component is a function of removed nodes to analyze the robustness of the network. As shown in Figure 8(b), the slope of the line with eigenvector strategy is the largest; thus, the eigenvector criterion has a significant effect on ARRN giant component. The lines of degree and Bonacich almost coincide, so they have similar impact on ARRN giant component. The sizes of ARRN giant component and removed nodes are almost linear when under the betweenness and closeness strategies. Simultaneously, the fluctuation between giant component and removed nodes is great under random attack.The computational ARRN topology potential is compared in Figure8(c) under different attack strategies. From Figure 8(c), we find that lines of degree, betweenness, and Bonacich have similar slopes, illustrating that the effects on ARRN topology potential caused by the three strategies are close to each other. Moreover, since the curve of ARRN topology potential based on closeness is almost in line with the eigenvector, the two attack strategies yield extremely similar results. It is obvious that random attack has minimal effect on ARRN topology potential.As shown in Figure8(d), the relationship between ARRN topology potential relative entropy and removed nodes is described to show performance of the network robustness. In the beginning, ARRN topology potential relative entropy caused by degree and Bonacich strategies grows faster than others; in addition, the relative entropy value of degree is similar to that of Bonacich. Although the line of ARRN topology potential relative entropy caused by betweenness is lower than that caused by degree and Bonacich, its slope is higher than that of the latter. Therefore, with the increase of removed nodes, the relative entropy caused by betweenness exceeds that of degree and Bonacich. That is, the performance of network robustness varies from different stages. Curves of closeness and eigenvector are slightly higher than those of random strategy, meaning that closeness and eigenvector have slightly greater impact on robustness than random strategy.In short, from Figure8, we know that the proposed theory can reflect the degree and trend of robust change in ARRN well. Furthermore, the result is specific and accurate. So, the proposed theory has objectivity, accuracy, and applicability in studying the ARRN robustness under different attack strategies.


## 5.1. Air Route Reduction Network Model

With the continuous development of the aviation industry, airspace resources are also becoming increasingly tense. As the main carrier of aircrafts, air routes are the important component of airspace. The continuous increase of traffic flow makes the traffic density in the air route network too large, which further highlights the irrationality of the air route network structure. As a result, the pressure on the air route continues to increase, the risk of air route failure increases, and the robustness plays an important role in the operation of the air route. The layout of Chinese air route network is shown in Figure3.Figure 3
The distribution of Chinese air route network.As shown in Figure3, the red dots represent air route waypoints such as airports, navigation points, route intersections, and reporting points. Simultaneously, the air route segments are depicted by the blue solid line and connected by a series of waypoints. In this section, an air route reduction network (ARRN) model is constructed to analyze the robustness of the network. The press of model building is as follows:(a)
An airport and its terminal area are collapsed into one node. Meanwhile, Navigation points, intersections, and important reporting points are reduced to nodes. If there is a route between two nodes, then add an edge.(b)
If there is a waypoint on the route, and it is not a convergence point such as an intersection and an inflection point, the point is fused to other nodes on the principle of proximity, and the original air route segment remains unchanged.(c)
When there are two or more air route segments between two nodes, multiple route segments are condensed to one edge. All of them constitute an undirected network model.Based on the theory mentioned above, the ARRN model is shown in Figure4.Figure 4
Air route reduced network model.In Figure4, red solid dots indicate the nodes that reduced by the waypoints of the air route network, and blue solid lines represent the edges between nodes. A series of nodes and edges are interconnected to form the ARRN model. At the same time, it is known that the distribution of nodes and edges is uneven; namely, the distribution of air routes in the airspace is extremely uneven.On the basis of the analysis of the network structure in Figure4, the basic topology features of the ARRN can be obtained in Table 1.Table 1
Basic topology features of the ARRN.
ParametersNodesEdgesAverage degreeClustering coefficientAverage shortest path lengthMixing coefficientARRN88117623.990.2110.03−0.029Table1 shows some basic network parameters of ARRN. The average degree of the network is about 4, indicating that each node is directly connected with 4 neighbors. The clustering coefficient and the average shortest path length of the network are 0.21 and 10.03, respectively, illustrating that the network has small-world properties to some degree. Mixing coefficient of the network is negative, which means that large-degree nodes are more likely to link the small-degree ones; that is, the network is disassortative.


## 5.2. Attack Strategies

Robustness has important theoretical and practical value for air route networks. Generally, complex networks face two attack strategies: random attack and intentional attack. Random attack is that a node or an edge has failed by being randomly attacked with a certain probability. Intentional attack is that the node or edge is attacked according to certain strategy and fails. Based on complex network theory, intentional attack strategies include degree, betweenness, closeness, eigenvector centrality, and Bonacich centrality.The degree of nodevi is defined as the number of edges connected to this node. Intuitively, the greater the degree of a node, the greater the importance of the node in a certain sense.The betweenness of nodevi is defined as the fraction of shortest paths between node pairs that pass through the node of interest, which reflects the role and influence of the node in the entire network. The betweenness of node vi, denoted by Bvi is [37, 38](13)Bvi=∑s≠i≠t∈Vnstvinst,where nst is the number of shortest paths between nodes vs and vt, and nstvi denotes the number of shortest paths between vs and vt, which pass through node vi.Based on [39, 40], closeness of node vi is defined as the reciprocal of the sum of geodesic distances to all other nodes of V, and it is calculated by the following formula:(14)Ccvi=1∑j=1,j≠idij,where dij is the geodesic distance between vi and vj. The greater the closeness of the node, the greater the centrality of the node, and the more important it is in the network.Dangalchev (2006) modified the definition to a general form, called residual closeness in [41]. Residual closeness is able to reflect the effects of node removal even if this removal does not result in disconnected components, and it is expressed as(15)CRvi=∑j=1,j≠i2−dij.Eigenvector centrality of nodevi, denoted as CEvi is computed by [42, 43](16)CEvi=λmax−1∑j=1Naijej,where λmax is the maximum eigenvalue of the adjacency matrix A and e=e1,e2,…,eNT is the corresponding eigenvector, aij is the connection between node vi and node vj:aij=1 when there is a connection existing, aij=0 otherwise.Bonacich centrality is defined as follows [44]:(17)Cδ,β=δI−βA−lA,where δ is a scaling constant, β reflects the effects of the centrality of its neighbors on a node’s centrality and β<1/λmax, I is an identity matrix, and l is a column vector of ones.According to the above attack strategies, the top-20 nodes of ARRN are obtained as shown in Figures5(a)–5(f) respectively.Figure 5
The top-20 nodes of ARRN ranked by random, degree, betweenness, closeness, eigenvector, and Bonacich metrics, respectively.
(a)(b)(c)(d)(e)(f)Figure5 shows the spatial distribution of top-20 nodes (see solid green dots) ranked by different strategies in ARRN, where Figure 5(a) shows one of the results of the random strategy. It is shown in Figure 5 that most of the top-20 nodes are located in Central-south and Southeast China. From Figures 5(c) and 5(d), we can see that the distributions based on betweenness and closeness are similar; meanwhile, the results of degree and Bonacich are extremely close (see Figures 5(b) and 5(f)). However, the eigenvector is different, and the distribution is extremely concentrated (see Figure 5(e)).


## 5.3. Network Topology Potential

In Section3.2, the key step in getting topology potential is to determine the optimal control parameter αZ. According to the ARRN model, the function curve of topology potential entropy H and control parameter α is obtained, and the result is shown in Figure 6.Figure 6
Topology potential entropyH changes with α.As depicted in Figure6, the topology potential entropy H decreases first and then increases. When α=1.0, H gets the minimum value Hmin. Therefore, the optimal control parameter αZ=1.0.Based on the topology potential theory, the nodes topology potential of the ARRN are achieved in Figure7.Figure 7
The distribution of ARRN nodes topology potential.The topology potential of ARRN nodes is averagely divided inton=7 intervals, and the results are shown in Figure 7. That is, the set of intervals is X=xi|i=1,2,…,7. From the theory in Section 3.2, we can get the distribution law of the random variable x and it is expressed as follows:(18)X0,55,1010,1515,2020,2525,3030,35Probability0.0800.2960.3840.1520.0520.0270.009.From the distribution law, the value range and probability distribution of the network topology potential can be clearly and directly observed. In the next section, the relative entropy of topology potential under different attack strategies will be discussed to analyze the robustness of the ARRN.


## 5.4. Robustness Analysis

In order to analyze the robustness of the ARRN, different attack strategies mentioned in Section4.2 are implemented on the network, and the top-20 nodes in Figure 5 are removed by the order of descending metric values. Then, some robustness measures including network efficiency, giant component, network topology potential, and topology potential relative entropy are applied to measuring performance of the network robustness. The results are shown in Figure 8.Figure 8
Comparison of robustness measures for different attacks on ARRN, and the top-20 nodes are removed by the order of descending metric values.
(a)(b)(c)(d)Figure8 presents the results of six attack strategies to ARRN with four different robustness measures. In Figure 8(a), network efficiency decreases as a function of the number of nodes removed in ARRN for each criterion. With the betweenness strategy, the rate of efficiency reduction is higher than that of others (see Figure 8(a)). Meanwhile, the line of efficiency in closeness is slightly above betweenness. However, degree and Bonacich have similar effects on ARRN efficiency, for their line almost overlaps as shown in Figure 8(a). The impact of attack with eigenvector strategy on ARRN efficiency is less than that of other intentional attacks, but higher than that of random attack.In Figure8(b), the size of ARRN giant component is a function of removed nodes to analyze the robustness of the network. As shown in Figure 8(b), the slope of the line with eigenvector strategy is the largest; thus, the eigenvector criterion has a significant effect on ARRN giant component. The lines of degree and Bonacich almost coincide, so they have similar impact on ARRN giant component. The sizes of ARRN giant component and removed nodes are almost linear when under the betweenness and closeness strategies. Simultaneously, the fluctuation between giant component and removed nodes is great under random attack.The computational ARRN topology potential is compared in Figure8(c) under different attack strategies. From Figure 8(c), we find that lines of degree, betweenness, and Bonacich have similar slopes, illustrating that the effects on ARRN topology potential caused by the three strategies are close to each other. Moreover, since the curve of ARRN topology potential based on closeness is almost in line with the eigenvector, the two attack strategies yield extremely similar results. It is obvious that random attack has minimal effect on ARRN topology potential.As shown in Figure8(d), the relationship between ARRN topology potential relative entropy and removed nodes is described to show performance of the network robustness. In the beginning, ARRN topology potential relative entropy caused by degree and Bonacich strategies grows faster than others; in addition, the relative entropy value of degree is similar to that of Bonacich. Although the line of ARRN topology potential relative entropy caused by betweenness is lower than that caused by degree and Bonacich, its slope is higher than that of the latter. Therefore, with the increase of removed nodes, the relative entropy caused by betweenness exceeds that of degree and Bonacich. That is, the performance of network robustness varies from different stages. Curves of closeness and eigenvector are slightly higher than those of random strategy, meaning that closeness and eigenvector have slightly greater impact on robustness than random strategy.In short, from Figure8, we know that the proposed theory can reflect the degree and trend of robust change in ARRN well. Furthermore, the result is specific and accurate. So, the proposed theory has objectivity, accuracy, and applicability in studying the ARRN robustness under different attack strategies.


## 6. Conclusions

In this paper, a TPRE robustness measure is proposed to analyze the robustness of air route network based on topology potential (TP) and relative entropy (RE) theories. The matrix form of the topology potential is given, which can reduce the complexity of batch calculations. According to Chinese air routes, an air route reduction network (ARRN) model is constructed. Then, attack strategies including random, degree, betweenness, closeness, eigenvector, and Bonacich are implemented on ARRN. At last, robustness measures including network efficiency, giant component, and the proposed one are used to show performance of the ARRN robustness. The robustness is analyzed by different measures, and the results show that the proposed measure is objective, accurate, and effective. In the future, we will continue to optimize the proposed theory, making it more applicative, and explore more good methods to study the network robustness.



---

*Source: 5527423-2021-07-14.xml*