Metodi per la prevedibilità di connessioni e comunità nei grafi random

Questa tesi introduce e analizza il metodo della perturbazione spettrale (SPM) per la predicibilità dei collegamenti, testandolo su reti sintetiche generate tramite il modello stocastico a blocchi (SBM). Si confronta SPM con un algoritmo non spettrale basato sull’inferenza della struttura comunitaria della rete, impiegando tecniche della meccanica statistica applicata ai sistemi complessi. La tesi si articola in cinque capitoli. Il primo offre una panoramica sulla teoria dei grafi, includendo concetti come la distribuzione del grado, la connettività e le reti bipartite, e definisce alcuni modelli generativi di reti casuali come l' Erdős-Rényi e ll modello SBM. Il secondo capitolo introduce elementi di meccanica statistica l' algoritmo di belief propagation (BP) per il calcolo dei marginali di una distribuzione di Boltzmann. Nel terzo capitolo si esaminano le applicazioni pratiche e i limiti del metodo BP applicato al problema della community detection su reti, illustrando l'implementazione in Python. Il quarto capitolo dettaglia il metodo SPM, con esempi di applicazione e valutazione sperimentale. Infine, nel quinto capitolo, si discutono le applicazioni pratiche del metodo SPM, confrontando i risultati ottenuti su vari dataset di reti generate. L’obiettivo è fornire un quadro complessivo del metodo SPM per la previsione dei collegamenti, evidenziando criteri di valutazione e aspetti statistici.