Identifying vital edges in Chinese air route network via memetic algorithm

Du Wenbo,Liang Boyuan,Yan Gang,Oriol Loran,Cao Xianbin,*

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

bBeijing Key Laboratory for Network-based Cooperative Air Traffic Management,Beijing 100191,China

cSchool of Physics Science and Engineering,Tongji University,Shanghai 200092,China

dUniversitat Polite`cnica de Catalunya-BarcelonaTech,C/Colom no.11,Terrassa 08222,Spain

Identifying vital edges in Chinese air route network via memetic algorithm

Du Wenboa,b,Liang Boyuana,b,Yan Gangc,Oriol Lordand,Cao Xianbina,b,*

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

bBeijing Key Laboratory for Network-based Cooperative Air Traffic Management,Beijing 100191,China

cSchool of Physics Science and Engineering,Tongji University,Shanghai 200092,China

dUniversitat Polite`cnica de Catalunya-BarcelonaTech,C/Colom no.11,Terrassa 08222,Spain

Air route network;Air transport network;Memetic algorithm;Robustness;Vital edges

Due to rapid development in the past decade,air transportation system has attracted considerable research attention from diverse communities.While most of the previous studies focused on airline networks,here we systematically explore the robustness of the Chinese air route network,and identify the vital edges which form the backbone of Chinese air transportation system.Specifically,we employ a memetic algorithm to minimize the network robustness after removing certain edges,and hence the solution of this model is the set of vital edges.Counterintuitively,our results show that the most vital edges are not necessarily the edges of the highest topological importance,for which we provide an extensive explanation from the microscope view.Our findings also offer new insights to understanding and optimizing other real-world network systems.

1.Introduction

With the increasing people and goods transport demand during the accelerating globalization process,the air transportation system plays a more important role than ever before due to its high-speed and high-security advantages.For example,the air transport volume of China grows at an average annual speed of over 10%in the past decades,and now it possesses over one seventh of the total comprehensive transport volume(including roadways,railways,shipping and air transport),which was only 7.9%in 2000.Hence the air transportation system has been drawing much attention from different research communities.Oneofthe mostinteresting directions is to analyze the structure and function of air transportation systems within the framework of complex network theory.

The air transportation system can be represented as a network,in which nodes denote airport and an edge will be created if there is a direct flight between two airports.In the vast majority of previous literature,the air transport network(ATN)was primarily classified into two scales:worldwide and national.

For the worldwide scale,Amaral et al.firstly found that worldwide ATN is a small-world network with a power-lawdegree distribution,and the highest-degree airport is not necessarily the most central node,prompting them to propose a network model where both geographical and political factors are taken into account.1,2Barrat et al.investigated the worldwide ATN from a perspective of complex weighted networks and found the nonlinear positive correlation between flight flow and topology properties.3,4They proposed a weighted network model,enlightening the understanding of weighted feature of complex systems.Verma et al.decomposed the worldwide ATN into three distinct layers via k-core decomposition and found that this network is robust to the removal of long distance edges,but fragile to the disconnectivity of short and apparently insignificant edges.5,6

For the national scale,ATNs of several major nations,such as US,Brazil,India and China,are extensively studied3,7–11,and the national ATNs usually exhibit different features from the worldwide ATN.Gautreau et al.studied US ATN during 1990–2000.3A remarkable result they presented is that although most statistical properties are stationary,an intense activity takes place at the local level.Fleurquin et al.proposed a delay propagation model via quantifying the network congestion for US ATN,revealing that even under normal operating condition the systemic instability risk is non-negligible.11Rocha investigated the Brazilian ATN during 1995–2006,and found that it shrank in topology but grew in traffic volume.7Bagler studied the Indian ATN,and found its signature of hierarchy feature.12As the most active economy,the Chinese aviation industry ranks second to US in the past decade and keeps a high increase rate.Consequently,Chinese ATN attracts continuous attention in different aspects from topology to dynamics and evolution,8–10,13,14one of which is to investigate the backbone of ATN,the air route network(ARN).

