Efficient Computation of Time-Dependent Centralities in Air Transportation Networks

摘要

We introduce indices of centrality to analyze air transportation networks which represent 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 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 2010 provided by Official Airlines Guide (OAG) on the complete world-wide 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.