CBL - Campus del Baix Llobregat

Projecte llegit

Títol: Power domination sets and centralities in the European airport network

Estudiants que han llegit aquest projecte:

Director/a: COMELLAS PADRÓ, FRANCESC

Departament: MAT

Títol: Power domination sets and centralities in the European airport network

Data inici oferta: 17-03-2021     Data finalització oferta: 17-11-2021


Estudis d'assignació del projecte:
    GR ENG SIS TELECOMUN
    GR ENG SIST AEROESP
Tipus: Individual
 
Lloc de realització: EETAC
 
Paraules clau:
European airport network, power domination, centralities
 
Descripció del contingut i pla d'activitats:
A power domination set in a network is a subset of its nodes such
that by applying a simple set of rules all nodes are monitored.
The concept was introduced in the context of electrical networks
but has been extended and studied for other networks and families
of graphs. It has been shown that this problem is NP-complete and
thus, for large networks, optimization methods like simulated
annealing, threshold acceptance or genetic algorithms could be
useful to find near-optimal solutions.
In this TFG we will study power domination sets for small
families of small world / scale free / hierarchical graphs and
the results will be applied to analyze these sets in relation to
airport centralities in the European airport network.
 
Overview (resum en anglès):
A power domination set in a network is a subset of its nodes such that by applying a simple set of rules all nodes are monitored. The concept was introduced in the context of electrical networks but has been extended and studied for other networks and families of graphs.

It has been shown that this problem is NP-complete and thus, for large networks, optimization methods like simulated annealing, threshold acceptance or genetic algorithms could be useful to find near-optimal solutions.

In this TFG we introduce a new threshold acceptance algorithm to find power domination sets in graphs and we apply it to analyze these sets in relation to airport centralities and cascade failures in the European airport network.

To start with, the cited network is analyzed using a few distinct centrality definitions, including a classical degree centrality, betweenness centrality PageRank, etc. to find the most connected nodes and have an overview of the whole network. An alternative outlook of the local connectivity between nodes is given by finding communities. These groups of nodes are identified according to their strong local associations, in opposition to weaker associations with the rest of the nodes.

Having characterised the network from different perspectives, cascade failures are modelled to detect vulnerabilities on the network by comparing the effects of different airport closures. A comparison is assessed based on the effect of the failure of airports depending on their classification. Failing nodes could belong to power dominations sets or be nodes selected from high, medium or low connectivity levels.

The main result is a complete insight on how the system is affected from the failure of nodes according to their properties and how the parameters used to tune the model affect this analysis.

© CBLTIC Campus del Baix Llobregat - UPC