A latent space model approach for clustering complex network data

Complex networks are becoming increasingly important in many scientific domains, mostly due to the abundance of possible applications in mathematics, economy, biology or logistics. The mathematical community has been focusing on the modeling of networks as graphs objects since the late 1950s, producing an incredibly vast literature on the subject. The first part of the dissertation covers the essential notions and definitions of graph theory and introduces the most prominent models by describing their positioning in the general state of the art and presenting both similarities and dissimilarities between them. In the second part, a special attention is given to the class of Latent Space Models, which are characterized by the presence of latent variables used to compute the likelihood of the observed networks. The goal of Latent Space Models is to map the observed network in the latent space by meeting precise probabilistic requirements: once the latent positions have been estimated, different kinds of clustering can be performed in the latent space to group similar nodes as an interesting alternative to algorithms designed for community detection. Finally, throughout our work we provide many examples of analyses on benchmark datasets to assess the performances of Latent Space Models, as well as a final innovative application which also constitutes a bridge towards possible future developments.

Lo studio delle reti complesse sta diventando sempre più importante in diversi campi scientifici, soprattutto grazie all'abbondanza di possibili applicazioni in matematica, economia, biologia o logistica. La comunità matematica si è dedicata alla modelizzazione delle reti sotto forma di grafi a partire dalla fine degli anni '50, portando allo sviluppo di una notevole letteratura al riguardo. La prima parte della tesi è riservata alla definizione delle principali nozioni di teoria dei grafi ed alla trattazione dei modelli fondamentali, confrontati tra loro e collocati in precisi ambiti del più ampio contesto teorico. La seconda parte è invece dedicata alla presentazione dei cosiddetti Latent Space Models, una speciale classe caratterizzata dalla presenza di variabili latenti utilizzate per esprimere la verosimiglianza delle reti osservate. Partendo dai dati relativi ad una struttura di tipo grafo, l'obiettivo di questi modelli consiste nel mappare la rete nello spazio latente affinché siano rispettati determinati vincoli di natura probabilistica. Le posizioni latenti stimate possono essere successivamente utilizzate per individuare clusters e raggruppare quindi tra loro nodi strutturalmente simili, offrendo pertanto un'alternativa interessante ad algoritmi pensati per il rilevamento di comunità. Nei capitoli sono contenuti esempi di analisi su datasets di riferimento, utilizzati per testare le performance dei Latent Space Models e preparare infine la discussione di un'applicazione innovativa tratta da un contesto particolarmente attuale.