Projecte llegit
Títol: Optimització de xarxes d'interconnexió. Aplicació a una xarxa d'aeroports.
Estudiants que han llegit aquest projecte:
MONJO CURSACH, MONTSERRAT (data lectura: 14-09-2017)- Cerca aquest projecte a Bibliotècnica
MONJO CURSACH, MONTSERRAT (data lectura: 14-09-2017)Director/a: COMELLAS PADRÓ, FRANCESC
Departament: MAT
Títol: Optimització de xarxes d'interconnexió. Aplicació a una xarxa d'aeroports.
Data inici oferta: 11-01-2017 Data finalització oferta: 11-09-2017
Estudis d'assignació del projecte:
- GR ENG SIST AEROESP
| Tipus: Individual | |
| Lloc de realització: EETAC | |
| Paraules clau: | |
| xarxa d'aeroports, comunicabilitat, optimització | |
| Descripció del contingut i pla d'activitats: | |
| ¿ Com ha arribat una xarxa, per exemple l'elèctrica, la de
routers, la daeroports o fins i tot una xarxa biològica o social a tenir la configuració concreta que té ? Perquè són "petit-món" i moltes també "scale- free" ? Estudiarem si l'optimització de certs paràmetres ho explica. Un d'ells podria ser la "comunicabilitat" que compta, per a cadascun dels nodes de la xarxa, el nombre de camins que comencen i acaben en ell [1,2]. A partir d'una xarxa aleatòria geogràfica veurem quines condicions fan que el procés d'optimització dels paràmetres porti a estructures de xarxa similars a les reals. En aquest treball el mètode d'optimització que es farà servir serà l'algorisme llindar [3]. Per exemple, en el cas d'una xarxa d'aeroports començariem amb els nodes (aeroports) connectats aleatòriament i aplicant lalgorisme llindar canviarem connexions optimitzant diferents funcions de cost per trobar la millor i comparar comparar amb la real. [1] E. Estrada, J.A. Rodriguez-Velazquez, Subgraph centrality in complex networks, Physical Review E 71, 056103 (2005). http://arxiv.org/abs/cond-mat/0504730 [2] E. Estrada, D.J. Higham, N. Hatano, Communicability betweenness in complex networks, Physica A 388 (2009) 764774 http://arxiv.org/abs/0905.4102 [3] G. Dueck, T. Scheuer, Threshold Accepting: A general purpose optimization algorithm appearing superior to Simulated Annealing, J. Comput. Phys. 90 (1990) 161-175. |
|
| Overview (resum en anglès): | |
| The purpose of this degrees final project is the study of those parameters that determine, after their optimitzation, the properties of a network. We will focus on the optimitzation of the airports network of the United States of 2001. Each airports is represented by a node, which contains this information: name of the airport, coordinates and the total number of airports operations during a year.
The study is based on the creation of a random network. It has the same nodes but they are connected randomly. For this reason, its properties are very different to the real network properties. Hence, an optimitzation process should be apllied: threshold accepting. The algorithm performs an optimitzation to a certain cost function by making changes to the connections between nodes. Therefore, a final network with properties of small-world, a degree histogram which follows a potential law (both properties of real networks), etc, is achieved. Seven cost functions have been used and each of them is formed by one centrality. The centralities used are based on the paths between nodes, load models, etc. Moreover, the number of airports operations and its coordinates have been took into account. To prove the correct performance of the algorithm, four reduced networks has been generated from the real network. Once the results are obtained, the optimization of the airports network of USA has been performed by using the cost functions that works properly for this case. |
|