ATN is actually a logic network with origin-destination(OD)relationships.In real air traffic operation,a flight does not straightly fly from departure airport to landing airport,but along some air route waypoints.ARN consists of air route waypoints and connections between them.In 2012,Cai et al.firstly investigated the Chinese ARN15and found that the degree distribution of Chinese ARN is homogeneous but the traf fic flow is rather heterogeneous.Vitali et al.then investigated the horizontal deviation and delays in Italian ARN.16The analysis of ARN is quite a novelty in the literature.However,the network robustness,which is an important issue for infrastructure systems17and has been extensively studied in ATN,18,19is still rare in ARN.In the typical network robustness model,edges are removed by different targeted attack strategies and the size of giant component estimates the robustness of the network.20When a small amount of edges are removed,the size of giant component is of a very small change.In this paper,we focus on identifying the vital edges in Chinese ARN by examining the robustness of the new network after removing an edge set via memetic optimization.Remarkably,we find that the most vital edges are not necessarily the edges of the highest topological importance.

The rest of this paper is organized as follows.In the next section,we demonstrate Chinese air route network and its basic properties.Section 3 describes the optimization model and the memetic algorithm.Section 4 presents the simulation results and corresponding analysis.Finally,the paper is concluded in Section 5.

2.Chinese air route network

In Ref.15,the authors found that the topology structure of the Chinese ARN is homogeneous,yet its distribution of flight flow is quite heterogeneous.If we compare the Chinese ATN with the Chinese ARN,we found signi ficant differences.On one hand,the Chinese ATN is a typical small-world with low average shortestpath length and large clustering coefficient.On the other hand,the Chinese ARN is not a small-world network due to its low clustering coefficient,large average shortest path length and exponential spatial distance distribution.

3.Model

3.1.Optimization model

The static robustness of complex networks has been extensively studied in the past decades.In Ref.21,it is quantified by the relative size of the largest connected componentG=N′/NwhereNis the total number of nodes in initial network andN′is the number of nodes in the largest component after attack.The larger value ofGrepresents a more robust network.Based on the largest connected component,Schneider et al.proposed a measureRto evaluate the robustness against targeted attack on nodes.17

wheres(Q)is the fraction of nodes in the largest component after removingQnodes.For calculating the robustness of a network,we will follow a degree adaptive strategy:the highest degree nodes will be systematically removed one by one.It is a more comprehensive measure of network robustness.Obviously,a network with higherRhas a stronger resistance to targeted attacks.

In the Chinese ARN,the closure of air route segment will decrease the connectivity of the whole network.If the vital edges can be recognized,we can prevent the cascading effect induced by the remove of the edges.It is of great significance to identify vital edges that lead to the vulnerability of Chinese ARN.In Ref.22,Freeman proposed a global metric edgebetweenness to measure the importance of an edge,which can identify influential edges effectively.It is defined as follows:

where Γ is the set of nodes,njkthe number of the shortest paths fromjtok,andnjk(i)the number of the shortest paths fromjtokvia edgei.

In this work,we formulate a combinational optimization problem to identify the vital edges within network robust model in the Chinese ARN.The objective is to minimize the network robustness after removing certain edges,i.e.closing certain air route segments.Therefore,these edges play an important role in maintaining network robustness.The optimization model is formulated as follows:

A樣品空白對照——25 μl樣品+25 μl底物（37 ℃孵育10 min）+50 μl蒸餾水（37 ℃下孵育 60 min）+100 μl醋酸-醋酸鈉緩沖溶液；

whereVis the total number of edges in the network and x is aVdimensional binary variable,e(k)∈ ｛0，1｝ (e(k)represents thekth edge in the network).e(k)=1 represents that the edgee(k)is removed,otherwise it remains in the network.The total number of removed edges is certain and denoted as cost(C).Thus,we can identify critical edges in the network and minimize its robustness.

3.2.Memetic algorithm

For solving this optimization model,we will use the memetic algorithm(MA),a useful tool for dealing with large-scale combinational problem.23–26Coming from the concept of meme,MA is defined as a part of local improvement in the process of cultural evolution.It is a hybrid metaheuristic of global search and heuristic local search with three operations:crossover,local search and tournament selection.

