Time-Dependent Centrality

IIn cooperation with ECAD GmbH, the European Center for Aviation Development, we have started to analyze air transportation networks. Analysis tools for airport networks allow airports, airlines and policy makers to monitor network performance over time, and to design strategies to improve the competitive position of airports. Airlines and alliances of airlines can use these methods to optimize their schedules.

Recent interest in network analysis of the world-wide airport network
arose from its role for the spreading of diseases such as the SARS and the swine flu epidemic (Balcan et al. 2009, Colizza et al. 2006).

A first analysis of the world-wide airport network has been presented by Guimera and Amaral (2004) and  Guimera et al. (2005). They use a simple network model: each airport corresponds to a vertex and two vertices are connected by an undirected edge if and only if there is a non-stop flight between them (it does not matter when a flight departures or arrives, and for simplicity, the network is made symmetric). Burghouwt and Redondi (2009)  recently surveyed the state-of-the-art and compared several models and measures which are used to analyze the connectivity of air transport networks and airport accessibility.

We introduced several new centrality measures representing the importance of airports and individual flights  dependent on the time of the day (time-dependent centrality indices). Our centrality indices are based on earliest arrival paths with a minimum number of transfers in a time- and event-dependent network model. This means, that all paths correspond to real connections,  in particular with transfers which obey minimum transfer times between flights.

While the straight-forward computation of these indices is quite expensive, we provide efficient algorithms for the centrality computation. To this end, we construct a certain sequence of pairwise disjoint profile graphs representing all relevant paths by exploiting a special kind of subpath optimality. This avoids unnecessary repeated computations of \emph{all} optimal time-dependent multi-criteria paths and allows us to use single criterion path queries for the earliest arrival time (without path construction).

We have tested our method with original schedule data of 2000, 2005,
and 2010 provided byOfficial Airlines Guide (OAG) on the complete world-wide airport network and the European airport network. Our approach yields a speed-up over the straight-forward centrality computation by a factor of about 100 for the world-wide network and so makes the difference between an impractical and an applicable algorithm. A first experimental analysis yields interesting insights into the time-dependent transfer centrality of airports.

These results have been published in Proceedings of WALCOM 2011   . An extended version is available as Technical Report 2010/5.

Up