# Vulnerability Evaluation and Improvement Method of Civil Aviation Navigation Network

Authors: Tingyu Gong; Songchen Han; Kunshan Yang
Journal: Complexity
 (2022)

---

## Abstract

Due to events such as natural disasters and navigation equipment failures, enormous calamity may be caused by the interruption of the navigation network which is a guarantee for the flight safety of civil aviation aircraft. The navigation network consists of the navigation stations as nodes and the routes between them as edges. Different nodes have different effects on the vulnerability of the network due to their different abilities to maintain the stability of the network topology and the normal function of the network. To quantify this difference and identify key nodes that have a greater impact on the vulnerability of the navigation network, an indicator to assess the importance of a navigation station is proposed which combines the structural importance reflected by node topology centrality and functional importance reflected by node weight. The structural importance of a node corresponds to its topology features including local dominance of the node and its global influence, and the important contribution to both adjacent and nonadjacent nodes from this node, while the functional importance is indicated by the flight flow serviced by the node during a fixed period of time. Vulnerability evaluation shows that the navigation network is more vulnerable when subject to the intentional attack of nodes with higher comprehensive node importance than an intentional attack of nodes with a larger value of indicators used in previous literature. Finally, the vulnerability of the navigation network is improved through changing the topology of the most critical node and balancing the node importance of the whole network.


---

## Body

## 1. Introduction

The navigation station provides positioning services and heading guidance for the aircraft in the air, which is an important guarantee for the safety of civil aviation flight. With the dramatically increasing number of civil aviation flights, the stable operation of the navigation network formed by the navigation stations and the air routes connecting the navigation stations plays an increasingly significant part in the civil aviation transport system. According to the reports published by the Civil Aviation Administration of China in 2020, the traffic flow of China’s civil aviation has grown to 11.6605 million take-off and landing sorties and 659.9342 million passenger transports in 2019 [1]. Although the traffic flow in 2020 and 2021 is lower than before due to the COVID-19 pandemic, in the long run, China’s civil aviation traffic demand will continue to grow which brings further demand for the support capability of the navigation network [2]. The navigation network always suffers natural hazards and manmade accidents such as earthquake, rainstorm, mudslide, operation error, and other unexpected disasters. Its interruption or failure can result in a seriously negative impact on flight safety which may lead to severe consequences and economic loss. Hence, it is of great significance to investigate the vulnerability of navigation network, and it is crucial to identify key nodes in the network to improve the vulnerability to minimize the risk of disruptive events.In recent years, the vulnerability assessment of the transportation system has received extensive attention from scholars, including airline, highway, railway, subway, and high-speed railway. Klophaus and Lordan [3] measured the vulnerability of the Global airline codesharing network of Star Alliance, SkyTeam, and Oneworld, respectively, by applying a normalized codesharing network vulnerability metric based on the average edge betweenness. Hsieh and Feng [4] examined the resilience of Taiwan highway networks in regard to failures from the perspectives of accessibility and connectivity. Liu et al. [5] analyzed the susceptibility of both existing and planned Chinese railway system subjected to rainfall-induced multihazards quantitatively using a machine learning method and historical disaster events through which the main climatic factors that influence the safety of the railway system are identified. Sun et al. [6] evaluated the vulnerability of the Beijing rail transit network by applying topology indicators such as node degree, betweenness, and strength and analyzed the cascading failures of the weighted network considering loading and redistribution of multistatic passenger flow based on coupled map lattices. While most researches on transportation system mainly concentrate on the vulnerability modeling and analyzing of a single subsystem, Li et al. [7] proposed a method to analyze the vulnerability of public transport system composed of two or more transport subsystems and identified the critical area within the system based on the data of running timetable and position coordinates. The study filled the gap of less considering the simultaneous interruption of subsystems of the previous research studies by investigating the differences of vulnerability and critical areas between individual subsystem and overall system.There are mainly two methods for vulnerability assessment of transportation networks, one is based on network topology features and the other is based on network function features. Sen et al. [8] employed the shortest path length as the metric in vulnerability measure of the conventional railway system of India. Erath et al. [9] described the road network of Swiss as an unweighted network and used the degree centrality and closeness centrality in vulnerability assessment. Ouyang et al. [10] assessed the vulnerability of China’s conventional railway taking the degree of centrality of stations as the network connectivity indicator. These literature studies evaluate the vulnerability of transportation network based on its topology feature which are constructive to the design and planning of network structure.Nevertheless, some other studies consider service feature in the vulnerability analysis of transportation network. Rodríguez-Núñez and García-Palomares [11] applied travel time and train number as the indicators to evaluate the vulnerability of the urban rail network. Cats et al. [12] took the reduction in passenger flow under specified disaster scenarios as the vulnerability metric of the urban rail-bound network. Lu [13] developed a model for the vulnerability assessment of rail network subject to operation accidents by integrating network topology feature and passenger volume feature. Li and Rong [14] investigated the impacts of service feature including passenger flow and travel time on vulnerability analysis of high-speed railway network taking service performance as the evaluation indicator. The network function features such as passenger flow, train number, and travel time are of great worth in optimizing traffic assignment and route choice.These two vulnerability assessment methods have different starting points and have their own advantages. Methods based on topology features are usually helpful to design or improve the network structure in long development while methods based on function features are commonly useful to optimize the network in better operation. With the rapid development of civil aviation in China, neither topological integrity nor functional normal operation is negligible in the vulnerability assessment of navigation networks to ensure the network’s ability to guarantee flight safety.As a preventive mechanism, vulnerability evaluation refers to the adoption of appropriate technical means to ensure the sustainability of key units by identifying key elements in the system and possible sources of danger [15]. At present, few studies are explored on vulnerability evaluation of navigation network, but relevant theories and experiences of other infrastructure networks which have similarities with the navigation network can be used for reference. Some scholars have conducted research on key infrastructure in air traffic management (ATM) support system in order to improve the reliability of ATM support system. Feng et al. [16] used the improved fuzzy Petri net to evaluate and verify the business continuity of aviation security system. Haji [17] reviewed different types of risks associated with airline business evaluation processes and proposed solutions to these risks based on experience and industry practices. From the perspective of the vulnerability evaluation of the aviation equipment support system, Guan [18] evaluated the signal range of navigation, surveillance, communications, and other air traffic control equipment. Bloom et al. [19] discussed the application of business continuity in different areas of commercial aviation, including aircraft rescue, fire protection, and security of airport terminals. Li and Xu [20] proposed a comprehensive evaluation method of airport importance which combines fuzzy soft set theory with complex network theory to identify key airports. Complex network theory is widely used in vulnerability analysis of power systems and is extended to other complex systems [21, 22]. Lordan et al. [23] analyzed the stability of the European civil aviation network via observing network behaviour under random or malicious attacks. Cai et al. [24] found that the Chinese air route network is a geographical network with exponential degree distribution, low clustering coefficient, large shortest path length, and exponential spatial distance distribution. Voltes-Dorta et al. [25] analyzed the vulnerability of European air transportation networks from the perspective of interruption delays and ranked the importance of each airport. Wu et al. [26] analyzed the complex network characteristics of the air traffic control network, based on the route structure covered by navigation, communication, and surveillance equipments.In general, part of the nodes identified as important nodes plays a key role in the structure and function of the network. Finding important nodes and adopting protective strategies may effectively reduce the vulnerability of the network [27]. Importance evaluation methods such as the centrality evaluation method and eigenvector method are commonly used. Centrality measures include degree centrality [28], betweenness centrality [29–31], and residual closeness centrality [32] while eigenvector method includes PageRank algorithm [33] and LeaderRank algorithm [34]. Zuo [35] proposed a method for importance nodes identification of a Ground-based Air Traffic Management Support System based on node betweenness centrality, which only considered intermedium centrality of nodes and ignored the contribution of adjacent nodes and nonadjacent nodes. Zhao et al. [36] proposed a node importance contribution matrix (NICM) method, in which a node contributed its initial importance, characterized by betweenness, to its adjacent nodes evenly with the base of degree. NICM considered the importance contribution from adjacent nodes, but not from nonadjacent nodes and its importance contribution of adjacent nodes is uniformly distributed, which does not match the real situation. Based on the NICM, Hu et al. [37] proposed a node importance contribution correlation matrix (NICCM) method, in which a node contributes importance to its adjacent and next adjacent nodes in light of dependence strength between them. NICCM made up for the lack of consideration of the importance contribution of nonadjacent nodes in NICM and illustrated that the importance contribution of nodes is nonuniform. Feng [38] proposed a node efficiency method which combined the importance matrix to evaluating vulnerability of navigation network and achieved promising results. However, the importance matrix did not cover interdependence between nonadjacent nodes, and only node efficiency was used as a metric in node importance consideration. Node efficiency characterizes the distance centrality of the navigation station to other nodes, which only reflects the global importance of the navigation station in terms of network topology.Based on the above-given literature review, it is obvious that studies on the key nodes identification are generally limited to the perspective of network topology features, ignoring the network function features such as traffic flow. It is indispensable to take traffic flow into account in importance evaluation work so as to applying in practical problems. Li and Rong [39] proposed a metric combining topology location and function influence to evaluate the importance of a node within the network, which is indicated by degree centrality and passenger flow. The indicator shows that a node is more important with more neighbours connected to it directly and more passenger flow through the node. In addition, a few studies applied the function features such as passenger flow, traffic load, and traffic time in characterizing the importance of a component of transportation networks [6, 13, 40]. Although the impacts of function features such as passenger flow on the key nodes identification of other networks have been revealed, investigating indicators for describing node importance of navigation network from both topology and function features perspectives attracts less attention. The aim of this paper is to propose a comprehensive indicator to assess the importance of a navigation station within a navigation network. To explore the vulnerability of the navigation network under intentional attack with our proposed indicator, results are compared with the results obtained by utilizing indicators introduced in previous literature studies. The results show that the navigation network is more vulnerable when subject to an intentional attack of nodes according to our proposed indicator.The rest of this paper is organized as follows: Section2 introduces preliminaries and models used in this research including the vulnerability evaluation model, node importance assessment indicator, and vulnerability improvement method of navigation network. Section 3 conducts a comparative experimental analysis on vulnerability evaluation to verify the effectiveness of the indicator assessing the importance of navigation stations within the navigation network in the case of southwest China and the vulnerability improvement results are analyzed with the same case. Finally, in Section 4, we summarize the viewpoints and contributions of this paper.


