ETD

Archivio digitale delle tesi discusse presso l'Università di Pisa

Tesi etd-02112018-093823


Tipo di tesi
Tesi di laurea specialistica
Autore
TIRALOSI, CHRISTIAN
URN
etd-02112018-093823
Titolo
Block centric label propagation: analisi ed implementazione
Dipartimento
INFORMATICA
Corso di studi
TECNOLOGIE INFORMATICHE
Relatori
relatore Prof.ssa Ricci, Laura Emilia Maria
relatore Dott.ssa Guidi, Barbara
Parole chiave
  • edge betweenness
  • label propagation
  • community detection
  • block centric
Data inizio appello
02/03/2018
Consultabilità
Completa
Riassunto
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.
File