Gérald Gurtner

Physics, Networks and Agent-Based Models

Community Detection — Airports

We had at our disposition two databases, one called DDR and gathering detailed trajectories of all the flights over Europe during 15 months, and the second one called NEVAC, with detailed information on airspaces. Some of the results can be found in this paper and this paper, the rest is in a deliverable which can be sent on demand.

One of the analyses we have performed is called community detection, sometimes called cluster analysis. In network theory, the overall approach of community detection is to try to find groups of nodes which are more closely connected to each other than they are to the rest of the network. There are several methods and algorithms for this: we used modularity-based methods, an information-based method with the infomap algorithm and finally the very powerful OSLOM algorithm.

First, we applied these methods to the network of airports. Here is an image of communities of airports using modularity maximization with the Blondel algorithm.

cropped-communities_pretty.png

Colours indicate strongly connected airports, which could help designing better inter-airports procedures or even sketch out a new bottom-up division of the European airspace, similar to the FABs. By comparing this partition of the European Airspace to the one envisioned for the FABs (see figure below), some details are quite striking: for instance, a FAB gathering Portugal and Spain make sense, just like a FAB gathering UK and Ireland. On the contrary, FAB gathering France, Germany and Benelux does not seem to be a good idea based on this analysis. Same remark for a FAB gathering Italy and Greece, or a division of Scandinavia in two blocks, as it is currently planned.

map_communities_natural.png

It is also interesting to try to remove the bias due to distance between airports. For this, we changed the null model of the standard definition of modularity and replaced it with a gravity null model (essentially saying that the airport are more likely to be connected if they are close to each other). Maximizing this new modularity with a simulated annealing process, we ended up with the following partition.map_communities_SA_spatial.png

Communities are quite different now, even though some are still robust, like the Greek community of the UK one. Strikingly, it is even possible to see a “Ryan Air” network: Fiumicino in Rome, Stansted in the UK, Charleroi near Brussels, Beauvais near Paris, etc, are all part of the same community.

Hence, this method is able to catch hidden statistical features of the data and deliver a bottom-up approach for some important issues.

Since the airport network is not the most relevant from an operational point of view for the FAB, we also studied other networks related to the airspace.

PreviousNext

%d bloggers like this: