Heuristics of node selection criteria to assess robustness of world airport network

Citation

Soria, M., Lordan, O.; Sallan, J. M. (2017). Heuristics of node selection criteria to assess robustness of world airport network. Chinese Journal of Aeronautics, 30(4), 1473-1480.
doi: http://dx.doi.org/10.1016/j.cja.2017.04.012
UPCommons: http://hdl.handle.net/2117/108021

Abstract

The world airport network (WAN) is one of the networked infrastructures that shape today's economic and social activity, so its resilience against incidents affecting the WAN is an important problem. In this paper, the robustness of air route networks is extended by defining and testing several heuristics to define selection criteria to detect the critical nodes of the WAN. In addition to heuristics based on genetic algorithms and simulated annealing, custom heuristics based on node damage and node betweenness are defined. The most effective heuristic is a multi-attack heuristic combining both custom heuristics. Results obtained are of importance not only for advance in the understanding of the structure of complex networks, but also for critical node detection.

Algoritmos genéticos

Esta cita de Darwin resume en una frase el funcionamiento de los algoritmos genéticos.

Combinatorial explosion

Combinatorial optimization is about picking one element of a set of finite objects that optimizes an objective function. Put in this way, the solution may seem straightforward: just enumerate all elements of the set and assess the objective function for each object.

The problem with this naïve approach is that the number of elements of the set can be very large. Let's consider, for instance, the symmetric travelling salesperson problem. For an instance of n nodes, the number of possible solutions is the factorial of (n-1) divided by two. This means that, for a problem of size n=20, and taking one millisecond to assess each solution, it takes around 1,108,606 years to assess all solutions. This effect is called combinatorial explosion.

This video shows an example of an even faster combinatorial explosion. Additionally, helps in learning how to count large numbers in Japanese...