## 2. Preliminaries and Models

### 2.1. Navigation Network

The air route network is always described by applying complex network theory where waypoints are taken as nodes and routes are taken as edges. Waypoints are determined by positioning signals from one or more navigation stations and routes are lines connecting these waypoints. Most of the waypoints of the traditional routes are the corresponding air positions directly above the navigation station. Each air route has a direction and the air route network is also a directed network; however, almost all routes are bidirectional with different flight level in each direction. Based on this, the navigation network can be modelled by taking navigation stations as nodes, and connecting an edge between two nodes if the two navigation stations are adjacent on a same route. Even if the two navigation stations are passed by multiple routes in the same or different directions, there is only one edge between them, and the edge weight is the flight flow on this route. The navigation network is a weighted undirected complex network withn nodes and m edges which are expressed as follows:(1)G=V,E,W,where V=v1,v2,…,vn is node set and E=e1,e2,…,em is edge set. W=wijn×n is the matrix formed by the weight of every edge in G in which wij includes both flight flow going from vi to vj and flight flow going from vj to vi. If there’s no edge between vi and vj, wij=0, A is the adjacency matrix.(2)A=0δ12⋯δ1nδ210⋯δ2n⋮⋮⋯⋮δn1δn2⋯0,where elements δij=1 if an edge exists between vi and vj, and δij=0 otherwise. Diagonal elements are all set to 0 to indicate that there is no self-loop in the network.Table1 lists the fundamental metrics and network properties parameters in the navigation network.Table 1
The network metrics of navigation network.
MetricsEquationInterpretationDegree [41]ki=∑j=1,j≠inδijThe degreeki refers to the number of connections with other nodes from node vi, which directly reflects the local importance of navigation station vi in the network.Strength [42]wi=∑j=1nwijThe node strength of the navigation stationwi is the sum of flows of all routes connected to vi, and wij is the sum of flight flow on routes going from vi to vj and vj to vi.Local clustering coefficient [41]CCi=∑j,kw^ijw^ikw^jk/∑j≠kw^ijw^ikWherew^ij=wij/maxk,lwkl is the normalized weight of edge between vi and vjBetweenness [29]BCi=∑1≤j≤k≤nj≠i≠kpjki/pjkWherepjk is the number of shortest paths going from vj to vk, and pjki is the number of shortest paths going from vj to vk which pass through vi.Average shortest path length [28]L=2/nn−1∑1≤i<j≤ndijWheren is the total number of nodes and dij is the shortest path length between vi and vj.Node efficiency [28]Ii=1/n−1∑j=1,j≠in1/dijThe node efficiencyIi reflects the degree of centralization of vi, and is defined as the average of the reciprocal sum of the distances between vi and other nodes in the network. Where dij is the minimum distance between vi and vj.Network efficiency [28, 29]NI=2/nn−1∑1≤i≤j≤n1/dijThe network efficiencyNI reflects the invulnerability of the network and is defined as the average of the reciprocal sum of the distances between each pair of nodes.Maximum connected subset ratio [41]U=n′/nThe maximum connected subset ratio is a measure of the network connectivity vulnerability. Here,n′ and n represent the maximum number of connected nodes and the total number of nodes in the network, respectively.


### 2.2. Vulnerability Evaluation Model

On the basis of previous research studies, in this paper, the vulnerability of a navigation network is defined as the relative loss of network performance under navigation stations failure caused by a natural disaster or manmade accident, which can be constructed as follows [7]:(3)Vul=Pnor−PabnPnor,where Pnor and Pabn correspond to the performance of the navigation network in normal operation and abnormal operation, respectively.The performance of the navigation network is measured in this paper by the topology features reflected by the maximum connected subset and function features reflected by the network accessibility efficiency, which means that the more nodes the connected subset includes and the higher the network accessibility efficiency, the better the performance. The performance of the navigation network is shown as follows:(4)P=U⋅HmaxH,where U is the maximum connected subset ratio that belongs to 0 to 1, and the right part of the equation stands for normalized H by the maximum value. H represents the network accessibility efficiency which is constructed as follows:(5)H=2nn−1∑1≤i≤j≤nhij,where n denotes the number of navigation stations and hij is the accessibility efficiency from node vi to node vj which is calculated as follows:(6)hij=w^ijdij,where dij represents the shortest path length from node vi to node vj, and w^ij is the normalized weight of edge between vi and vj.Thus, the performance of the navigation network in normal operation,Pnor, and the performance in abnormal operation, Pabn, can be calculated by equation (4), and then the vulnerability of the navigation network under the scenario of disturbances or disruptions can be calculated by equation (3).


### 2.3. Node Importance