(1)Initialization

In MA,the population is composed ofPnindividuals.Each individualxrepresents a scheme of removing edges in the network and was generated randomly.

(2)Crossover

The crossover operator works on two parent individuals and can search in a large area.Suppose thatxp1andxp2are two parent individuals,andxc1andxc2are two child individu-als.First,we assignxp1toxc1andxp2toxc2and obtain the following sets of edges:

Table 1 Pseudocode of MA.

In summary,only the set of non-common edges that we want to remove will be swapped betweenxc1andxc2(Fig.3).

(3)Local search

The local search operator is an important part in MA that can accelerate the convergence speed.Based on previous edge importance evaluations,27,28we adopted a local search in the direction of removing more important edges.We first select an individual from parent and child population using the roulette wheel selection based on their fitness.Then for each edge of the selected individual,we conduct a local search with probabilityPl.For example,edgeeij(eijrepresents the edge between nodeiand nodej)will mutate into a randomly selected existing edgeelmbut not in its individual.This mutation will be accepted when the following formula is satisfied:

Table 2 Parameters of memetic algorithm.

where μ is a formula parameter in the range[0,1]andkl，km,kiandkjrepresent the degree of nodesl,m,iandjrespectively.

(4)Tournament selection

In this part,two individuals are respectively chosen from parent population and child population to run a tournament for the tournament selection.The population with the best fitness is selected for the next generation,and the total number of generation isPm.

To conclude,the pseudocode of MA proposed is presented in Table 1.

4.Results

In some previous papers,under different kinds of malicious attacks on edges,the strategy based on edge-betweenness is actually a commonly adopted attack strategy.20,29,30Here,in order to identify the vital edges,we examine the robustness of the new networks after removing edges via MA,and compare it with the highest edge-betweenness adaptive strategy(BEAS).As many real-world networks are of scale-free properties,such as air transportation network,9World-Wide Web,31Internet32and social network,33the experiments are carried out not only on Chinese ARN but also on Baraba′si-Albert(BA)scale-free network to demonstrate the universality of our method.The Chinese ARN has 1499 nodes and 2242 edges.The BA scale-free network is generated withm0nodes and a new node is added withmedges at each time step,which connect the new node withmdifferent existing nodes.Here,it is set thatm0=2 andm=2 and the BA network is of 1000 nodes and 2000 edges.The cost denoting total number of removing edges is set from 0 to 300 and the network without edges removed represents the initial network.Table 2 shows the configurations of the memetic algorithm parameters used on the optimization model.

Fig.4 shows the simulation results of the MA and BEAS of identifying the vital edges for the BA network and Chinese ARN.Looking at both networks via MA,we can see that the robustnessRdecreases and the costCincreases when removing edges(Fig.4(a)and(b)).It can also be noticed that the MA is significantly better than the BEAS.The difference between the two methods is especially high.It is obvious that the critical edges in the network are not extremely related with the edge-betweenness.Moreover,the memetic algorithm works better in the Chinese ARN and decreases its robustnessRfaster when a few edges are removed.The reason is that the Chinese ARN is not a small-world network.And the Chinese ARN is vulnerable because of its small clustering coefficient and large average shortest path length.In detail,Fig.4(c)and Fig.4(d)separately show 10 edges identified by the MA and BEAS methods in the Chinese ARN.It is found that all the top 10 highest edge-betweenness edges in the network are located at the middle China,which are almost completely different from the 10 edges identified by MA.

We have seen that the MA works on both Chinese ARN and BA network.In order to reveal the underlying mechanism clearly,we examine a toy model with a network containing 10 nodes and 17 edges(Fig.5).In Fig.5,the blue lines are the existing edges and gray dotted lines are edges removed in that step.In the same way,the gray nodes mean that these nodes are removed and yellow nodes still exist.When no edge is removed from the network(Fig.5(a)),the robustness of the initial network is 0.35.Here,three edges are removed to measure the criticality of these edges using the MA and BEAS methods.Since edgese1，4,e2，7ande4，9have the highest edgebetweenness in the network,they are removed in the BEAS(Fig.5(b))and now we have a new network namedA.Similarly,edgese1，3,e4，9ande7，9are identified as the most important ones in the MA,and we now have a new network B(Fig.5(f)).For estimating which group of edges is critical,we compare the robustness of networkAandB(Fig.5(c)–(e))and Fig.5(g)–(i)).Table 3 illustrates the corresponding solutions and the robustness of the solution for both methods.

