Topological Srrucrure of US Flighr Nerwork Based on Complex Nerwork Theory

Li Shanmei（李善梅），Xu Xiaohao（徐肖豪），Wang Fei（王飛），Wang Xinglong（王興隆）

Air Traffic Management Research Base，Civil Aviation University of China，Tianjin 300300，P.R.China

（Received 3 June 2014；revised 25 December 2014；accepted 7 March 2015）

Topological Srrucrure of US Flighr Nerwork Based on Complex Nerwork Theory

Li Shanmei（李善梅）*，Xu Xiaohao（徐肖豪），Wang Fei（王飛），Wang Xinglong（王興隆）

Air Traffic Management Research Base，Civil Aviation University of China，Tianjin 300300，P.R.China

（Received 3 June 2014；revised 25 December 2014；accepted 7 March 2015）

Absrracr：US flight network，composed of 285 airports（nodes）and 3 971 flights（edges）is studied.A static network model and a dynamic network model of US flight network are established.Firstly，the characteristics of static network are analyzed.One finds that such a network is a″small-world″and″scale-free″network.The cumulative degree distributions of weighted network and unweighted network follow″Double Pareto Law″.And the degree exponent of weighted network is smaller than unweighted network.The average shortest-path length is 2.368 9，which is smaller than previous results.The clustering coefficient of unweighted network is 0.637 1 and of weighted network is 0.653 6，which are both bigger than previous results.The correlation of degree，unweighted clustering coefficient and weighted clustering coefficient are also discussed.Secondly，the characteristics of dynamic network are studied.The structure of flight network is changing as the time goes by on a day.In rush hours，the network＇s character of″scale-free″is stronger than other times.And then the relationships of topological structures and congestion effects are addressed.

complex network；scale-free；small-world；congestion effect

0 Inrroducrion

Complex network theory provides strong method to understand the topological structures of different systems.Along with the flourishing development of complex network theory，″smallworld″network model and″scale-free″network model are the most exciting discovery at the end of the last century［1-2］.During the past few years，complex network analysis has been used to study airlines from different aspects.The world-wide airport network（WAN）has been proved that of″small-world″and″scale-free″［3-8］.Besides the national airline networks，such as the airline network of America，China，Brazil，and India，are also extensively studied［9-12］.It is found that the national airline networks can exhibit different properties including disassortative mixing，two regime power-law degree distributions，exponential traffic volume increasing and so on.The research above is important for reasons of policy，administration and efficiency.

This paper will present investigations of US flight network，in which the vertices are the airports and the flights connecting two airports are represented by the edges.The network has three characteristics：（1）Direction.All the flights are directed，sorted as arrival and departure.（2）Weight.The number of flights from any given airport i to j is used to indicate how busy a certain line is.（3）Hourly flight information.The hourly flight information partly reflects the evolution of the flight network.

In this paper，US flight network is studied from two aspects.Firstly，the network as a″static network model″is studied，which contains″unweighted network″and″weighted network″.The statistical characteristics are analyzed such as thedegree distributions，the weight distributions，the clustering coefficient，the diameter and so on. Secondly，the network as a″dynamic network model″is studied，whose structure varies along as the time goes by.The weight distributions are analyzed，which show the hourly evolution mechanisms of US flight network.

1 Dara and Model

US flight network contains 285 nodes and 3 971 directed lines that connect most major cities in USA.The data are about 6：00 to 24：00 of January 1st，2010（The data are obtained from http：//www.transtats.bts.gov/Fields.asp？Table-ID=236）.We collect the number of flights of every line in each hour.

1.1 Sraric nerwork model

The static network model is established from the point of macro view.The topology of the network can be symbolized by a 285×285 matrix A. aijis 1 if there is no flights flying from airport i to airport j on the day.It is 0 otherwise.The element of weighted matrix U represents the number of flights from airport i to airport j on the day.

1.2 Dynamic nerwork model

The dynamic network model is established from micro perspective.The network structure varies as the number of flights of each link is different for every hour.A 285×285×18 connectivity matrix C is established.cijtis 1 if there is no flights flying from airport i to airport j at the t th hour of a day.It is 0 othewise.t=1 represents the time interval from 6：00 to 7：00；t=2 represents the time interval from 7：00 to 8：00；…；t= 18 represents the time interval from 23：00 to 24：00.A 285×285×18 weight matrix W is also established with wijtbeing the number of flights from airport i to airport j at the t th hour.Fig.1 gives the structures of static network model and dynamic network model，respectively.

Fig.1 Structures of network models

2 Topological Analysis of Sraric Nerwork

2.1 Degree disrriburions and degree correlarions