Although the failure of a navigation station is hard to prevent and predict, its failure effects on the performance of the navigation network can be reduced by increasing the security protection on critical navigation stations in the network. The importance of a navigation station is determined by its topology features such as degree centrality reflecting the connectivity within the network, betweenness centrality describing the transitivity, and closeness centrality indicating the accessibility within the network as well as function features such as flight flow. The topology features of a navigation station are denoted as structural importance which includes local dominance of the node and its global influence, and the importance contribution to both adjacent and nonadjacent nodes from this node, while the function features are denoted as functional importance which is indicated by the flight flow serviced by the node during a fixed period of time. Based on this definition, an indicator for assessing the importance of a navigation station is proposed by combining its topology location and function influence, through which the critical navigation stations are identified as the key nodes in the network.One air route passes through several navigation stations and several air routes pass through one navigation station. When failure or destruction of a navigation station occurs, routes passing through this navigation station are affected. Take nodevi as an example, ki is the degree of vi. If vi fails, all the connections to vi are disconnected. The local importance Di of node vi is defined as the normalized value of node degree ki.(7)Di=kin−1,where n−1 is the maximum possible node degree value in the network.Whenvi fails, traffic flow involving node vi must be redistributed, which may affect the traffic distribution of the entire network. The node efficiency Ii of vi characterizes the average distance from vi to other nodes, and it reflects the global impact of the navigation station in terms of network topology. The betweenness Bi measures the transitivity of vi to other nodes as an intermediary in the network, which reflects the global importance in terms of traffic flow. Thus, the global importance of node vi denoted as Qi is contained by two parts.(8)Qi=IiBi,where Ii and Bi have been normalized to the interval 0 to 1 considering the synergy of the two factors. For a connected network containing n nodes, the maximum possible value of node degree is n−1, and the maximum possible value of node betweenness is the betweenness value of the central node in the star network. Because the shortest paths between all other pairs of nodes are unique and all pass through the central node, the betweenness of the central node is the number of these shortest paths, which is 1/2n−1n−2. Hence the normalized betweenness of node vi is(9)Bi=2n−1n−2∑1≤j≤k≤nj≠i≠kpjkipjk.ForIi, the maximum possible value is also the node efficiency value of the central node in the star network which equals to 1.When a navigation station fails, flight flow passing through it will be assigned to other navigation stations. Generally, the closest navigation stations in distance will be given priority which means neighbour nodes are affected by the reassigned traffic firstly. The transmission efficiency is introduced to describe the affection. In previous research studies, the transmission efficiency between nodevi and vj is defined as the reciprocal distance between them which is shown as follows [43]:(10)cij=1dij.The network transmission efficiency matrix withn navigation stations is donated as C, in which nodes do not handle flights to themselves, so the diagonal elements are set to 0.(11)C=0c12...c1nc210...c2n⋮⋮...⋮cn1cn2...0.When nodevi fails, its adjacent nodes will first share the traffic load of node vi. The more neighbour nodes it has, the faster the load can be distributed, which means the higher the transmission efficiency of the node. We initialize the importance of node vi with its local importance Di.(12)F0=0c12D1...c1nD1c21D20...c2nD2⋮⋮...⋮cn1Dncn2Dn...0.Considering the global importance here, a node with higher global importance may have greater impacts on other nodes in the network. Hence the importance contribution to other nodes can be described as the following matrix after addingQi to C.(13)F1=0c12D1Q1...c1nD1Q1c21D2Q20...c2nD2Q2⋮⋮...⋮cn1DnQncn2DnQn...0.In addition, one situation must be considered when traffic is assigned to other navigation stations. If the assigned traffic exceeds the maximum capacity, further redistribution is triggered. Hence the importance contribution to other nodes from a navigation station node is related to not only the node itself but also other nodes in the network.When a navigation station fails, the traffic flow passing through the node is turned to its neighbour nodes, and the traffic flow of neighbour nodes is spread to the neighbour nodes of neighbour nodes. Nodes with higher global importance are more inclined to share more traffic, that is, the proportion of the contribution value distribution can be determined by the global importance of other nonfailed nodes. Hence multiplying the global importance of other nonfailed nodes can express the importance of contribution values more accurately.F1 is modified as below in combination with the global importance of other navigation stations which is denoted as F2.(14)F2=0c12D1Q1Q2′...c1nD1Q1Qn′c21D2Q2Q1′0...c2nD2Q2Qn′⋮⋮...⋮cn1DnQnQ1′cn2DnQnQ2′...0,where Qj′ is the normalized global importance of node vj in the network without the failed node. Thus, the structural importance of navigation station vi is calculated as follows:(15)Fi=1n−1∑j=1,j≠incijDiQiQj′.The functional importance of navigation stationvi is denoted as the normalized strength of node vi.(16)Si=wimax1≤l≤nwl,where wi is the sum of flight flow on routes going from both vi to other nodes and other nodes to vi.The comprehensive importance of a navigation station is the combination ofFi and Si. In equation (15), the transmission efficiency cij only considers the topological features and cannot describe the flight flow of the route between node vi and vj. Hence, we replace cij with hij which is shown in equation (6) to improve the transmission efficiency metric so as to calculate the node importance by combining topology location and function influence. hij means shorter distance and larger flight flow between two navigation stations correspond to more accessible reach to each other, indicating the higher transmission efficiency. The comprehensive node importance is constructed as follows:(17)Oi=1n−1∑j=1,j≠inhijDiQiQj′.


### 2.4. Vulnerability Improvement

The comprehensive importance of a navigation station comprises its local dominance, global influence, importance contribution to other navigation stations, and the flight flow it handles. The navigation stations corresponding to the larger importance value are the key nodes whose failure can result in the larger loss of the navigation network performance than others. Moreover, when a key node fails, which means a critical navigation station is out of service, then all routes connected directly to it become unavailable which will cause further losses to its neighbour nodes. This can be improved by creating a new node within a certain range near the key node to divert traffic load from the key node as much as possible while directing the traffic to other nodes with functional redundancy among the neighbour nodes of the key node. While the service resources of other noncritical navigation stations are utilized more, the relative importance of key nodes is reduced and the importance of nodes in the network is more balanced. At this time, the loss of network performance caused by the failure of this key node is reduced, and the vulnerability of the network is improved.The main focus of this section is to choose the location of the new navigation station to reduce the relative importance of the key node and balance the importance of navigation stations within the network, thereby to improve the vulnerability of the navigation network. VarianceσO2 of comprehensive importance of all navigation stations is introduced to measure the change of the node importance of the new network after adding a new node compared to the original network. The smaller the variance, the more balanced the node importance of the network, which means the more balanced of the service capability of the navigation stations. Thus, the objective function is formulated as follows:(18)PMi=minσO′2−σO2,σO2=∑i=1nOi−O¯2n,σO′2=∑i=1n+1Oi−O′¯2n+1,where σO2 and σO′2 are the variances of the comprehensive importance of navigation stations Oi before and after the new node is added, respectively. O¯ and O′¯ are the mean value of Oi in the original network and in the new network. If σO′2<σO2, which means the importance of nodes in the new network is more balanced, then σO′2−σO2 is a negative value, and the smaller the value, the greater the contribution of the new node to the node importance balance of the network.In addition, the location of the new node should follow the basic principle of the coverage of the navigation station. The distance between any two navigation stations must be less than the average maximum function range of the navigation station which is expressed as follows:(19)∀vk∈Vj,ljk≤r,where Vj is the set of the neighbour nodes of the new navigation station node vj, and ljk is the geographic distance between node vj and node vk; r is the maximum function range of a navigation station.


## 2.1. Navigation Network

The air route network is always described by applying complex network theory where waypoints are taken as nodes and routes are taken as edges. Waypoints are determined by positioning signals from one or more navigation stations and routes are lines connecting these waypoints. Most of the waypoints of the traditional routes are the corresponding air positions directly above the navigation station. Each air route has a direction and the air route network is also a directed network; however, almost all routes are bidirectional with different flight level in each direction. Based on this, the navigation network can be modelled by taking navigation stations as nodes, and connecting an edge between two nodes if the two navigation stations are adjacent on a same route. Even if the two navigation stations are passed by multiple routes in the same or different directions, there is only one edge between them, and the edge weight is the flight flow on this route. The navigation network is a weighted undirected complex network withn nodes and m edges which are expressed as follows:(1)G=V,E,W,where V=v1,v2,…,vn is node set and E=e1,e2,…,em is edge set. W=wijn×n is the matrix formed by the weight of every edge in G in which wij includes both flight flow going from vi to vj and flight flow going from vj to vi. If there’s no edge between vi and vj, wij=0, A is the adjacency matrix.(2)A=0δ12⋯δ1nδ210⋯δ2n⋮⋮⋯⋮δn1δn2⋯0,where elements δij=1 if an edge exists between vi and vj, and δij=0 otherwise. Diagonal elements are all set to 0 to indicate that there is no self-loop in the network.Table1 lists the fundamental metrics and network properties parameters in the navigation network.Table 1
The network metrics of navigation network.
MetricsEquationInterpretationDegree [41]ki=∑j=1,j≠inδijThe degreeki refers to the number of connections with other nodes from node vi, which directly reflects the local importance of navigation station vi in the network.Strength [42]wi=∑j=1nwijThe node strength of the navigation stationwi is the sum of flows of all routes connected to vi, and wij is the sum of flight flow on routes going from vi to vj and vj to vi.Local clustering coefficient [41]CCi=∑j,kw^ijw^ikw^jk/∑j≠kw^ijw^ikWherew^ij=wij/maxk,lwkl is the normalized weight of edge between vi and vjBetweenness [29]BCi=∑1≤j≤k≤nj≠i≠kpjki/pjkWherepjk is the number of shortest paths going from vj to vk, and pjki is the number of shortest paths going from vj to vk which pass through vi.Average shortest path length [28]L=2/nn−1∑1≤i<j≤ndijWheren is the total number of nodes and dij is the shortest path length between vi and vj.Node efficiency [28]Ii=1/n−1∑j=1,j≠in1/dijThe node efficiencyIi reflects the degree of centralization of vi, and is defined as the average of the reciprocal sum of the distances between vi and other nodes in the network. Where dij is the minimum distance between vi and vj.Network efficiency [28, 29]NI=2/nn−1∑1≤i≤j≤n1/dijThe network efficiencyNI reflects the invulnerability of the network and is defined as the average of the reciprocal sum of the distances between each pair of nodes.Maximum connected subset ratio [41]U=n′/nThe maximum connected subset ratio is a measure of the network connectivity vulnerability. Here,n′ and n represent the maximum number of connected nodes and the total number of nodes in the network, respectively.


## 2.2. Vulnerability Evaluation Model

On the basis of previous research studies, in this paper, the vulnerability of a navigation network is defined as the relative loss of network performance under navigation stations failure caused by a natural disaster or manmade accident, which can be constructed as follows [7]:(3)Vul=Pnor−PabnPnor,where Pnor and Pabn correspond to the performance of the navigation network in normal operation and abnormal operation, respectively.The performance of the navigation network is measured in this paper by the topology features reflected by the maximum connected subset and function features reflected by the network accessibility efficiency, which means that the more nodes the connected subset includes and the higher the network accessibility efficiency, the better the performance. The performance of the navigation network is shown as follows:(4)P=U⋅HmaxH,where U is the maximum connected subset ratio that belongs to 0 to 1, and the right part of the equation stands for normalized H by the maximum value. H represents the network accessibility efficiency which is constructed as follows:(5)H=2nn−1∑1≤i≤j≤nhij,where n denotes the number of navigation stations and hij is the accessibility efficiency from node vi to node vj which is calculated as follows:(6)hij=w^ijdij,where dij represents the shortest path length from node vi to node vj, and w^ij is the normalized weight of edge between vi and vj.Thus, the performance of the navigation network in normal operation,Pnor, and the performance in abnormal operation, Pabn, can be calculated by equation (4), and then the vulnerability of the navigation network under the scenario of disturbances or disruptions can be calculated by equation (3).


