• SBM
• R
• community detection
• walktrap

La community detection, ovvero l'identificazione dei gruppi di elementi all'interno di insiemi complessi, è un strumento fondamentale al fine di ottenere una conoscenza approfondita del sistema e della sua struttura. Il problema di identificare le comunità non è ben definito, pertanto si rendono necessari metodi diversi in funzione del tipo di ricerca che viene affrontata.
Lo strumento cardine di questo tipo di ricerca è la teoria dei grafi. Con questo tipo di rappresentazione si riescono a schematizzare un gran numero di sistemi.
L’esecuzione di un’analisi efficiente sta assumendo un’importanza sempre maggiore all’interno di un mondo digitale, caratterizzato da una crescente capacità di raccolta di immense quantità di dati.
Argomento di questa trattazione è lo studio di alcuni metodi per la community detection, applicati al fine di individuare migliori modalità di classificazione e catalogazione di reperti archeologici di ceramica risalenti ad un periodo compreso fra il primo secolo a.C. ed il terzo secolo d.C.. La raccolta dati, gestita dalla facoltà di Archeologia dell'Università di Pisa, nell'ambito del progetto europeo ArchAIDE, mira a sviluppare un programma in grado di identificare automaticamente i frammenti ceramici, migliorando i sistemi di datazione e riconoscimento. Lo studio è stato svolto con il coordinamento e sotto la supervisione del dottor Nevio Dubbini e del dottor Gabriele Gattiglia.
Nella prima parte sono analizzati vari metodi di community detection. In particolare, utilizzando un modello di grafi aleatori detto Stochastic Blockmodels, sono trattati due modelli che massimizzino rispettivamente la verosimiglianza e una funzione di qualità specifica e due test statistici per la determinazione del numero delle classi; attraverso un approccio basato sulle passeggiate aleatorie viene descritto l'agoritmo Walktrap, illustrandone i collegamenti con i metodi spettrali.
Nella seconda parte è presentata la sperimentazione dei test e degli algoritmi esposti in tesi su grafi sintetici. Successivamente è presente la sperimentazione sui dati reali di alcuni degli algoritmi di clustering e della distanza fra comunità.