Degree of a node is the number of nodes to which it is connected.In a directed network，indegree（out-degree）of a node is the number of incoming（out-going）links.

For the unweighted network，in-degree，outdegree and degree of node i is defined as

where N is the total number of nodes in the network.

Similarly，one can prove the degree expressions for weighted network

Firstly，one considers the distributions of k（i）and kw（i），respectively.The cumulative form gives the probability that airport i has a degree larger than k.It is expressed as

Fig.2 presents behaviors of k（i）and kw（i）distributions.It shows that both two distributions follow a two-regime power law with two different exponents，known as double Pareto law. The formation of lower-degree airports is different from that of higher-degree airports.

Fig.2 Cumulative degree distribution of US flight network with double Pareto law

The double Pareto law shows that US flight network is a scale-free network.The reason of the phenomenon is studied by many scholars.An airport cannot increase routes unlimitedly as the existence of connection cost［3］.Two airports cannot connected if the distance of them is much bigger than the restrict of geography distance［6］.In the paper，imbalance economy and congestion effect in transportation are the most important causes of the double Pareto law distribution.

Zheng，et al.pointed out that the bigger the degree exponentαwas，the weaker the heterogeneity was［13］.Fig.2 illustrates that the heterogeneity of weighted network is stronger than unweighted network，because the power exponent of kwis smaller than k.In the paper，the phenomenon can be attributed to the economic imbalance and congestion effect.

As shown in Fig.3，the distributions offollow double Pareto law.

Fig.3 Cumulative degree distribution

The difference between the degree exponentsis very small，which shows that US flight network has fine symmetries.The number of flights from airport i to j is equal to the number of flights from airport j to i.

The nonlinear relationship of kwand k is given in Fig.4.The relational expression is described as kw～k1.1464.

Fig.4 Correlation of unweighted degree and weighted degree（kw—k1.1464）

The relationship shows that the number of flights increases exponentially with the increase of air routes.This phenomenon can be understood by network externalities in economics.People always choose the airports with many routes as there are many direct flights and transfer flights，which makes their journey much more convenient.

2.2 Shorresr parh analysis

Diameter is the average shortest-path length between two nodes in the system［14］.The diameter of our flight network is defined as

where dijis the minimum number of edges connecting from airport i to j.

The results of the shortest paths analysis is shown in Table 1.Apart from other statistics，we also show the number of flight transfers，which is an indicator of the convenience of travel in the network.In Table 1，we can find that the shortest path lengths of the whole flight network are 1，2，3 and 4，with the probabilities of 0.049 6，0.542 6，0.373 5，0.034 3，respectively.This implies that there is no more than three transfers from airport i to j.The diameter of US flight network is D=2.368 9.It means that on the average there is 1.368 9 transfers from airport i to j.Thus，the diameter is rather small compared with the number of airports，which demonstrates the properties of small-world.In addition，US flight network is becoming″smaller″as time goes by as the value D computed here is a little smaller than D=2.403 calculated in Ref.［15］.

Table 1 Shorresr parhs and rheir percenrage

2.3 Clusrering coefficienr

Clustering coefficient is used to quantify the inherent concentration trends.It includes unweighted clustering coefficient ciand weighted clustering coefficient

The clustering coefficient of unweighted network C and weighted network Cware defined as

The clustering coefficient C is 0.637 1，and Cw0.653 6.They are bigger than previous research result 0.618，which indicates the network is becoming smaller and smaller as the time goes by［15］.The clustering coefficient and degree correlation are given in Fig.5.C（k）decreases with degree increasing，which means that the clustering coefficient of nodes with bigger degree is much small and nodes with smaller degree connects closely.It shows that the structure of US flight network is hierarchical.Besides，the values of Cw（k）and C（k）are becoming gentle with k increasing and Cw（k）is bigger than C（k），which indicate that the traffic between airports with bigger degree is much higher than airports with smaller degree.In the paper，we can get that US flight network follows Pareto law.This contributes to congestion formation.Thus the small average path length and high cluster coefficient demonstrate the small-world property of US flight network.

Fig.5 Correlation of clustering coefficients and degree

3 Topological Analysis of Dynamic Nerwork

The previous approaches to study the complex systems mainly focus on the topology，and partly neglect the time-varying weight associated with the link［12］.

The evolution of US flight network on a day based on the dynamic network model is studied. Taking 5：00—6：00，8：00—9：00 and 23：00—24：00 intervals for instance，the distributions of kwof the above intervals are displayed in the following.