## 2.3. Node Importance

Although the failure of a navigation station is hard to prevent and predict, its failure effects on the performance of the navigation network can be reduced by increasing the security protection on critical navigation stations in the network. The importance of a navigation station is determined by its topology features such as degree centrality reflecting the connectivity within the network, betweenness centrality describing the transitivity, and closeness centrality indicating the accessibility within the network as well as function features such as flight flow. The topology features of a navigation station are denoted as structural importance which includes local dominance of the node and its global influence, and the importance contribution to both adjacent and nonadjacent nodes from this node, while the function features are denoted as functional importance which is indicated by the flight flow serviced by the node during a fixed period of time. Based on this definition, an indicator for assessing the importance of a navigation station is proposed by combining its topology location and function influence, through which the critical navigation stations are identified as the key nodes in the network.One air route passes through several navigation stations and several air routes pass through one navigation station. When failure or destruction of a navigation station occurs, routes passing through this navigation station are affected. Take nodevi as an example, ki is the degree of vi. If vi fails, all the connections to vi are disconnected. The local importance Di of node vi is defined as the normalized value of node degree ki.(7)Di=kin−1,where n−1 is the maximum possible node degree value in the network.Whenvi fails, traffic flow involving node vi must be redistributed, which may affect the traffic distribution of the entire network. The node efficiency Ii of vi characterizes the average distance from vi to other nodes, and it reflects the global impact of the navigation station in terms of network topology. The betweenness Bi measures the transitivity of vi to other nodes as an intermediary in the network, which reflects the global importance in terms of traffic flow. Thus, the global importance of node vi denoted as Qi is contained by two parts.(8)Qi=IiBi,where Ii and Bi have been normalized to the interval 0 to 1 considering the synergy of the two factors. For a connected network containing n nodes, the maximum possible value of node degree is n−1, and the maximum possible value of node betweenness is the betweenness value of the central node in the star network. Because the shortest paths between all other pairs of nodes are unique and all pass through the central node, the betweenness of the central node is the number of these shortest paths, which is 1/2n−1n−2. Hence the normalized betweenness of node vi is(9)Bi=2n−1n−2∑1≤j≤k≤nj≠i≠kpjkipjk.ForIi, the maximum possible value is also the node efficiency value of the central node in the star network which equals to 1.When a navigation station fails, flight flow passing through it will be assigned to other navigation stations. Generally, the closest navigation stations in distance will be given priority which means neighbour nodes are affected by the reassigned traffic firstly. The transmission efficiency is introduced to describe the affection. In previous research studies, the transmission efficiency between nodevi and vj is defined as the reciprocal distance between them which is shown as follows [43]:(10)cij=1dij.The network transmission efficiency matrix withn navigation stations is donated as C, in which nodes do not handle flights to themselves, so the diagonal elements are set to 0.(11)C=0c12...c1nc210...c2n⋮⋮...⋮cn1cn2...0.When nodevi fails, its adjacent nodes will first share the traffic load of node vi. The more neighbour nodes it has, the faster the load can be distributed, which means the higher the transmission efficiency of the node. We initialize the importance of node vi with its local importance Di.(12)F0=0c12D1...c1nD1c21D20...c2nD2⋮⋮...⋮cn1Dncn2Dn...0.Considering the global importance here, a node with higher global importance may have greater impacts on other nodes in the network. Hence the importance contribution to other nodes can be described as the following matrix after addingQi to C.(13)F1=0c12D1Q1...c1nD1Q1c21D2Q20...c2nD2Q2⋮⋮...⋮cn1DnQncn2DnQn...0.In addition, one situation must be considered when traffic is assigned to other navigation stations. If the assigned traffic exceeds the maximum capacity, further redistribution is triggered. Hence the importance contribution to other nodes from a navigation station node is related to not only the node itself but also other nodes in the network.When a navigation station fails, the traffic flow passing through the node is turned to its neighbour nodes, and the traffic flow of neighbour nodes is spread to the neighbour nodes of neighbour nodes. Nodes with higher global importance are more inclined to share more traffic, that is, the proportion of the contribution value distribution can be determined by the global importance of other nonfailed nodes. Hence multiplying the global importance of other nonfailed nodes can express the importance of contribution values more accurately.F1 is modified as below in combination with the global importance of other navigation stations which is denoted as F2.(14)F2=0c12D1Q1Q2′...c1nD1Q1Qn′c21D2Q2Q1′0...c2nD2Q2Qn′⋮⋮...⋮cn1DnQnQ1′cn2DnQnQ2′...0,where Qj′ is the normalized global importance of node vj in the network without the failed node. Thus, the structural importance of navigation station vi is calculated as follows:(15)Fi=1n−1∑j=1,j≠incijDiQiQj′.The functional importance of navigation stationvi is denoted as the normalized strength of node vi.(16)Si=wimax1≤l≤nwl,where wi is the sum of flight flow on routes going from both vi to other nodes and other nodes to vi.The comprehensive importance of a navigation station is the combination ofFi and Si. In equation (15), the transmission efficiency cij only considers the topological features and cannot describe the flight flow of the route between node vi and vj. Hence, we replace cij with hij which is shown in equation (6) to improve the transmission efficiency metric so as to calculate the node importance by combining topology location and function influence. hij means shorter distance and larger flight flow between two navigation stations correspond to more accessible reach to each other, indicating the higher transmission efficiency. The comprehensive node importance is constructed as follows:(17)Oi=1n−1∑j=1,j≠inhijDiQiQj′.


## 2.4. Vulnerability Improvement

The comprehensive importance of a navigation station comprises its local dominance, global influence, importance contribution to other navigation stations, and the flight flow it handles. The navigation stations corresponding to the larger importance value are the key nodes whose failure can result in the larger loss of the navigation network performance than others. Moreover, when a key node fails, which means a critical navigation station is out of service, then all routes connected directly to it become unavailable which will cause further losses to its neighbour nodes. This can be improved by creating a new node within a certain range near the key node to divert traffic load from the key node as much as possible while directing the traffic to other nodes with functional redundancy among the neighbour nodes of the key node. While the service resources of other noncritical navigation stations are utilized more, the relative importance of key nodes is reduced and the importance of nodes in the network is more balanced. At this time, the loss of network performance caused by the failure of this key node is reduced, and the vulnerability of the network is improved.The main focus of this section is to choose the location of the new navigation station to reduce the relative importance of the key node and balance the importance of navigation stations within the network, thereby to improve the vulnerability of the navigation network. VarianceσO2 of comprehensive importance of all navigation stations is introduced to measure the change of the node importance of the new network after adding a new node compared to the original network. The smaller the variance, the more balanced the node importance of the network, which means the more balanced of the service capability of the navigation stations. Thus, the objective function is formulated as follows:(18)PMi=minσO′2−σO2,σO2=∑i=1nOi−O¯2n,σO′2=∑i=1n+1Oi−O′¯2n+1,where σO2 and σO′2 are the variances of the comprehensive importance of navigation stations Oi before and after the new node is added, respectively. O¯ and O′¯ are the mean value of Oi in the original network and in the new network. If σO′2<σO2, which means the importance of nodes in the new network is more balanced, then σO′2−σO2 is a negative value, and the smaller the value, the greater the contribution of the new node to the node importance balance of the network.In addition, the location of the new node should follow the basic principle of the coverage of the navigation station. The distance between any two navigation stations must be less than the average maximum function range of the navigation station which is expressed as follows:(19)∀vk∈Vj,ljk≤r,where Vj is the set of the neighbour nodes of the new navigation station node vj, and ljk is the geographic distance between node vj and node vk; r is the maximum function range of a navigation station.


## 3. Comparative Experiment and Results Discussion

