Degree centrality and superhubs : the lastminute.com case

The goal of this thesis is to analyse different techniques of centrality applied on a huge air transportation network of lastminute.com in order to extrapolate a list of airports that represent the ”busiest” airports in the world nicknamed as ”superhubs”. The first step is to define the environment in which the project will run, and the choice lean on the Google Cloud Platform already used in the company. The analysed data come from different interaction that the user can do on the lastminute.com site such as booking data, search data and search results data, in order to have a lot of information and much more knowledge as possible. The graph is the best data structure to exploit for this kind of problem and the degree centrality measure is used to achieve the extrapolation of the ”superhubs” list. There are a lot of degree measures applied on graphs; in this thesis five different techniques will be analysed: the classical degree centrality, the eigenvalue centrality, the Katz centrality, betweeness centrality and a particular weighted centrality. The thesis presents different simulations in order to compare the centrality measure mentioned before in terms of graph size (number of vertices |V | and edges |E|), computational complexity, timing of execution, scalability and results.

L’obiettivo di questa tesi è di analizzare diverse tecniche di centralità applicate sull’enorme rete di trasporto aereo di lastminute.com al fine di estrapolare un elenco di aeroporti che rappresentano gli aeroporti ”più trafficati” del mondo soprannominati ”superhub”. Il primo passo è definire l’ambiente in cui verrà eseguito il progetto e la scelta si baserà sulla piattaforma Google Cloud già utilizzata in azienda. I dati analizzati provengono da diverse interazioni che l’utente può fare sul sito lastminute.com come dati di prenotazione, dati di ricerca e dati dei risultati di ricerca, al fine di avere una mole importante di informazioni e più conoscenza possibile. Il grafo è la migliore struttura dati da sfruttare per questo tipo di problema e le diverse misure di centralità dei grafi verranno sfruttate per ottenere l’elenco dei ”superhub”. Ci sono molte misure di centralità applicate sui grafi; in questa tesi verranno analizzate cinque diverse tecniche: la classica centralità, eigenvector centrality, Katz centrality, betweenness centrality e una particolare centralità ponderata. La tesi presenta diverse simulazioni al fine di confrontare la misura della centralità menzionata in precedenza in termini di dimensioni del grafico (numero di vertici |V | e bordi |E|), complessità computazionale, tempistica di esecuzione, scalabilità e risultati.