An introduction to network embedding and role discovery : methods and applications

Complex networks analysis is more and more in the spotlight of scientific research due to the large number of possible applications. Nevertheless, with very large amount of data, network models become increasingly difficult to handle and to store. This opens the problem of reducing the dimensionality of the network by means of a compact node representation, which is called network embedding. The studies on network embedding pave the way to many subsequent tasks, and reveal connections with already existent network problems, such as role discovery. In this thesis we give three main contributions. First, we review and compare several network embedding and role discovery methods, obtaining a possible taxonomy for them. Then, we select six of these algorithms in order to see them in action on a collection of social networks. Finally, we apply the selected algorithms to two real-world networks: ICIO Dataset (Inter-Country Input-Output Tables) and European Air Transportation Network (EATN). In particular, for ICIO, among other results, we analyse the evolution in time of the roles of a set of world countries in international trades, while for EATN we compare the roles that different airports have for low-cost and major airlines.

L’analisi di reti complesse è sempre più al centro dell’attenzione della ricerca scientifica per l’elevato numero di possibili applicazioni. Tuttavia, a causa della crescente quantità di dati a disposizione, l’elaborazione delle reti diventa sempre più problematica dal punto di vista computazionale. Questo pone il problema di ridurre la dimensionalità delle reti tramite una rappresentazione più compatta, cioè attraverso il procedimento che definiamo network embedding. Gli studi sui metodi di network embedding aprono la strada a diverse applicazioni e trovano collegamenti con altri problemi, come l’analisi di ruolo. In questa tesi si forniscono tre contributi principali. Per prima cosa, si presentano e confrontano diversi metodi di network embedding e analisi di ruolo, proponendo anche una possibile tassonomia. In seguito, si selezionano sei algoritmi per vederli in azione applicati ad una raccolta di reti sociali. Infine, si applicano gli algoritmi selezionati a due reti reali riguardanti il commercio mondiale (ICIO) e il trasporto aereo europeo (EATN). In particolare, per la rete ICIO, tra i vari risultati si presenta un’analisi dell’evoluzione negli anni del ruolo rivestito da un insieme di paesi coinvolti nel commercio internazionale. Invece, per la rete EATN si confrontano i ruoli di diversi aeroporti per compagnie aeree low-cost e tradizionali.