Fig.6 shows that the structure of the dynamic network is changing as the time goes by on a day.In rush hours，the network＇s character of″scale free″is stronger than other times.Furthermore，the degree exponent of rush hours is much smaller than non-rush hours，which shows that the heterogeneity of rush hours is stronger than other times.For example，αof 8：00—9：00 is smaller than 5：00—6：00，which is shown in Fig.6.The results above are consistent with the serious congestion of rush hours.

Fig.6 Cumulative degree distribution of weighted network for different intervals

4 Conclusions

The weighted and unweighted US flight network are studied.The static network model is constructed，which contains unweighted network and weight network.The cumulative degree distribution，the shortest path length and clustering coefficient are discussed both for the unweighted and weighted networks，which indicates US flight network is of″scale-free″and″small world″.The results are also compared with previous research. The dynamic network model is also established. The hourly weight distributions are analyzed and the hierarchy of the network for different intervals is discussed.

The research in this paper displays that US flight network is not a random network，but a scale free network.The fluctuation of the number of flights on the non-random structure should be addressed for the next step，which is used to explain the behavior of traffic congestion.

Acknowledgemenrs

This work was supported by the Projects in the National Science&Technology Pillar Program（2011-BAH24B10），the Joint Funds of National Natural Science Foundation of China（61571441），the Fundamental Research Funds for the Central Universities of Civil Aviation University of China in 2016，the Open Fund of Air Traffic Management Research Base（No.KGJD201503），and the Scientific Research Foundation of Civil Aviation University of China（No.2014QD01S）.

［1］ Watts D J，Strogatz S H.Collective dynamics of″small-world″networks［J］.Nature，1998，393（6684）：440-442.

［2］ Barabási A L，Albert R.Emergence of scaling in random networks［J］.Science，1999，286（5439）：509-512.

［3］ Amaral L A N，Scala A，Barthelemy M，et al.Classes of small-world networks［J］.Proceedings of the National Academy of Sciences，2000，97（21）：11149-11152.

［4］ Guimer′a R，Mossa S，Turtschi A，et al.The worldwide air transportation network：Anomalous centrality，community structure，and cities global roles［J］. Proceedings of the National Academy of Sciences，2005，102（22）：7794-7799.

［5］ Li W，Cai X.Statistical analysis of airport network of China［J］.Physical Review E，2004，69（4）：046106.

［6］ Barrat A，Barthelemy M，Pastor-Satorras R，et al. The architecture of complex weighted networks［J］. Proceedings of the National Academy of Sciences，2004，101（11）：3747-3752.

［7］ Guimera R，Amaral L A N.Modeling the worldwide airport network［J］.The European Physical Journal B-Condensed Matter and Complex Systems，2004，38（2）：381-385.

［8］ Colizza V，Barrat A，Barthélemy M，et al.The role of the airline transportation network in the prediction and predictability of global epidemics［J］.Proceedings of the National Academy of Sciences，2006，103（7）：2015-2020.

［9］ Gautreau A，Barrat A，Barthélemy M.Microdynamics in stationary complex networks［J］.Proceedings of the National Academy of Sciences，2009，106（22）：8847-8852.

［10］Zhang J，Cao X B，Du W B，et al.Evolution of Chinese airport network［J］.Physica A：Statistical Mechanics and Its Applications，2010，389（18）：3922-3931.

［11］da Rocha L E.Structural evolution of the Brazilian airport network［J］.Journal of Statistical Mechanics：Theory and Experiment，2009，4（1）：P04020.

［12］Bagler G.Analysis of the airport network of India as a complex weighted network［J］.Physica A：Statistical Mechanics and Its Applications，2008，387（12）：2972-2980.

［13］Zheng J F，Gao Z Y，Zhao X M.Properties of transportation dynamics on scale-free networks［J］.Physica A：Statistical Mechanics and Its Applications，2007，373（36）：837-844.

［14］Albert R，Jeong H，Barabási A L.Internet：Diameter of the world-wide web［J］.Nature，1999，401（6749）：130-131.

［15］Chi L P，Wang R，Su H，et al.Structural properties of US flight network［J］.Chinese Physics Letters，2003，20（8）：1393.

（Executive Editor：Xu Chengting）

V355Documenr code：AArricle ID：1005-1120（2015）05-0555-05

*Corresponding aurhor：Li Shanmei，Lecturer，E-mail：yma820203@163.com.

How ro cire rhis arricle：Li Shanmei，Xu Xiaohao，Wang Fei，et al.Topological structure of US flight network based on complex network theory［J］.Trans.Nanjing U.Aero.Astro.，2015，32（5）：555-559.

http：//dx.doi.org/10.16356/j.1005-1120.2015.05.555