In order to verify the effectiveness of the model, we take the navigation network in Southwest China as a case where 56 navigation stations are involved. Figure1 shows the topology of the network in which nodes represent for navigation stations and edges represent for connecting relationships among them. The characteristics of the network are analyzed based on the data from VariFlight MAP.Figure 1
Navigation network in Southwest China. There are 5 provinces in Southwest China, including 56 navigation stations.Table2 shows the average degree of the network is 3.4643, indicating that a node in this region is connected with 3 to 4 other nodes in average. The diameter of the network is 9, representing the longest route in the network passing through 9 navigation stations. The average path length is 4.2344, which shows that it takes an average of 4–5 shifts to reach another node from one node. The weighted clustering coefficient of the network is 0.2729; however, the mean value of the average clustering coefficient of the random network generated by 56 nodes randomly reconnected 50 times is only 0.0536. It shows that the connection between the adjacent nodes of the navigation network is closer than that of the random network.Table 2
Main statistic characteristics of the navigation network.
Number of nodesThe average degreeAverage path lengthNetwork diameterAverage clustering coefficient (actual)Average clustering coefficient (random)563.46434.234490.27290.0536Table3 lists the statistical results of the top 10 nodes ranking in degree value. Figure 1 and Table 3 show that nodes with a larger degree are basically located in the geographic core position in the area which are known as capital cities such as Chengdu, Chongqing, Kunming, and Guiyang. Node 42, node 56, node 5, and node 15 have high strength, handling relatively heavier flight flow. Node 42, node 1, and node 41 have relatively larger betweenness which means these 3 nodes are the intersections of routes with a large number of shortest paths in the network passing through them. From Table 3 we can see although node 1 has a large degree, its strength is low, which is possibly because most flights go through node 3 which is nearby to node 1.Table 3
Features of navigation stations with larger degree.
Top degreeNode numberNavigation stationDegreeStrengthClustering coefficientBetweenness142SGM95200.08330.271921ZW7300.23810.205633WFX72630.33330.1725456KWE73380.09520.181054FJC62870.40.094767MYG6370.33330.0815741XFA61030.06670.208385GAO53500.20.174396JTG51020.50.02561012SB51630.20.1514


### 3.1. Identifying Key Nodes

In the case of the navigation network of Southwest China, several indicators of the importance of navigation stations are calculated separately, namely, local importance, global importance, structural importance, functional importance, and comprehensive importance. A navigation station with high structural importance but low functional importance means it actually has redundancy in service capabilities, resulting in a waste of service resources. In opposite, a navigation station with low structural importance but high functional importance leads to overload operation. The structural importance of the navigation console should match the functional importance to maximize the utilization of service resources. Table4 shows the results of node importance derived from various metrics sorted by a degree in descending order, which are normalized by the maximum value in each set of results.Table 4
Part of node importance results.
Node numberLocal importanceGlobal importanceStructural importanceFunctional importanceComprehensive importance421111110.7777780.9244130.7076210.0666670.4939730.7777780.8771820.6391810.5104760.596279560.7777780.8534560.5534290.6533330.5867340.6666670.8144610.5198820.556190.53198570.6666670.7732990.4376180.080.318412410.6666670.9256460.6080650.2057140.47394850.5555560.8322090.3673880.676190.47032260.5555560.7260610.3418390.203810.295829120.5555560.8568670.4459420.3104760.400786150.5555560.806210.3896780.8019050.527087310.5555560.8836010.4352670.516190.462242………………480.1111110.6605330.0500840.0095240.036564490.1111110.6286320.0388880.0190480.032274500.1111110.6286320.0388880.0095240.0291520.1111110.6064540.0316110.0095240.024249It is obvious that the importance of nodes in the network is different according to different indicators and any indicator of local importance, global importance, structural importance, and functional importance may fail in node importance ranking. Local importance cannot distinguish node importance sequence for node 1, node 3, and node 56 as well as node 4, node 7, and node 41. Global importance and structural importance fail in node importance ranking of node 49 and node 50. Functional importance is short for recognizing the importance node between node 50 and node 52. This means that considering only one or a few of the topology features or only function features leads to important information missing in node importance assessment resulting in an inaccurate ranking of nodes. Comprehensive importance fills the gap by combining topology features and function features in describing node importance and is of great value in key nodes identification within the navigation network. The difference of node importance with different metrics is further shown in Figure2 more intuitively.Figure 2
Node importance results of various measurements which are presented in different colours.The green line represents the functional importance of nodes which is basically at a low level. Most nodes have low values of traffic flow which means there is redundancy in service. Node 1 has high structural importance which is 0.707621, but relatively low functional importance which is 0.066667, implying that node 1 is redundant in capacity. Node 15 and node 26 have high strength which are above 0.6; however, the structural importance are only 0.389678 and 0.213971, respectively. This illustrates that the two nodes are located in an area with high traffic demand and provide services running at full capacity which means these two navigation stations are of great importance in maintaining the normal operation of the navigation network. Function features exert obvious impacts on evaluating the importance of nodes because important nodes such as node 15 and node 26 cannot be found when evaluating only with structure features.Due to the geographical features of China’s civil aviation, traffic demand is high in some areas and low in others which has a great relationship with the development of the city. Generally, it is hard to achieve an even distribution of traffic demand in all regions. However, when the traffic demand in some areas continues to expand, the corresponding aviation support equipment such as the navigation station in the area needs to be added to meet the increased traffic demand.The blue line represents the comprehensive importance of nodes that differs greatly from each other which means the network importance distribution is unbalanced. Node 42 occupies an absolute important position in any indicator evaluation. After normalization according to the importance value of node 42, the comprehensive importance values of other nodes are almost all below 0.6 which means node 42 is the most critical node in the navigation network and the failure of node 42 may result in serious consequences to the entire network.


### 3.2. Vulnerability Evaluation

To evaluate the vulnerability of the navigation network, the failure scenarios should be identified first according to the definition of vulnerability. Despite of many types of disruptive events that affect the normal operation of the navigation network, such as natural disasters, operational accidents, and malicious attacks, the consequences of various disruptive events usually appear as navigation stations failure. Based on this, the failure scenarios can be simulated from the commonality of their consequences which means assuming a specified number of navigation stations fail, a failure scenario is simulated. The random failure (RF) model and malicious attack (MA) model are commonly applied to simulating different categories of disruptive events [7, 10]. The RF model can simulate the random failure of navigation stations that may be caused by natural disasters and operational accidents, such as earthquake, rainstorm, mudslide, and signal failure in which a specified number of navigation stations are randomly selected to fail. The MA model basically simulates the failure scenarios induced by human activities such as terrorist attack and military strike, in which a fraction of important navigation stations is assumed to be failed.The RF model and MA model are used in this study to simulate different failure scenarios, under which the vulnerability of the navigation network is analyzed. In order to verify the effectiveness of our proposed indicator denoting the importance of navigation stations, the results obtained in the MA model taking comprehensive importance as the basis for selection of failed navigation stations are compared with the results obtained by three other methods, namely, Zuo’s method [35], NICCM [37], and Feng’s method [38]. The three methods use different indicators assessing the importance of nodes according to their topology features. Zuo’s method is mainly oriented on node betweenness, while Feng’s method focuses on node efficiency, and NICCM emphasis on the node importance contribution matrix which contains topology features of nodes within the network. Table 5 lists the comparison of the top ten important nodes derived from the three methods and our method.Table 5
Comparison of four different methods in node importance evaluation. Only the TOP TEN node values are listed in the table, accurate to 4 decimal places.
Zuo’s methodFeng’s methodNICCMOur methodNode IdValueNode IdValueNode IdValueNode IdValue31.0000421.0000421.0000421.000010.9954410.7660410.797330.596340.983710.7560560.7102560.586760.9595310.7377310.691140.5320430.9570560.737710.5660150.5271410.950050.6408440.542110.4940420.949830.6344120.4808410.4739440.9065120.556730.468450.4703560.8870440.556750.4552310.4622120.8467260.4481430.4286120.4008As Table5 shows, the results of our method is to a certain degree similar as the three methods from former literature which proves the feasibility and effectiveness of our method. Zuo’s method leads to a small deviation from the other three methods in which node 42 is ranked after node 41. In Feng’s method and NICCM, node 41 is ranked second in importance as the adjacent node of node 42, but in our method, node 41 is obviously less important than node 42, indicating that our method can better filter out key nodes.The vulnerability of navigation network under the random failure of navigation stations and under the failure of navigation stations due to malicious attack, are analyzed, respectively. To further investigate the variations in the vulnerability of the navigation network under the failure scenario based on the MA model, the important navigation stations are selected according to different measures of their importance as shown in Table5. Figure 3 reveals that the vulnerability of the navigation network is different under different failure scenarios; however, the network is more vulnerable under the failure scenario based on MA regardless of which node importance measurement indicator is used than that under RF. In a comparison of the results of the four MA failure scenarios, maliciously attacking navigation stations with a large comprehensive importance always causes more loss to the performance of the navigation network than attacking navigation stations with the three other indicators of node importance. This shows that the comprehensive importance indicator can identify the key navigation stations in the navigation network, and attacking these navigation stations will cause great losses to the performance of the network. In other words, the failure of the key navigation stations has greater impacts on the vulnerability of the navigation network than other navigation stations.Figure 3
Vulnerability of navigation network under the failure scenarios of navigation stations with RF and MA in four methods, including Zuo’s method, NICCM, Feng’s method, and our method.In order to further understand what happened to the structure and function of the navigation network subject to different failure scenarios of navigation stations, the change of the maximum connected subgraph of the navigation network and the network accessibility efficiency under the failure of different numbers of navigation stations are investigated, and the results are shown in Figure4. Obviously, with the increase of the number of failed navigation stations, the size of the largest connected subset of the navigation network is getting smaller and smaller, which means that the structural connectivity of the network is affected, and simultaneously the network accessibility efficiency is also reduced, indicating that the functional integrity of the network is damaged. Under malicious attack with a large comprehensive importance of navigation station proposed in our method, the network accessibility efficiency almost drops to 0 after 35 navigation stations failed, and simultaneously the maximum connected subset size is reduced to nearly the minimum which means the entire navigation network is down. The impact to the topology structure and function of the navigation network is reflected in the loss of network performance, that is, the vulnerability of the network.Figure 4
Network topology and function changes under different failure scenarios of navigation stations: (a) Maximum connected subset. (b) Network accessibility efficiency.
(a)(b)