In networkA(BEAS),we first remove node 2 with the highest-degree together with all edges connected with it:e2，3,e2，4,e2，5,e2，8ande2，10.s(Q=1)of the new network is 0.9,which is the fraction of nodes in the giant component after removing 1 node(Fig.5(c)).However in networkB(MA),the value ofs(Q=1)quickly decreases to 0.7(Fig.5(g)).Then,after the second nodes are removed,s(Q=2)in both networksAandBare 0.4 and 0.3 respectively(Fig.5(d)and Fig.5(h)),which is reduced to 0.4 and 0.2 after the third node is removed(Fig.5(e)and Fig.5(i)).At the end,all nodes are removed from the network and the robustness of networkAandBis 0.37 and 0.29 respectively.Thus,as previous results revealed,the critical edges in the network are not extremely related to the edge-betweenness,which apparently contradicts common intuitions.

Table 3 illustrates the corresponding solutions and the robustness of the solution to both methods of the toy model in Fig.5.In the network after removingQnodes and the edges connected with them,Nis the number of nodes,Mis the number of edges,ands(Q)is the fraction of nodes in the largest component.The results demonstrate that the most vital edges are not necessarily the edge with the highest topological importance.Thus these edges identified by MA are important for the network robustness and should be protected to ensure the survivability of the network.

Table 3 Illustration of vital edges identified by MA and BEAS.

5.Conclusions

It is of great importance to improve the robustness of real networks.In this paper,we identified the vital edges in Chinese air route network,which lead to fast breakdown after targeted attacks.Our results reveal that the edge-betweenness,an index to measure the importance of edges in short paths,is of little relevance to this problem.Furthermore,we demonstrate that the memetic algorithm is able to pinpoint the edges that have been proven more important than edges of high edgebetweenness.We also confirm these findings in scale-free model networks,hence offering novel insights of edge essentiality in various real networks.Thus,we think the vital edges identified by memetic algorithm should be especially protected to ensure a good performance of a network.In Chinese ARN,this means that air traffic managers should foresee complex solutions when considering the closure of one vital air route segment.

Acknowledgements

This paper is supported by the National Natural Science Foundation of China(Nos.91538204,61425014,61521091),National Key Research and Development Program of China(No.2016YFB1200100),andNationalKeyTechnology R&D Program of China(No.2015BAG15B01).

1.Amaral LAN,Scala A,Barthe′le′my M,Stanley HE.Classes of small-world networks.ProcNatlAcadSciUSA2000;97(21):11149–52.

