[en] English: In this project we study the optimization of a complex network based on the geographical length of the links and the number of geodesic paths that go through them (edge betweenness). By considering relevant properties of real complex networks (degree distribution, average distance, diameter, clustering, degree of intermediation of nodes and links, etc.), we generate initial networks with a predefined structure (random networks and a networks with links to the closest nodes) and we study cost functions that optimize the network to create a new network with properties comparable to the real size networks (including a power law degree distribution). We use two methods to perform the optimization: Simulated annealing, and Threshold Accepting. The first set of simulations use simulated annealing (programmed in C) starting with an initial Erdös-Rényi random graph and also graphs with links to the closest nodes. The results obtained with the different cost functions considered show that the optimized graphs do not display power law distributions. The second set of simulations use the Threshold Accepting method (written in Python and with the NetworkX package) based on an initial grid graph type with average degree near to 8. In this case the results obtained with different cost functions lead to power law degree distribution typical of scale-free networks, when the cost function is proportional to the product of the edge betweenness and the logarithm of the geographical distance between nodes. The results obtained in this case are compared with the actual network of world airports, suggesting a simple explanation to their structure and properties.

[es] Castellano: Éste proyecto tiene como objetivo el estudio de la optimización de una red compleja a partir de la longitud de sus enlaces i la medida del nombre de caminos geodésicos que le pasan (grado de intermediación de los enlaces o edge betweenness). En este trabajo, en base a las propiedades relevantes de las redes complejas reales (distribución de grado, distància media, diámetro, clustering, grado de intermediación de nodos y enlaces, etc.) se considera una red inicial con una estructura predefinida (aleatoria, con enlaces a los nodos más cercanos o tipo malla), y se estudia cuál es la función de coste que permite optimizar ésta red y generar una red de propiedades específicas ( en particular una distribución potencial de grados), comparables con las redes reales de dimensiones similares o proporcionales. Dado que la optimización de las redes complejas debe hacerse a partir de mecanismos de optimización combinatoria, se han utilizado dos métodos para la realización de las simulaciones: Simulated annealing (o recocido simulado), y Threshold Accepting (o algoritmo del umbral). La primera parte de las simulaciones utiliza el método de optimización del recocido simulado (programado en lenguaje C) a partir de los grafos iniciales aleatorios de tipo Erdös-Rényi i también para grafos iniciales con enlaces a los nodos más cercanos. Los resultados indicativos obtenidos con las diferentes funciones de coste consideradas muestran que los grafos resultantes del proceso de optimización no producen en general redes complejas con distribución de grado de tipo potencial (o scale-free), aunque mantienen algún parecido. La segunda parte de las simulaciones utiliza el método le umbral (escrito en Python y utilizando el paquete NetworkX) a partir de un grafo inicial de tipo malla y con un grado medio cercano a 8. En éste caso los resultados obtenidos con las diferentes funciones de coste dan lugar a redes con distribución potencial de grados típicas de redes scale-free, en el caso en que la función de coste es directamente proporcional al grado de intermediación de los enlaces i mantiene una proporción logarítmica respecto a la distància geográfica entre los nodos. Los resultados obtenidos en éste caso se han comparado con la red real de aeropuertos mundial, confirmando una explicación simple a su tipología y propiedades.