### 3.3. Network Vulnerability Improvement

The comprehensive importance of each navigation station in the case of the navigation network of Southwest China is obtained from which node 42 is found to be the most critical node in the network. The comprehensive importance of node 42 is much higher than that of other nodes which means node 42 is the key node in the navigation network. Once node 42 fails, which means the 42nd navigation station is out of service, all routes directly connected to node 42 become unavailable which will cause further losses to its neighbour nodes. The neighbour nodes which share the load from node 42 may possibly be overloaded because of the heavy load of node 42. Therefore, creating a new node to offload the load of node 42 and reduce the operating pressure of node 42 will improve the performance of the area around node 42 and even the entire network. The new node needs to divert traffic from the key node as much as possible while directing the traffic to other nodes with functional redundancy among the neighbour nodes of node 42. The neighbour nodes of the key node in the navigation network are node 39, node 40, node 41, node 44, node 10, node 45, node 46, node 47, and node 48 among which node 39, node 40, node 44, node 10, node 47, and node 48 have greater functional redundancy according to the results shown in Table 4. Figure 1 reveals that the density of navigation stations is high in the north side of node 42 and low in the south side, while the redundancy of the south side nodes is relatively high. Therefore, a preliminary judgment is made that the location of the new node should be within a certain distance to the south side of node 42.The effective range of the en-route navigation station increases with flight altitude to maximum of 200 nautical miles (370 km), and in the terminal area, it is generally 25 nautical miles (46 km). Considering the density of the navigation stations and the guarantee of overlapping coverage, an area with node 42 as the center and a radius of 200 km extending outward is selected as the location candidate area for the newly added navigation station. The interval between candidate positions should be as small as possible if only they can be distinguished from each other. Thus, the interval is set to 50 km and the distribution of candidate node positions is shown in Figure5 in which each blue dot represents a candidate position of the new navigation station.Figure 5
Distributions of candidate positions of the new navigation station. The center point is node 42 in the original network. (a) Vertical and horizontal arrangement. (b) Staggered arrangement.
(a)(b)Figure5(a) reveals that the interspace between two adjacent circles is relatively large which is marked in yellow in the figure. If we stagger two adjacent rows of circles by 0.5 units, the interspace will shrink a lot as shown in Figure 5(b). Choosing candidate node positions according to the distribution shown in Figure 5(b) can reduce the interval between adjacent candidate positions overall and get a better chance to choose the best position. In the distribution shown in Figure 5(b), an offset of 0.5 units from one position is exactly equivalent to a counter clockwise rotation of 60 degrees around the adjacent position. Therefore, a regular hexagon grid is taken to rearrange the distribution of candidate positions of the new node, and Figure 5 is reproduced by replacing the circles with squares and hexagons respectively as shown in Figure 6. From the staggered distribution shown in Figure 6(b), 60 positions are primarily selected as the candidate positions of the new navigation station.Figure 6
Distributions of candidate positions of the new navigation station. The circles are replaced by squares and hexagons, respectively. (a) Square. (b) Hexagon.
(a)(b)The new network is generated by the following two steps.Firstly, select one of the candidate positions shown in Figure6(b) as the position of the new node.Secondly, connect the new node and the existing nodes by establishing edges between them. The new edges represent the routes connected to the new navigation station, and the new routes should avoid crossing the existing routes as much as possible.Adding new node and associated edges at each candidate position can generate a new network for each candidate position. The best position of the new navigation station is obtained by comparing the node comprehensive importance variance of every new network with the original network. Part of the variance calculation results are shown in Table6.Table 6
Part of the results of node comprehensive importance variance. Position 0 represents the original network.
Candidate positionVarianceReduction00.032796010.0767187740.04392320.0768803170.04408430.0780350190.04523940.0704626780.03766750.0830220330.050226………340.0351924410.002396350.019069493−0.01373360.0616078810.028812370.045067280.012271380.02703616−0.00576390.01812485−0.01467400.022010876−0.01079410.023000971−0.0098420.02254633−0.01025430.0364705480.003675………580.0638815530.031085590.0655733360.032777600.0663326780.033536The addition of a navigation station at candidate position 39 reduces the variance of the comprehensive importance of the navigation station the most in the network. It is found in Table6 that some variance increments are positive indicating that when a new navigation station is added at these positions, the node comprehensive importance variance does not decrease but increases. Most of these positions are located to the north of node 42 where the density of navigation stations in this area is already relatively high. Adding more navigation stations in these positions will bring more traffic flow to the navigation stations in the area, and the node comprehensive importance distribution is further unbalanced. The results of the comprehensive importance of navigation stations after adding a new navigation station at position 39 in the new network are revealed in Figure 7.Figure 7
Comparison of normalized node importance before and after adding new node.The normalized comprehensive importance of node 42 still equals 1, indicating that node 42 is still the most critical node in the network; however, the gap between node 42 and the second-ranked node 3 is significantly reduced which means the importance of node 42 decreases after the addition of node 57 at candidate position 39. Due to the addition of node 57, the traffic flow passing node 42 and node 41 are both dispersed, and the comprehensive importance of node 42 and node 41 are reduced correspondingly. And, the importance gap of each node in the whole network is narrowed which means the importance of nodes in the entire network is more balanced.The vulnerability of the new navigation network after adding a new navigation station is evaluated under the failure scenario of maliciously attacking the navigation stations with high comprehensive importance. Figure8 reveals that the failure of the most critical navigation station in the original navigation network can result in a 14.9% loss of the navigation network performance, while its failure results in a 9.5% loss of navigation network performance in the new navigation network, meaning the failure of the most critical navigation station has a 5.4% decrease in the impact on the network vulnerability. In the original network, when the top three nodes ranking by comprehensive importance in the network fail, the performance of the network drops by 60.3%, while in the new network, the failure of the top three nodes can only cause the performance of the network drop by 26.5% and when the node ranked 4th in comprehensive importance also fails at the same time, the network performance drops by 59.8%. This indicates that the newly added node 57 balances the importance of the top three nodes and node 57 becomes a relative important node in the navigation network. The navigation network is vulnerable subject to malicious attack based on the comprehensive importance of the navigation station and adding a new navigation station at a certain position can effectively balance the importance of the critical navigation stations and improve the vulnerability of the navigation network.Figure 8
Vulnerability comparison of the original navigation network and the improved network under the malicious attack based on the comprehensive importance of navigation stations.The change of the maximum connected subgraph of the navigation network and the network accessibility efficiency under the malicious attack based on the comprehensive importance of navigation stations are investigated in the original network and the new network, respectively. The results are shown in Figure9.Figure 9
Network topology and function changes under malicious attack based on comprehensive importance of navigation stations: (a) Network accessibility efficiency. (b) Maximum connected subset.
(a)(b)As can be seen from Figure9(a), after adding node 57, the network accessibility efficiency has been improved to a certain extent. With the increasing numbers of navigation stations subject to a deliberate attack, the network accessibility efficiency of the new network decreases at a relatively slower rate than that of the original network. In the original network, the network accessibility efficiency dropped to 0 meaning the entire network has collapsed when 35 navigation stations are attacked maliciously to fail, while the number of failed navigation stations that caused the network to collapse is 37 in the new network. The change of the maximum connected subset of the network is similar as the network accessibility efficiency as is shown in Figure 9(b). The slope of the descending curve of the maximum connected subset size of the new network is smaller than that of the original network. The maximum connected subset size of the original network drops to the minimum in the MA scenario that 41 navigation stations are attacked to fail, while the number is the 43 in the new network. It is proved that the new network is less vulnerable after adding a new navigation station compared to the original network. The structure of the new navigation network is shown in Figure 10.Figure 10
The new network construction.


## 3.1. Identifying Key Nodes