2.Guimera`R,Mossa S,Turtschi A,Amaral LAN.The worldwide air transportation network:Anomalous centrality,community structure,and cities’global roles.Proc Natl Acad Sci USA2005;102(22):7794–9.

3.Barrat A,Barthe′lemy M,Pastor-Satorras R,Vespignani A.The architecture of complex weighted networks.Proc Natl Acad Sci USA2004;101(11):3747–52.

4.Gautreau A,Barrat A,Barthe′lemy M.Microdynamics in stationary complex networks.Proc Natl Acad Sci USA2009;106(22):8847–52.

5.Verma T,Arau′jo NAM,Herrmann HJ.Revealing the structure of the world airline network.Sci Reports2014;4:5638.

6.Verma T,Russmann F,Arau′jo NAM,Nagler J,Herrmann HJ.Emergence of core–peripheries in networks.Nat Commun2016;7(1):10441.

7.da Rocha LEC.Structural evolution of the Brazilian airport network.J Stat Mech2009;2009(4):125–36.

8.Wang JE,Mo HH,Wang FH.Evolution of air transport network of China 1930–2012.J Trans Geo2014;40:145–58.

9.Zhang J,Cao XB,Du WB,Cai KQ.Evolution of Chinese airport network.Physica A2010;389:3922–31.

10.Li W,Cai X.Statistical analysis of airport network of China.Phys Rev E2004;69(4 Pt 2):046106.

11.Fleurquin P,Ramasco JJ,Eguiluz VM,Victor M.Characterization of delay propagation in the US air-transportation network.Transp J2014;53(3):330–44.

12.Bagler G.Analysis of the airport network of India as a complex weighted network.Physica A2008;387(12):2972–80.

13.Du WB,Zhou XL,Lordan O,Wang Z,Zhao C,Zhu YB.Analysis of the Chinese Airline Network as multi-layer networks.Trans Res Part E2016;89:108–16.

14.Liu HK,Zhou T.Empirical study of Chinese city airline network.Acta Phys Sin2007;56(1):106[Chinese].

15.Cai KQ,Zhang J,Du WB,Cao XB.Analysis of the Chinese air route network as a complex network.Chin Phys B2012;21(2):028903.

16.Vitali S,Cipolla M,Gurtner G,Lillo F,Beato V,Pozzi S.Statistical regularities in ATM:Network properties,trajectory deviations and delays.Second SESAR innovation days2012.

17.Schneider CM,Moreira AA,Andrade Jr JS,Havlin S,Herrmann HJ.Mitigation of malicious attacks on networks.Proc Natl Acad Sci2011;108(10):3838–41.

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

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

20.Zeng A,Liu WP.Enhancing network robustness against malicious attacks.Phys Rev E2012;85(6):066130.

21.Motter AE,Lai YC.Cascade-based attacks on complex networks.Phys Rev E2002;66(6):065102.

22.Freeman L.Set of measures of centrality based on betweenness.Sociometry1977;40(1):35–41.

23.Menc?′a R,Sierra MR,Menc?′a C,Varela R.Memetic algorithms for the job shop scheduling problem with operators.Appl Soft Comput2015;34:94–105.

24.Gong MG,Cai Q,Li YY,Ma JJ.An improved memetic algorithm for community detection in complex networks.2012 IEEE world congress on evolutionary computation;2012 June 10–15,Brisbane,Australia.Piscataway(NJ):IEEE Press;2012.

25.Neri F,Cotta C.Memetic algorithms and memetic computing optimization: A literature review.SwarmEvolComput2012;2:1–14.

26.Bhuvana J,Aravindan C.Memetic algorithm with preferential local search using adaptive weights for multi-objective optimization problems.Soft Comput2016;20(4):1365–88.

27.Tan F,Xia YX,Zhang WP,Jin XY.Cascading failures of loads in interconnected networks under intentional attack.EPL2013;102(2):28009.

28.Peng XZ,Yao H,Du J.Load-induced cascading failures in interconnected networks.Nonlin Dyna2015;82(1–2):97–105.

29.Wang JW,Rong LL.Robustness of the western United States power grid under edge attack strategies due to cascading failures.Safety Sci2011;49(6):807–12.

30.Mirzasoleiman B,Babaei M,Jalili M,Safari M.Cascaded failures in weighted networks.Phys Rev E2011;84(4):046114.

31.Albert R,Jeong H,Baraba′si AL.Diameter of the World-Wide Web.Nature1999;401(6):130–1.

32.Faloutsos M,Faloutsos P,Faloutsos C.On power-law relationships of the internet topology.Comput Commun Rev1999;29(4):251–63.

33.Newman MEJ.The structure and function of complex networks.SIAM Rev2003;45(2):167–256.

28 July 2016;revised 12 September 2016;accepted 8 October 2016

Available online 21 December 2016

?2016 Chinese Society of Aeronautics and Astronautics.Production and hosting by Elsevier Ltd.This is anopenaccessarticleundertheCCBY-NC-NDlicense(http://creativecommons.org/licenses/by-nc-nd/4.0/).

*Corresponding author.

E-mail address:xbcao@buaa.edu.cn(X.Cao).

Peer review under responsibility of Editorial Committee of CJA.