• block centric
• community detection
• edge betweenness
• label propagation

Lo scopo di questa tesi è quello di proporre una versione distribuita di Label propagation sfruttando un approccio block-centric.
La tesi è strutturata come segue: in una prima fase evidenzieremo quale è lo stato dell’arte nel mondo della community detection, e per farlo introduremo ed utilizzeremo le varie metadefinizioni del termine ’Community’. Vedremo come le diverse caratteristiche che descrivono le community influenzano la tipologia di algoritmo che possono essere utilizzati per l’estrazione.
Gli algoritmi a loro volta verranno classificati sulla base delle logiche di estrazione che utilizzano e sulla tipologia di input per cui sono predisposti. A conclusione del capitolo 2 viene effettuato un confronto tra la metodologia Vertex Centric e Block Centric introdotto da una breve panoramica sui big data.
Nel capitolo 3 analizzeremo due noti algoritmi di community scelti appositamente in quanto adottano differenti logiche di estrazioni delle comunità: Edge Betweenness e Label Propagation. Alla fine delle valutazioni dei due algoritmi e per via delle apposite conclusioni ne viene scelto uno con lo scopo di rivisitarlo in ottica Block Centric, la scelta nel nostro caso ricade su Label Propagation.
Nel capitolo 4 viene proposta ed analizzata una versione block centric di Label Propagation.
Nel capitolo 5 affrontiamo da un punto di vista prettamente tecnico l’implementazione della Block Centric Label Propagation; verranno mostrati gli strumenti utilizzati per generare le partizioni dei grafi, implementare l’algoritmo distribuito ed infine testarlo. Il capitolo si conclude con le dovute valutazioni.
Il capitolo 6 è lasciato alle conclusioni del lavoro svolto e ai possibili sviluppi futuri che ne potrebbero derivare a partire dai risultati ottenuti in questa tesi.