In the case of the navigation network of Southwest China, several indicators of the importance of navigation stations are calculated separately, namely, local importance, global importance, structural importance, functional importance, and comprehensive importance. A navigation station with high structural importance but low functional importance means it actually has redundancy in service capabilities, resulting in a waste of service resources. In opposite, a navigation station with low structural importance but high functional importance leads to overload operation. The structural importance of the navigation console should match the functional importance to maximize the utilization of service resources. Table4 shows the results of node importance derived from various metrics sorted by a degree in descending order, which are normalized by the maximum value in each set of results.Table 4
Part of node importance results.
Node numberLocal importanceGlobal importanceStructural importanceFunctional importanceComprehensive importance421111110.7777780.9244130.7076210.0666670.4939730.7777780.8771820.6391810.5104760.596279560.7777780.8534560.5534290.6533330.5867340.6666670.8144610.5198820.556190.53198570.6666670.7732990.4376180.080.318412410.6666670.9256460.6080650.2057140.47394850.5555560.8322090.3673880.676190.47032260.5555560.7260610.3418390.203810.295829120.5555560.8568670.4459420.3104760.400786150.5555560.806210.3896780.8019050.527087310.5555560.8836010.4352670.516190.462242………………480.1111110.6605330.0500840.0095240.036564490.1111110.6286320.0388880.0190480.032274500.1111110.6286320.0388880.0095240.0291520.1111110.6064540.0316110.0095240.024249It is obvious that the importance of nodes in the network is different according to different indicators and any indicator of local importance, global importance, structural importance, and functional importance may fail in node importance ranking. Local importance cannot distinguish node importance sequence for node 1, node 3, and node 56 as well as node 4, node 7, and node 41. Global importance and structural importance fail in node importance ranking of node 49 and node 50. Functional importance is short for recognizing the importance node between node 50 and node 52. This means that considering only one or a few of the topology features or only function features leads to important information missing in node importance assessment resulting in an inaccurate ranking of nodes. Comprehensive importance fills the gap by combining topology features and function features in describing node importance and is of great value in key nodes identification within the navigation network. The difference of node importance with different metrics is further shown in Figure2 more intuitively.Figure 2
Node importance results of various measurements which are presented in different colours.The green line represents the functional importance of nodes which is basically at a low level. Most nodes have low values of traffic flow which means there is redundancy in service. Node 1 has high structural importance which is 0.707621, but relatively low functional importance which is 0.066667, implying that node 1 is redundant in capacity. Node 15 and node 26 have high strength which are above 0.6; however, the structural importance are only 0.389678 and 0.213971, respectively. This illustrates that the two nodes are located in an area with high traffic demand and provide services running at full capacity which means these two navigation stations are of great importance in maintaining the normal operation of the navigation network. Function features exert obvious impacts on evaluating the importance of nodes because important nodes such as node 15 and node 26 cannot be found when evaluating only with structure features.Due to the geographical features of China’s civil aviation, traffic demand is high in some areas and low in others which has a great relationship with the development of the city. Generally, it is hard to achieve an even distribution of traffic demand in all regions. However, when the traffic demand in some areas continues to expand, the corresponding aviation support equipment such as the navigation station in the area needs to be added to meet the increased traffic demand.The blue line represents the comprehensive importance of nodes that differs greatly from each other which means the network importance distribution is unbalanced. Node 42 occupies an absolute important position in any indicator evaluation. After normalization according to the importance value of node 42, the comprehensive importance values of other nodes are almost all below 0.6 which means node 42 is the most critical node in the navigation network and the failure of node 42 may result in serious consequences to the entire network.


## 3.2. Vulnerability Evaluation

To evaluate the vulnerability of the navigation network, the failure scenarios should be identified first according to the definition of vulnerability. Despite of many types of disruptive events that affect the normal operation of the navigation network, such as natural disasters, operational accidents, and malicious attacks, the consequences of various disruptive events usually appear as navigation stations failure. Based on this, the failure scenarios can be simulated from the commonality of their consequences which means assuming a specified number of navigation stations fail, a failure scenario is simulated. The random failure (RF) model and malicious attack (MA) model are commonly applied to simulating different categories of disruptive events [7, 10]. The RF model can simulate the random failure of navigation stations that may be caused by natural disasters and operational accidents, such as earthquake, rainstorm, mudslide, and signal failure in which a specified number of navigation stations are randomly selected to fail. The MA model basically simulates the failure scenarios induced by human activities such as terrorist attack and military strike, in which a fraction of important navigation stations is assumed to be failed.The RF model and MA model are used in this study to simulate different failure scenarios, under which the vulnerability of the navigation network is analyzed. In order to verify the effectiveness of our proposed indicator denoting the importance of navigation stations, the results obtained in the MA model taking comprehensive importance as the basis for selection of failed navigation stations are compared with the results obtained by three other methods, namely, Zuo’s method [35], NICCM [37], and Feng’s method [38]. The three methods use different indicators assessing the importance of nodes according to their topology features. Zuo’s method is mainly oriented on node betweenness, while Feng’s method focuses on node efficiency, and NICCM emphasis on the node importance contribution matrix which contains topology features of nodes within the network. Table 5 lists the comparison of the top ten important nodes derived from the three methods and our method.Table 5
Comparison of four different methods in node importance evaluation. Only the TOP TEN node values are listed in the table, accurate to 4 decimal places.
Zuo’s methodFeng’s methodNICCMOur methodNode IdValueNode IdValueNode IdValueNode IdValue31.0000421.0000421.0000421.000010.9954410.7660410.797330.596340.983710.7560560.7102560.586760.9595310.7377310.691140.5320430.9570560.737710.5660150.5271410.950050.6408440.542110.4940420.949830.6344120.4808410.4739440.9065120.556730.468450.4703560.8870440.556750.4552310.4622120.8467260.4481430.4286120.4008As Table5 shows, the results of our method is to a certain degree similar as the three methods from former literature which proves the feasibility and effectiveness of our method. Zuo’s method leads to a small deviation from the other three methods in which node 42 is ranked after node 41. In Feng’s method and NICCM, node 41 is ranked second in importance as the adjacent node of node 42, but in our method, node 41 is obviously less important than node 42, indicating that our method can better filter out key nodes.The vulnerability of navigation network under the random failure of navigation stations and under the failure of navigation stations due to malicious attack, are analyzed, respectively. To further investigate the variations in the vulnerability of the navigation network under the failure scenario based on the MA model, the important navigation stations are selected according to different measures of their importance as shown in Table5. Figure 3 reveals that the vulnerability of the navigation network is different under different failure scenarios; however, the network is more vulnerable under the failure scenario based on MA regardless of which node importance measurement indicator is used than that under RF. In a comparison of the results of the four MA failure scenarios, maliciously attacking navigation stations with a large comprehensive importance always causes more loss to the performance of the navigation network than attacking navigation stations with the three other indicators of node importance. This shows that the comprehensive importance indicator can identify the key navigation stations in the navigation network, and attacking these navigation stations will cause great losses to the performance of the network. In other words, the failure of the key navigation stations has greater impacts on the vulnerability of the navigation network than other navigation stations.Figure 3
Vulnerability of navigation network under the failure scenarios of navigation stations with RF and MA in four methods, including Zuo’s method, NICCM, Feng’s method, and our method.In order to further understand what happened to the structure and function of the navigation network subject to different failure scenarios of navigation stations, the change of the maximum connected subgraph of the navigation network and the network accessibility efficiency under the failure of different numbers of navigation stations are investigated, and the results are shown in Figure4. Obviously, with the increase of the number of failed navigation stations, the size of the largest connected subset of the navigation network is getting smaller and smaller, which means that the structural connectivity of the network is affected, and simultaneously the network accessibility efficiency is also reduced, indicating that the functional integrity of the network is damaged. Under malicious attack with a large comprehensive importance of navigation station proposed in our method, the network accessibility efficiency almost drops to 0 after 35 navigation stations failed, and simultaneously the maximum connected subset size is reduced to nearly the minimum which means the entire navigation network is down. The impact to the topology structure and function of the navigation network is reflected in the loss of network performance, that is, the vulnerability of the network.Figure 4
Network topology and function changes under different failure scenarios of navigation stations: (a) Maximum connected subset. (b) Network accessibility efficiency.
(a)(b)


## 3.3. Network Vulnerability Improvement

