Studio della betweenness centrality e valutazione sperimentale dell'algoritmo SILVAN su reti complesse

La betweenness centrality (BC) è una metrica che misura la centralitá dei nodi in una rete, ovvero quanto sono importanti o centrali per i cammini minimi di un grafo. Nello studio e analisi di reti, la betweenness centrality é una metrica particolarmente importante perché permette di individuare i nodi chiave, ad esempio nella diffusione delle informazioni in un grafo. In questa tesi si fornisce una descrizione dell’algoritmo per il calcolo esatto della BC e si introducono degli algoritmi rigorosi per il calcolo approssimato della BC, i quali sono piú efficienti dal punto di vista computazionale e quindi preferibili per lo studio di reti complesse e di grandi dimensioni. Con particolare attenzione la tesi prende inconsiderazione SILVAN, un algoritmo in grado di stimare la BC utilizzando la tecnica del progressive sampling e concetti avanzati di statistical learning. Vengono inoltre analizzati alcune reti di grandi dimesioni mostrando come SILVAN é uno stimatore efficiente e rigoroso della BC.