The comprehensive importance of each navigation station in the case of the navigation network of Southwest China is obtained from which node 42 is found to be the most critical node in the network. The comprehensive importance of node 42 is much higher than that of other nodes which means node 42 is the key node in the navigation network. Once node 42 fails, which means the 42nd navigation station is out of service, all routes directly connected to node 42 become unavailable which will cause further losses to its neighbour nodes. The neighbour nodes which share the load from node 42 may possibly be overloaded because of the heavy load of node 42. Therefore, creating a new node to offload the load of node 42 and reduce the operating pressure of node 42 will improve the performance of the area around node 42 and even the entire network. The new node needs to divert traffic from the key node as much as possible while directing the traffic to other nodes with functional redundancy among the neighbour nodes of node 42. The neighbour nodes of the key node in the navigation network are node 39, node 40, node 41, node 44, node 10, node 45, node 46, node 47, and node 48 among which node 39, node 40, node 44, node 10, node 47, and node 48 have greater functional redundancy according to the results shown in Table 4. Figure 1 reveals that the density of navigation stations is high in the north side of node 42 and low in the south side, while the redundancy of the south side nodes is relatively high. Therefore, a preliminary judgment is made that the location of the new node should be within a certain distance to the south side of node 42.The effective range of the en-route navigation station increases with flight altitude to maximum of 200 nautical miles (370 km), and in the terminal area, it is generally 25 nautical miles (46 km). Considering the density of the navigation stations and the guarantee of overlapping coverage, an area with node 42 as the center and a radius of 200 km extending outward is selected as the location candidate area for the newly added navigation station. The interval between candidate positions should be as small as possible if only they can be distinguished from each other. Thus, the interval is set to 50 km and the distribution of candidate node positions is shown in Figure5 in which each blue dot represents a candidate position of the new navigation station.Figure 5
Distributions of candidate positions of the new navigation station. The center point is node 42 in the original network. (a) Vertical and horizontal arrangement. (b) Staggered arrangement.
(a)(b)Figure5(a) reveals that the interspace between two adjacent circles is relatively large which is marked in yellow in the figure. If we stagger two adjacent rows of circles by 0.5 units, the interspace will shrink a lot as shown in Figure 5(b). Choosing candidate node positions according to the distribution shown in Figure 5(b) can reduce the interval between adjacent candidate positions overall and get a better chance to choose the best position. In the distribution shown in Figure 5(b), an offset of 0.5 units from one position is exactly equivalent to a counter clockwise rotation of 60 degrees around the adjacent position. Therefore, a regular hexagon grid is taken to rearrange the distribution of candidate positions of the new node, and Figure 5 is reproduced by replacing the circles with squares and hexagons respectively as shown in Figure 6. From the staggered distribution shown in Figure 6(b), 60 positions are primarily selected as the candidate positions of the new navigation station.Figure 6
Distributions of candidate positions of the new navigation station. The circles are replaced by squares and hexagons, respectively. (a) Square. (b) Hexagon.
(a)(b)The new network is generated by the following two steps.Firstly, select one of the candidate positions shown in Figure6(b) as the position of the new node.Secondly, connect the new node and the existing nodes by establishing edges between them. The new edges represent the routes connected to the new navigation station, and the new routes should avoid crossing the existing routes as much as possible.Adding new node and associated edges at each candidate position can generate a new network for each candidate position. The best position of the new navigation station is obtained by comparing the node comprehensive importance variance of every new network with the original network. Part of the variance calculation results are shown in Table6.Table 6
Part of the results of node comprehensive importance variance. Position 0 represents the original network.
Candidate positionVarianceReduction00.032796010.0767187740.04392320.0768803170.04408430.0780350190.04523940.0704626780.03766750.0830220330.050226………340.0351924410.002396350.019069493−0.01373360.0616078810.028812370.045067280.012271380.02703616−0.00576390.01812485−0.01467400.022010876−0.01079410.023000971−0.0098420.02254633−0.01025430.0364705480.003675………580.0638815530.031085590.0655733360.032777600.0663326780.033536The addition of a navigation station at candidate position 39 reduces the variance of the comprehensive importance of the navigation station the most in the network. It is found in Table6 that some variance increments are positive indicating that when a new navigation station is added at these positions, the node comprehensive importance variance does not decrease but increases. Most of these positions are located to the north of node 42 where the density of navigation stations in this area is already relatively high. Adding more navigation stations in these positions will bring more traffic flow to the navigation stations in the area, and the node comprehensive importance distribution is further unbalanced. The results of the comprehensive importance of navigation stations after adding a new navigation station at position 39 in the new network are revealed in Figure 7.Figure 7
Comparison of normalized node importance before and after adding new node.The normalized comprehensive importance of node 42 still equals 1, indicating that node 42 is still the most critical node in the network; however, the gap between node 42 and the second-ranked node 3 is significantly reduced which means the importance of node 42 decreases after the addition of node 57 at candidate position 39. Due to the addition of node 57, the traffic flow passing node 42 and node 41 are both dispersed, and the comprehensive importance of node 42 and node 41 are reduced correspondingly. And, the importance gap of each node in the whole network is narrowed which means the importance of nodes in the entire network is more balanced.The vulnerability of the new navigation network after adding a new navigation station is evaluated under the failure scenario of maliciously attacking the navigation stations with high comprehensive importance. Figure8 reveals that the failure of the most critical navigation station in the original navigation network can result in a 14.9% loss of the navigation network performance, while its failure results in a 9.5% loss of navigation network performance in the new navigation network, meaning the failure of the most critical navigation station has a 5.4% decrease in the impact on the network vulnerability. In the original network, when the top three nodes ranking by comprehensive importance in the network fail, the performance of the network drops by 60.3%, while in the new network, the failure of the top three nodes can only cause the performance of the network drop by 26.5% and when the node ranked 4th in comprehensive importance also fails at the same time, the network performance drops by 59.8%. This indicates that the newly added node 57 balances the importance of the top three nodes and node 57 becomes a relative important node in the navigation network. The navigation network is vulnerable subject to malicious attack based on the comprehensive importance of the navigation station and adding a new navigation station at a certain position can effectively balance the importance of the critical navigation stations and improve the vulnerability of the navigation network.Figure 8
Vulnerability comparison of the original navigation network and the improved network under the malicious attack based on the comprehensive importance of navigation stations.The change of the maximum connected subgraph of the navigation network and the network accessibility efficiency under the malicious attack based on the comprehensive importance of navigation stations are investigated in the original network and the new network, respectively. The results are shown in Figure9.Figure 9
Network topology and function changes under malicious attack based on comprehensive importance of navigation stations: (a) Network accessibility efficiency. (b) Maximum connected subset.
(a)(b)As can be seen from Figure9(a), after adding node 57, the network accessibility efficiency has been improved to a certain extent. With the increasing numbers of navigation stations subject to a deliberate attack, the network accessibility efficiency of the new network decreases at a relatively slower rate than that of the original network. In the original network, the network accessibility efficiency dropped to 0 meaning the entire network has collapsed when 35 navigation stations are attacked maliciously to fail, while the number of failed navigation stations that caused the network to collapse is 37 in the new network. The change of the maximum connected subset of the network is similar as the network accessibility efficiency as is shown in Figure 9(b). The slope of the descending curve of the maximum connected subset size of the new network is smaller than that of the original network. The maximum connected subset size of the original network drops to the minimum in the MA scenario that 41 navigation stations are attacked to fail, while the number is the 43 in the new network. It is proved that the new network is less vulnerable after adding a new navigation station compared to the original network. The structure of the new navigation network is shown in Figure 10.Figure 10
The new network construction.


## 4. Conclusions

In this research, a navigation network based on complex network theory is constructed, and a vulnerability evaluation and improvement method for the navigation network is proposed. Then, a novel indicator combining the function features with topology features is developed to assess the importance of navigation stations. Afterwards, the vulnerability of the navigation network is evaluated under different failure scenarios taking the navigation network of Southwest China as a case, and the maximum connected subset and network accessibility efficiency are analyzed further. At last, a new navigation network is obtained by adding a new navigation station balancing the importance of the navigation stations in the original network to improve the vulnerability of the navigation network.The main contributions of this paper are as follows:(1)
A novel indicator denoted as comprehensive importance to assess the importance of navigation stations in the navigation network is developed. Topology features such as degree centrality, betweenness centrality, and node efficiency, and function features such as flight flow are taken into account. The transmission efficiency metric is improved by combining flight flow to the shortest path length between two navigation stations to calculate the importance of the navigation station structurally and functionally. In comparison with the indicators in the previous literature studies, the importance of the navigation stations can be described more precisely by the comprehensive importance and through which the critical navigation stations are identified more reasonable.(2)
The results of vulnerability evaluation of the navigation network under various failure scenarios indicate that maliciously attacking navigation stations with high comprehensive importance can cause a larger loss of network performance than that with other metrics. Based on which a method for improving the vulnerability of the navigation network is proposed by adding a new navigation station to scatter the importance of critical navigation stations in the network. An innovative strategy of grid candidate positions is adopted in new node location selection, and it is mathematically more precise to determine the best position compared with the previous methods of only selecting a few approximate candidate positions in different directions.The results obtained may provide reference to the administrators of the navigation equipment support department in the planning and site selection of the navigation station. And, the manager may allocate more maintenance resources to the critical navigation stations in the navigation network according to the comprehensive importance of navigation stations to ensure flight safety in civil aviation operation.



---

*Source: 4032957-2022-07-11.xml*