Dipartimento di Informatica
Corso di Laurea in Tecnologie Informatiche
Relazione finale
Block centric label propagation:
analisi ed implementazione
Christian Tiralosi
Relatori:
Prof.ssa Laura Ricci Dott.ssa Barbara Guidi
1
1 Introduzione 6
2 Stato dell’arte 10
2.1 Meta definizioni . . . 12
2.2 Caratteristiche delle community . . . 14
2.3 Principali classificazioni . . . 16
2.4 Big Data analytics . . . 22
3 Algoritmi di Community Detection 25 3.1 Edge Betweenness . . . 25
3.2 Label Propagation . . . 34
3.3 Scelta dell’algoritmo . . . 45
4 Block centric label propagation 47 5 Descrizione tecnica 55 5.1 PeerSim . . . 55
5.2 Partizionatori . . . 58
5.3 Strutturazione del progetto . . . 60
5.4 Valutazioni . . . 70
6 Conclusioni 78
Bibliografia 81
Elenco delle tabelle
2.1 Modellazione di un grafo . . . 12
2.2 Algoritmi di tipo Feature distance . . . 17
2.3 Algoritmi di tipo Internal density . . . 18
2.4 Algoritmi di tipo Bridge detection . . . 19
2.5 Algoritmi di tipo Diffusion . . . 19
2.6 Algoritmi di tipo Closeness . . . 20
2.7 Algoritmi di tipo Structure . . . 20
2.8 Algoritmi di tipo Link clustering . . . 21
2.9 Algoritmi di tipo Meta clustering . . . 21
4.1 Rappresentazione di una edge list . . . 48
4.2 Esempio di notazione su due partizioni di un grafo . . . 50
5.1 Configurazione . . . 69
3.1 Un grafo su cui eseguire Edge betweennes . . . 26
3.2 Prima iterazione di Edge betweennes . . . 27
3.3 Seconda iterazione di Edge betweennes . . . 28
3.4 Terza iterazione di Edge betweennes . . . 29
3.5 Community estratte da Edge betweennes . . . 29
3.6 Il dendogramma ottenuto da Edge betweennes . . . 30
3.7 Un grafo su cui eseguire BFS . . . 30
3.8 Riorganizzazione di un grafo per BFS . . . 31
3.9 Calcolo dei valori di edge betweennes . . . 32
3.10 Oscillazione delle etichette su Label Propagation . . . 36
3.11 Aggregazione di due soluzioni . . . 41
3.12 Esecuzione algoritmo senza il parametro soglia . . . 43
3.13 Prima iterazione di Label Propagation . . . 44
3.14 Seconda iterazione di Label Propagation . . . 45
3.15 Ultima iterazione di Label Propagation . . . 45
4.1 Esempio di un grafo . . . 47
4.2 Il grafo partizionato su due nodi . . . 51
4.3 Inizializzazione delle etichette . . . 52
4.4 Prima iterazione di Block Centric Label Propagation . . . 52
4.5 Seconda iterazione di Block Centric Label Propagation . . . . 53
4.6 Scambio di etichette tra nodi . . . 53
4.7 Ultima iterazione di Block Centric Label Propagation . . . . 54
5.1 PeerSim cycle-based . . . 56
ELENCO DELLE FIGURE 5
5.2 PeerSim event-based . . . 57
5.3 Le interfacce di PeerSim . . . 57
5.4 Partizioni Metis - costo dell’algoritmo . . . 71
5.5 Partizioni Module - costo dell’algoritmo . . . 71
5.6 Partizioni Metis - n° di communities estrapolate . . . 72
5.7 Partizioni Module - n° di communities estrapolate . . . 73
5.8 Partizioni Metis - n° di iterazioni . . . 74
Introduzione
Negli ultimi anni lo studio e l’analisi delle reti complesse ha interessato gran parte del mondo della ricerca, fornendo nuovi spunti e riflessioni per la com-prensione dei fenomeni ad esse collegati. Lo studio di sistemi complessi trova applicazione in svariati campi: reti neurali, modelli di traffico, reti sociali ed organismi biologici[21, 8].
Grazie all’avvento dei social media, le reti complesse create a partire da legami sociali (reti sociali) hanno avuto uno sviluppo sempre crescen-te. L’analisi di tali reti è importante per comprendere le dinamiche delle attività umane, come ad esempio la creazione di nuove connessioni oppure l’aggregazione di persone in gruppi definiti community.
Le community in particolare possono fornire informazioni su diverse cat-teristiche delle reti complesse. Il concetto di community è legato alla classi-ficazione delle entità di interesse. La definizione di community dipende dal contesto e può essere sinonima di modulo, classe, gruppo o cluster.
In generale una community è definita come un sottoinsieme di nodi all’in-terno di un grafo, in cui le connessioni tra i nodi all’inall’in-terno del sottoinsieme sono più dense rispetto alle connessioni verso i nodi presenti nel resto del grafo[12].
L’individuazione di una community è una procedura molto complessa che richiede informazioni sull’interno il grafo da analizzare. Molti sono gli algoritmi presenti in letteratura e che sono stati proposti negli anni[3, 7, 10].
CAPITOLO 1. INTRODUZIONE 7 Il continuo sorgere di metodologie ed approcci allo studio delle community contribuisce e rafforza il legame tra gli studi sociologici delle relazioni sociali e gli studi analitici sulle rilevazioni delle community.
Dal punto di vista prettamente informatico l’estrapolazione delle commu-nity si traduce nell’analisi dei dati che descrivono la rete stessa, nell’applica-zione di algoritmi appositamente sviluppati e nella valutanell’applica-zione della bontà dei risultati ottenuti.
Gli algoritmi attualmente proposti sono molteplici e svariati: spesso si differenziano tra di loro sulla base delle tipologie di community che si vogliono estrapolare, dei dati che si vogliono analizzare e sulla base della complessità computazionale[1].
Tra questi, data la sua estrema semplicità, uno dei più utilizzati è Label Propagation[10]. Questo algoritmo lavora sulle etichette dei vertici del grafo, ad ogni iterazione per ogni vertice del grafo calcola l’etichetta maggiormente diffusa tra i vertici vicini, se l’etichetta del vertice differisce da quella calcolata questa viene aggiornata con quella calcolata. La procedura termina non appena tutti i vertici non necessitano più aggiornamenti alle etichette.
Una forte limitazione all’individuazione delle community riguarda la com-plessità degli algoritmi proposti per questo tipo di problema, considerando le dimensioni di molte reti complesse che possono raggiungere bilioni di archi e vertici, come ad esempio Facebook. Generalmente, gli algoritmi proposti non sono distribuiti, richiedono la presenza di tutto il grafo in memoria e sono single-thread[14].
Per questo motivo molti algoritmi di community detection sono stati proposti in una versione parallela[15, 17].
Lo scopo di questa tesi è proporre una versione parallela della Label propagation sfruttando un approccio block-centric.
Per fare ciò descriveremo lo stato dell’arte relativo al campo della com-munity detection e mostremo le possibili varianti del termine ’Comcom-munity’, classificheremo una serie di algoritmi utilizzati nella community detection e tra quelli presenti ne estrarremo due appartanenti a categorie differenti: Edge Betweenness e Label Propagation.
parti-re dalla nota versione di questo algoritmo proporparti-remo ed analizzeparti-remo una versione parallela. Poichè l’algoritmo proposto dovrà essere eseguito in un ambiente parallelo, occorrerà considerare il partizionamento del grafo da cui estrarre le community.
Proporremo due differenti tipologie di partizionamento ai fini di capire come si comporta l’algoritmo al variare di esse. La versione block centric di Label Propagation verrà successimente implementata in Java utilizzando un framework per la simulazione di software distruibuito.
L’idea di fondo su cui abbiamo basato l’analisi e l’implementazione di Block Centric Label Propagation è quella di distribuire il calcolo di tutte le community di un grafo su diversi nodi di elaborazione. Per fare questo partizioniamo il grafo che vogliano analizzare.
Su ogni nodo di elaborazione viene attivata un istanza dell’algoritmo pa-rallelo il cui compito iniziale sarà quello di prendersi in carico una partizione. Quando tutti i nodi saranno stati inizializzati con la loro partizione di grafo, questi eseguiranno una serie di iterazioni locali emulando Label Propagation. Per iterazioni locali intendiamo una serie di aggiornamenti di etichette effettuata senza disporre della totalità delle informazioni necessarie; ogni nodo aggiornerà le proprie etichette pur non avendo a disposizione tutte le etichette dei vertici vicini. Alcune di queste possono essere mantenute da altri nodi di elaborazione.
Le iterazioni locali vengono intervallate da alcune iterazioni con cui i vari nodi di elaborazione si scambiano le etichette di cui necessitano, si pensi a due vertici vicini (connessi da un arco) ma assegnati a partizioni differenti.
Le iterazioni locali e di scambio vengono a loro volta intervallate da itera-zioni con cui si procede a validare la condizione di terminazione, condizione per cui nessun vertice necessita l’aggiormanento dell’etichetta.
Validata la condizione di terminazione tutte le informazioni generate lo-calmente ai nodi di elaborazione vengono fatte confluire in modo da porter ottenere un unico elenco di community presenti nel grafo iniziale.
La tesi è strutturata come segue: in una prima fase evidenzieremo quale è lo stato dell’arte nell’ambito della community detection, e per farlo introdure-mo ed utilizzereintrodure-mo le varie metadefinizioni del termine ’Community’.
Vedre-CAPITOLO 1. INTRODUZIONE 9 mo come le diverse caratteristiche che descrivono le community influenzano le tipologie di algoritmo che possono essere utilizzate 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 appo-sitamente in quanto adottano differenti logiche di estrazioni delle community: Edge Betweenness[8] e Label Propagation[10]. Alla fine delle valutazioni dei due algoritmi 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’im-plementazione della Block Centric Label Propagation; verranno mostrati gli strumenti utilizzati per generare le partizioni dei grafi, implementare l’algo-ritmo distribuito ed infine testarlo. Il capitolo si conclude con lun insieme di valutazioni.
Stato dell’arte
In questo capitolo basandoci su un’esaustiva survery abbiamo potuto estra-polare lo stato dell’arte riguardo l’argomento in questione, abbiamo esposto quanto concerne le svariate metadefinizioni di community, le caratteristiche che le descrivono e le categorie in cui ricadono gli algoritmi sviluppati per la community detection.
Una panoramica sugli algoritmi maggiormente utilizzati nell’ambito ci è servita a poter effettuare una classificatzione di essi sulla base della tecnica che adottano per l’estrazione delle community.
Dalle varie classificazioni abbiamo scelto alcuni algoritmi in modo da approfondirli scendendo nel dettaglio e spiegandone i vari passaggi sulla base del loro pseudo codice.
Infine tra gli algoritmi approfonditi ne abbiamo selezionato uno e di que-sto abbiamo progettato, implementato e valutato una versione block centric. Con il termine ’Community’ spesso ci riferiamo ad un insieme di persone che condividono hobbies, passioni, immagini, video ed opinioni. Le commu-nity sono uno dei fenomeni più studiati come strutture nascoste all’interno di reti complesse.
Una community può essere definita in diversi modi, quello più semplici-stico definisce la community come un gruppo di entità che interagiscono tra di loro ed hanno delle proprietà in comune.
Si intuisce facilmente che lo scopo della community detection è quello
CAPITOLO 2. STATO DELL’ARTE 11 di estrapolare le community all’interno di strutture complesse. L’estrazione delle community ha diversi aspetti in comune con il data mining; essa in effetti può essere vista come un’analisi di data mining applicata sui grafi.
Esistono svariati algoritmi di community detection il cui compito gene-ralmente è quello di suddividere i vertici di un grafo in k gruppi, cercare di massimizzare il numero di archi interni ai singoli gruppi e di minimizzare il numero di archi tra vertici appartenenti a gruppi differenti.
Saranno proprio i gruppi ottenuti dalla detection che formeranno le com-munity del grafo. La definizione di comcom-munity sopracitata viene spesso ri-formulata sulla base della tipologia di community che si sta analizzando; le community infatti hanno diverse caratteristiche, si pensi ad esempio a community gerarchiche per cui vi sono dei gruppi composti a loro volta da sottogruppi di vertici o a community sovrapposte per cui vi sono vertici che appartengono contemporaneamente a due o più gruppi.
In alcuni casi le community possono essere dinamiche per cui durante un intervallo di tempo alcuni vertici possono variare il gruppo di appartenenza, in altri casi potrebbero presentare un fattore multirelazionale, caso in cui diversi vertici si considerano collegati tra di loro solamente quando viene presa in evidenziata una specifica relazione.
Il grafo in alcuni casi può utilizzare archi orientati per cui le relazioni tra i vertici assumono una diversa importanza sulla base del verso di percorrenza dell’arco stesso.
Grazie alla review ’A classification for Community Discovery Methods in Complex Networks’[1] è stato possibile analizzare e valutare alcuni tra gli algoritmi attualmente utilizzati per la community detection.
La review è strutturata quasi come un manuale utente volto alla risolu-zione dei problemi comuni allo studio delle community; propone inoltre una serie di definizioni e classificazioni di community basandosi sulla metodolo-gia con cui queste vengono ricercate e sulla tipolometodolo-gia di community a cui la ricerca si volge.
Quando trattiamo un problema di community detection è utile ricondurre il nostro modello dati ad un grafo. Definiremo G il grafo rappresentato dalla
quadrupla C = (V, E, L, C), indicheremo con V l’insieme di vertici etichettati, con E l’insieme degli archi etichettati, con L l’insieme delle etichette degli archi e con C l’insieme delle etichette dei vertici.
L’insieme E a sua volta è rappresentato dalla quadrupla (u, v, l, w) dove u e v sono vertici, l è un’etichetta e w rappresenta il peso dell’arco. Si assume che nel’insieme E possa esistere solo una coppia (u,v) per cui le quadruple (u,v,l,w) e (v,u,l,w) sono da considerarsi distinte. Ogni nodo del grafo può essere etichettato con una o più etichette dell’insieme C. Nei casi in cui non è necessario tenere in considerazione la rilevanza dell’arco andrà impostato w = 1.
E’ possibile tenere in considerazione anche l’evoluzione temporale del gra-fo etichettatando ogni vertice ed arco con una serie di timestamp. Si noti che i vertici possono introdurre e variare la loro etichetta oltre ad introdurre o rimuovere archi all’interno del grafo. Il modello descritto è sufficiente a rappresentare tutte le possibili varianti dei reali casi d’uso.
Per completezza riportiamo la rimanente notazione che ci permetterà di descrivere un grafo nella sua interezza:
n il numero dei vertici m il numero degli archi
k il numero di community |K| il grado medio del grafo
K il grado massimo del grafo
T il numero massimo di azioni nella rete A il numero massimo di azioni per un vertice D il numero di dimensioni
c il numero di tipologie di vertici t il numero di istanti temporali
Tabella 2.1: Modellazione di un grafo
2.1
Meta definizioni
Come già introdotto nel capitolo precedente suddivideremo i più diffusi al-goritmi di community detection sulla base di una classificazione e basandoci
CAPITOLO 2. STATO DELL’ARTE 13 sulla meta definizione di community:
«Una community in una rete complessa è un insieme di entita che con-dividono alcuni insiemi di azioni correlate tra di esse con altre entità della community. Si da quindi molta rilevanza alla connessione diretta tra entità e si considera questa come una tipologia di azione»
Di seguito le varie definizioni di community che possiamo distinguere:
Definizione di community basata sulla densità
Generalmente la definizione di community è basata sulla topologia degli archi della rete, infatti la community viene definita come un gruppo all’in-terno di cui vi sono molti archi che uniscono i vari vertici e al contempo vi sono pochi archi che uniscono i vari gruppi (si intendono archi che uniscono vertici appartenenti a gruppi differenti).
Sulla base della definizione di community che abbiamo dato, la connessio-ne tra due vertici è considerata una particolare tipologia di azioconnessio-ne; tentando quindi di suddividere i vertici nei vari gruppi massimizzando le azioni che hanno in comune, stiamo massimizzando il numero di archi interno alle com-munity. Da questa affermazioni prende spunto la definizione di community basata sulla densità, si cerca di massimizzare la densità degli archi interni alle community.
E’ possibile anche considerare diverse tipologie di archi come differen-ti azioni, questa variante implica che gli stessi nodi possono appartenere a community differenti sulla base della tipologia di azione che viene presa in considerazione.
Definizione di community basata sulla similarità dei vertici
Tra i vari possibili fattori da poter prendere in considerazione nella defini-zioni di una community vi è la similarità dei vertici, risulta molto realistica la supposizione che se due vertici sono simili tra di loro, prendendo in consi-derazione una proprietà locale o globale di riferimento, questi appartengano allo stesso gruppo, siano essi collegati o meno da un arco. Come proprietà di riferimento è possibile prendere anche solamente la presenza o meno di un’etichetta del vertice o il valore associato ad essa.
Definizione di community basata sulle azioni
Ponendo maggiore attenzione sull’utilizzo delle azione nella community detection, possiamo pensare di raggruppare i vertici di un grafo sulla base delle azioni che questi intraprendono. Un caso reale potrebbe essere quello per cui due utenti di un grafo sono considerati facenti parte dello stesso gruppo se eseguono le stesse ricerche (query).
Questa definizione di community racchiude due possibili varianti: la pri-ma considera appartenenti allo stesso gruppo i vertici di un grafo che eseguono le stesse azioni e che non necessariamente presentano archi diretti tra di loro, la seconda variante considera dello stesso gruppo i vertici di un grafo che eseguono le stesse azioni e che sono collegati tra di loro tramite archi diretti.
Definizione di community basata sull’influenza di propagazione Una caratteristica di alcune tipologie di grafo è quella di presentare al loro interno un insieme ristretto di vertici che sono in grado tramite le loro azioni di influenzare il comportamento di altri vertici.
Questa tipologia di vertici viene chiamata ’leader’. A seguito di un’azione intrapresa da un vertice leader all’interno di un grafo, è possibile considerare appartenenti allo stesso gruppo tutti quei vertici che entro un determinato lasso di tempo hanno intrapreso la stessa azione del vertice leader. Questa definizione di community si presta bene a descrivere reti di legami sociali.
2.2
Caratteristiche delle community
Le caratteristiche presenti in una community sono svariate, ai fini di una classificazione terremo conto solamente di quelle utili a valutare gli algorit-mi di community detection presentati nella survery. Iniziamo illustrando le caratteristiche delle community che vengono coinvolte anche dai problemi di rappresentazione del modello.
Overlapping
Questa caratteristica è molto interessante soprattutto per quanto riguarda le rappresentazioni di casi reali dove spesso le varie community di un grafo
CAPITOLO 2. STATO DELL’ARTE 15 condividono uno o più vertici. Si pensi ad esempio ad un social network dove un utente appartiene a più gruppi contemporaneamente, famiglia, lavoro, amici. Evidenzieremo gli algoritmi che gestiscono questa caratteristica.
Orientamento
Alcune rappresentazioni di casi reali fanno uso di archi orientati, siamo nel caso in cui l’orientamento dell’arco esprime una precisa relazione tra due vertici ed esclude la reciprocità. Possiamo prendere ad esempio un grafo di pagine web per cui esiste un collegamento dalla pagina A alla pagina B e non esiste il collegamento inverso. Daremo opportuna evidenza degli algoritmi che gestiscono questa caratteristica.
Presenza di pesi
Nei casi in cui la rappresentazione del grafo preveda anche gli archi pesati potremmo voler estrapolare solamente le community del grafo il cui peso degli archi supera una certa soglia. In questo modo è possibile dar luogo a differenti community con il variare della soglia.
Dinamicità
Sulla base della definizione di community data che abbiamo precedente-mente visto che in un certo intervallo di tempo alcuni archi possono essere introdotti e rimossi dal grafo; un’ulteriore caratteristica da poter gestire negli algoritimi di community detection.
Le restanti caratteristiche che elencheremo si riferiscono principalmente alla tipologia di input che viene fornita agli algoritmi di community detection tramite la rappresentazione del modello.
Parameter free
In alcuni casi gli algoritmi di community detection lavorano direttamen-te con il grafo otdirettamen-tenuto in input, non sono necessari uldirettamen-teriori parametri da settare all’algoritmo.
Input multidimensionale
Ci troviamo nel caso di input multidimensionale quando il grafo che stiamo descrivendo presenta un numero di tipologie di relazione superiore ad uno. Ad esempio su uno stesso vi sono associate più proprietà o nel grafo esistono diverse tipologie di archi.
Input incrementale
Alcuni algoritmi sono in grado di gestire un input incrementale; l’algorit-mo inizia a restituire soluzioni senza aver effettuato una scansione esaustiva dell’input. Si pensi ad un algortimo che per inserire un vertice all’interno di un dato gruppo verifica solamente i vertici vicini (o eventualmente i vertici che distano 2 hop).
Input multipartito
Diversi algoritmi lavorano anche sulla proiezione bipartita dei grafi in modo da sfruttare la computazione in modo efficiente. La multidimensionalità dei grafi viene quindi inclusa come una caratteristica dell’input.
2.3
Principali classificazioni degli algoritmi di
community detection
Procediamo col classificare i principali algoritmi di community detection prendendo in considerazione la definizione di comunity che essi utilizzano.
Gli algoritmi sono stati inglobati in determinate categorie in quanto con-dividono le condizioni necessarie per far sì che un gruppo di entità possa essere clusterizzato in una community.
Questa classificazione ci consente di avere una visione più ad alto livello delle possibili tecniche adottate dagli algoritmi di community detection. Ogni categoria presentata verrà seguita da una tabella in cui mostriamo una serie di algoritmi che ve ne fanno parte e per ognuno di essi specifichiamo quali caratteristiche presentano.
CAPITOLO 2. STATO DELL’ARTE 17 Le caratteristiche Overlapping (Ov), Orientamento (Or), Presenza di pesi (Pe), Dinamicità (Di), Parameter free (Pf), Multidimensionale (Md), Input incrementale (In) ed Input Multipartito (Mp) sono quelle descritte nel para-grafo precedente. Al tempo stesso va detto che queste classificazioni di algo-ritmi non sono esclusive, motivo per cui in alcuni casi l’approcio adottato da alcuni algoritmi potrebbe essere inglobato da più classificazioni.
Feature distance
In questa categoria ricadono tutti quegli algoritmi la cui definizione di community si basa sul fatto che i membri di un gruppo condividono un esatto insieme di caratteristiche. Definiamo le caratteristiche come una serie di attributi associati ad un arco o ad un vertice.
Questa tipologia di algoritmi trattano la community detection come un classico problema di data minig, MDL Minimum Description Lenght ne è un esempio.
Possiamo definire le community estratte tramite questa tiplogia di proce-dure come Feature Community e descrivere la meta procedura che accomuna questa categoria di algoritmi nel seguente modo: dato un insieme di entità con i loro attributi, siano esssi relazioni, azioni o proprietà, va generata una matrice di valori su cui potervi applicare tecniche di clusterizzazione.
Algoritmo Ov Or Pe Di Pf Md In Mp Complessità
Evolutionary* ! ! O(n2)
MSN-BD ! ! O(n2ck)
SocDim ! ! ! O(n2 log n)*
PMM ! ! O(mn2)
MRGC ! ! ! ! O(mD)
Infinite Relational ! ! O(n2cD)
Find-Tribes ! ! O(mnK2)
AutoPart ! ! ! O(mk2)
Timefall ! ! ! O(mk)
Context-specific Cluster Tree ! ! O(mk)
Internal density
Gli algoritmi associati a questa categoria lavorano tramite un processo di esplorazione del grafo guidato esclusivamente dalla ricerca delle aree più dense del grafo. Difatti si definisce una Dense Community un insieme di entità densamente connesse tra di loro, per essere definito tale, il numero di archi che li collega deve essere nettamente superiore al numero di archi di un grafo random.
Questa tipologia di algoritmi lavora in modo da espandere o collassare le partizioni di nodi in modo da ottimizzare la funzione che ne calcola la densità, ad ogni variazione delle partizioni si ricalcola la funzione finchè non non è più possibile ottenere margini di miglioramento.
Algoritmo Ov Or Pe Di Pf Md In Mp Complessità
Modularity ! ! ! ! ! ! O(mk log n)
MetaFac ! ! O(mnD)
Variational Bayes ! ! O(mk)
LA → IS2* ! ! O(mk + n)
Local Density ! ! ! O(mk log n)
Tabella 2.3: Algoritmi di tipo Internal density
Bridge detection
Il concetto di base che accomuna gli algoritmi di questa categoria è che le community sono delle aree dense del grafo collegate tra di loro da un bas-so numero di archi. Gli archi in questione giocano un ruolo fondamentale in quanto necessari a far veicolare le informazioni da una community all’al-tra. Questi archi vegono chiamati bridge e la rimozione di questi consente l’estrazione delle singole community del grafo.
Questa procedura definisce un’apposita misura per valutare il fattore di contribuzione degli archi, per poivalutare quanto vertici e archi del grafo contribuiscono a mantenere il grafo connesso. Infine la procedura rimuove iterativamente gli archi bridge, ovvero quelli con fattore di contribuzione più
CAPITOLO 2. STATO DELL’ARTE 19 basso, in modo da estrarre le community.
Algoritmo Ov Or Pe Di Pf Md In Mp Complessità
Edge Betweenness ! ! O(m2n)
CONGO* ! ! O(n log n)
L-Shell ! ! O(n3)
Internal-External Degree ! ! O(n2 log n)
Tabella 2.4: Algoritmi di tipo Bridge detection
Diffusion
Fanno parter della categoria Diffusion gli algoritmi che utilizzano il concet-to di Diffusion Community. Le Diffusion community sono formate da gruppi di vertici che reagiscono allo stesso modo a seguito di determinati eventi. Un evento ad esempio può riguardare la variazione di una determinata proprietà del grafo visibile a tutti i vertici o alla variazione di una proprietà presente solamente su un insieme ristretto di vertici (detti anche vertici sorgenti).
Questa tipologia di algoritmi itera un processo di propagazione sul grafo, sia esso a livello globale di grafo che a livello locale di vertici, per poi rag-gruppare tutti i vertici che dopo aver reagito alla propagazione si trovano nello stesso stato.
Algoritmo Ov Or Pe Di Pf Md In Mp Complessità
Label Propagation ! ! O(m+n)
Node Colouring ! ! O(mtk2)
Kirchhoff ! ! O(m+n)
GuruMine ! ! O(T An2)
DegreeDiscountIC ! O(k log n + m)
MMSB ! ! O(nk)
Tabella 2.5: Algoritmi di tipo Diffusion
Closeness
community basandosi sul concetto che queste sono rappresentate dai quei gruppi di vertici che tra di loro distano al più pochi hop. Small World Com-munity è come vengono definiti gli insiemi di vertici estratti dalle procedure adottate da questa tipologia di algoritmi.
La loro caratteristica è quella di essere formate da vertici la cui distanza in termini di hop è nettamente minore alla media degli hop degli shortest path del grafo. La procedura adottata da questo tipo di algoritmi esegue una serie di cammini casuali sul grafo e raggruppa tutti quei nodi che fre-quentemente vengono raggiunti nei cammini.
Algoritmo Ov Or Pe Di Pf Md In Mp Complessità
Walktrap ! O(mn2)
DOCS !
-Infomap ! ! ! O(m log2 n)
Tabella 2.6: Algoritmi di tipo Closeness
Structure
Rientrano in questa categoria gli algoritmi che definiscono la community come un gruppo di vertici la cui struttura segue un preciso schema.. Gli algortimi defiiscono determinati template di archi e tentano di applicarli agli archi ed ai vertici del grafo.
Tipicamente la procedura adottata da questo tipo di algoritmi definisce a priori l’esatta quantità di archi che devono essere presenti trai i vertici e come questi devono essere distribuiti trai i vertici. Solamente i gruppi di archi che soddisfano queste condizioni vengono considerati Structure Community.
Algoritmo Ov Or Pe Di Pf Md In Mp Complessità
K-Clique ! O(mlnm
10 )
S-Plexes Enumeration ! O(kmn)
Bi-clique ! ! O(m2)
EAGLE ! ! ! O(3 n
3) Tabella 2.7: Algoritmi di tipo Structure
CAPITOLO 2. STATO DELL’ARTE 21 Link clustering
Questa categoria di algortimi viene vista come una proiezione del problema di community detection, difatti le procedure adottate non lavorano sui vertici bensì alla clusterizzazione degli archi del grafo.
L’idea di base sta nel clusterizzare le relazioni (archi) presenti nel grafo sulla base della loro similarità, successivamente vengono connessi i vertici alle relazioni a cui appartengono in modo da formare le community. Nel caso specifico si definisce Link Community un insieme di vertici che condividono un certo numero di relazioni raggruppate.
Algoritmo Ov Or Pe Di Pf Md In Mp Complessità
Link modularity ! ! ! O(2mk log n)
HLC* ! ! ! O(n|K|2)
Link Maximum Likelihood ! O(mk)
Tabella 2.8: Algoritmi di tipo Link clustering
Meta clustering
Vi sono una serie di algoritmi che non si basano su una precisa definizione di community ma lavorano combinando i risultati di diversi approcci di com-munity detection. La definizione di Comcom-munity adottata da questa tipologia di algortimi risulta essere la più generica, difatti rientrano in essa tutti quegli insiemi che presentano un determinato numero di caratteristiche sulla base delle quali i vertici vengono raggruppati.
E’ chiaro e va detto che queste classificazioni di algoritmi non sono esclu-sive, motivo per l’approcio di alcuni algoritmi potrebbe essere inglobato da più classificazioni.
Algoritmo Ov Or Pe Di Pf Md In Mp Complessità
Hibrid* ! ! ! ! O(nk |K|)
Multirelational Regression ! !
-Hierarchichal Bayes O(n2)
Expectation Maximization !
2.4
Big Data analytics
Tra le parole chiave attuali una delle più diffuse è certamente il termine ’Big Data’. In realtà il concetto che si cela dietro ad essa è noto già da diversi anni ma solo la ricerca si è ampiamente occupata di questo campo, anche perchè si sta iniziando a comprenderne la loro importanza ed i campi di utilizzo.
La mole di dati che continuamente viene prodotta da qualsiasi rete, soft-ware, attività commerciale, se analizzatta adeguatamente può consentire ad un’azienda, un ente, un’organizzazione o semplicemente ad un ulteriore software di intraprendere decisioni cruciali e significative.
Quando ancora il termine ’Big Data’ non era contemplato, queste stesse decisioni a cui ci riferiamo venivano prese basandosi su semplici analisi nu-meriche effettuate su dei dataset limitati. Oggi la possibilità di mantenere ed analizzare enormi volumi di dati in modo efficiente ci permette di anticipare alcune scelte future in modo molto accurato.
Con il termine ’Big data analytics’ ci riferiamo al processo di raccolta ed analisi di grandi volumi di informazioni al fine di estrarre una serie di informazioni celate in esse. Quando si effettuano analisi accurate di questo tipo sui big data è possibile evincere informazioni che possono andare dal-le condizioni del mercato, ai possibili risultati di un’edal-lezione, dai gusti dei consumatori fino al comportamento di gruppi di persone, le community.
Lo studio dei grafi rientra tra quelli che si possono applicare sui big da-ta, sono difatti molteplici i dataset che vengono organizzati o rappresentati mediante grafi, per cui è possibile utilizzare le svariate tecniche di analisi dei grafi.
Gli algoritmi per elaborare grandi moli di dati o i framework utilizzati per implementare gli algoritmi stessi possono essere suddivisi in due macro cate-gorie in grado di descrivere il paradigma computazione adottato; possiamo definire queste macro categorie come:
vertex-centric block-centric
CAPITOLO 2. STATO DELL’ARTE 23 l modello di programmazione vertex-centric è il paradigma computazionale più consolidato, la logica di questo modello è quello di affidare l’elaborazio-ne delle informazioni dei singoli vertici del grafo ai vari nodi preposti alla computazione.
In pratica ad ogni vertice corrisponde un processo e contiene informazioni su se stesso e tutti gli archi uscenti dal vertice, i vari messaggi vengono scam-biati tra i singoli processi tramite meccanismi di comunicazione tra vertici o tramite meccanismi di condivisione di memoria.
Questo modello in determinate situazioni e per alcuni aspetti presenta dei punti critici, come ad esempio l’elaborazione di grafi reali, durante la quale è possibile imbattersi in scarse prestazioni spesso dovute alle logiche iterative presenti nelle procedure di elaborazione.
A differenze del modello vertex-centric, il block-centric affida a singoli nodi di elaborazione o processi la gestione di un blocco di vertici (una parti-zione del grafo), per cui l’unità di calcolo è il blocco e gli scambi di messaggi avvengono tra blocco e blocco.
Riferendoci ai framework vertex-centric possiamo citare GraphLab[15] ed Apache Giraph[19], entrambi consetono di modellare applicazioni con la logica del ’thinking like a vertex’ e rendere la progettazione degli algoritmi distribuiti in maniera più naturale e lineare.
GraphLab è un framework implementato in C++ che espone allo svi-luppatore una serie di astrazioni con cui definire i dati, la schedulazione delle attività da svolgere, gestire la computazione asincrona ed effettuare aggregazione dei dati.
Apache Giraph è un framework sviluppato per implementare algoritmi iterativi su grafi e basato su Apache Hadoop. L’input di una computazione su Giraph è un grafo composto da vertici e archi orientati dove ad ogni vertice e ad ogni arco è possibile associare un valore.
Le applicazioni in Giraph vengono seguono un iter ben preciso: nella fase iniziale tutti i vertici sono in uno stato attivo, poi ad ogni iterazione successiva (denominata superstep) ogni vertice attivo esegue il metodo Compute() la cui logica è stata definita dallo sviluppatore ed il cui risultato può fare variare lo stato del vertice.
Per quanto riguarda i framework block-centric possiamo citare Apache Spark[20] basato sul modello MapReduce ed in grado di supportare l’elabo-razione di dati su ambienti distribuiti.
Spark consente di sviluppare sia algoritmi iterativi su grafo che qualsiasi altro algoritmo data-flow.
Il framework è implementato in Scala per cui gli sviluppatori possono implementare i propri programmi in Scala, Java e in Python; lo sviluppatore si occupa di definire un driver che si connette ad un cluster di worker nodes e che poi effettua una serie di trasformazioni (map, filter, e join) ed azioni (count, reduce e collect) sui dati.
Capitolo 3
Algoritmi di Community
Detection
Dopo aver mostrato le diverse categorie di tecniche di community detec-tion, abbiamo deciso di approfondire due algoritmi appartenenti a due ca-tegorie differenti; per la categoria Bridge Detection abbiamo selezionato Edge Betweenness e per la categoria Diffusion abbiamo selezionato Label Propagation.
3.1
Edge Betweenness
L’algoritmo di Girvan-Newman[8] si basa sull’idea per cui se in un grafo vi sono presenti delle community queste sono lievemente connesse tramite pochi archi inter-group. La presenza di pochi archi inter-group implica che tutti i cammini che attraversano le diverse community devono necesariamente attraversare questi ultimi.
A differenza degli archi inter-group, quelli intra-group solitamente sono molto più densi all’interno di una community e di conseguenza i cammini minimi presenti tra i vertici del gruppo sono molteplici. L’algoritmo de-ve riconoscere gli archi inter-group e rimuode-verli progressivamente sulla base del loro valore di ’edge betweenness’ in modo da separare i vari gruppi, le community.
Per edge betweenness si intende la centralità degli archi, questo valore indica quanto sia centrale il ruolo di un arco del grafo nel connettere le possibili coppie di nodi presenti.
Definizione La betweenness di un edge è la quantità totale di flusso che un arco apporta tenendo conto del flusso apportato da tutti i cammini minini di tutte le coppie di nodi che lo attraversano.
Figura 3.1: Un grafo su cui eseguire Edge betweennes
Con riferimento alla Figura 3.1 calcoliano l’edge betweennes dell’arco (7,8). Vanno conteggiate tutte le unità di flusso apportate dai cammini mi-nimi che attraversano l’arco (7,8).
Ad esempio si considera 1 unità di flusso per il cammino che va dal vertice 1 al vertice 8.
A partire dal vertice 1 si conteggia 1 unità di flusso per ogni cammino che raggiunge i vertici (8 - 14); partendo dal vertice 1 ottenianmo quindi 7 unità di flusso.
Le stesse unità di flusso vanno conteggiate per tutti gli altri cammini che partono dai vertici (2 - 7). In totale otterremo 7x7= 49 unità di flusso.
CAPITOLO 3. ALGORITMI DI COMMUNITY DETECTION 27 Di seguito i passaggi che descrivono il funzionamento dell’algoritmo: Algoritmo 3.1 Edge Betweennes
1. ∀ arco e ∈ E si calcola l’edge betweennes.
2. Selezionare e rimuovere l’arco con la massima edge betweennes. 3. Ripetere il punto (1) finchè sono presenti archi nel grafo.
Si calcola l’edge betweennes di tutti gli archi del grafo in Figura 3.1, avremo che:
edge betweennes(7,8) = 7x7 = 49 edge betweennes(1,3) = 1x12 =12
edge betweennes(3,7), (6,7), (8,9), (8,12) = 33
A questo punto va rimosso l’arco con edge betweennes maggiore, in questo caso (7,8).
Figura 3.2: Prima iterazione di Edge betweennes
Rimosso l’arco (7,8) si procede a ricalcolare l’edge betweennes di tutti gli archi restanti:
edge betweennes(1,3) = 1x5 = 5
edge betweennes(3,7), (6,7), (8,9), (8,12) = 3x4 = 12
Vanno rimossi tutti gli archi con edge betweennes pari a 12 (3,7), (6,7), (8,9) e (8,12), il grafo ottenuto sara quello mostrato nella figura sottostante.
Figura 3.3: Seconda iterazione di Edge betweennes
L’ultimo passaggio effettuato dall’algoritmo consiste nel ricalcolo dell’ed-ge betweennes degli archi rimanenti:
edge betweennes degli archi (1,2), (1,3), (2,3), (4,5), (4,6), (5,6), (9,10), (9,11), (10,11), (12,13), (12,14), (13,14) = 1
CAPITOLO 3. ALGORITMI DI COMMUNITY DETECTION 29
Figura 3.4: Terza iterazione di Edge betweennes
Si rimuovono tutti gli archi restante in quanto presentano lo stesso valore di edge betweennes, l’algoritmo termina in quanto non vi sono più archi da esaminare.
Figura 3.6: Il dendogramma ottenuto da Edge betweennes
Rimuovendo tutti gli archi di fatto avremmo ottenuto n community quanti sono i vertici del grafo, ma se leggiamo i risultati ottenuti nei passaggi inter-medi (Figura 3.5) si ottiene un dendogramma da esplorare in verticale (Figu-ra 3.6). Vedremo in seguito come scegliere il miglior taglio/partizionamento ottenuto dall’algoritmo.
CAPITOLO 3. ALGORITMI DI COMMUNITY DETECTION 31 La peculiarità di questo algoritmo risiede nel fatto che, dopo aver calco-lato una prima volta la betweenness per ciascuna coppia di vertici ed aver eliminando l’arco con l’edge betweenness più alta, si procede ad un ricalcolo della betweenness di tutti gli archi prima di ripetere il procedimento di ta-glio, di fatto abbiamo visibilità di tutti i tagli effettuati. Se l’algoritmo non rieffettuasse il ricalcolo non avremmo la certezza di valutare la corretta edge betweenness di tutti gli archi di inter-group. E’ chiaro che la parte che incide maggiormente nella complessità dell’algoritmo è proprio il ricalcolo del peso dei link a ogni iterazione, e nel caso specifico di reti di elevate dimensioni o grafi sparsi, l’algoritmo ha una complessità O(n3). Dato che l’algoritmo di Girman-Newman ad ogni passo deve ricalcolare la betweenness di tutti gli archi rimanenti nel grafo e i suoi valori dipendono dal numero di cammini mi-nimi tra ogni coppia di vertici, vediamo come poter effettuare questo calcolo in maniera efficiente.
Figura 3.9: Calcolo dei valori di edge betweennes
L’idea è di effettuare una ricerca in ampiezza (BFS) a partire da ogni nodo in modo da calcolare come una singola unità di flusso si distribuisce nella rete a partire dal nodo in esame.
Per quanto riguarda i risultati ottenuti dall’algoritmo di Girman-Newman[8], abbiamo già visto che questo algoritmo restituisce una serie di partizioni che tendono ad aumentare la granularità delle community ottenute.
L’algoritmo non prevede ancora un sistema per determinare quando si è raggiunta il partizionamento ottimale del grafo, per cui dalla serie di risultati ottenuti si ottiente un dendogramma da interpretare.
Per fare ciò serve avere un criterio con cui stabilire quale è il miglior parti-zionamento restituto dall’algoritmo. Una possibilità è quella di valutare i vari livelli di partizionamento utilizzando una misura di bontà delle partizioni, la modularità.
CAPITOLO 3. ALGORITMI DI COMMUNITY DETECTION 33 Algoritmo 3.2 Calcolo dei valori di edge betweennes
1. Si esegue una ricerca BFS a partire da ogni vertice del grafo. 2. Si costruisce l’albero dei percorsi minimi per ogni vertice del grafo. 3. Per ogni vertice v1, si calcola quanti cammini minimi ci sono da v1 a v2,
se il nodo v2 si trova al i-imo livello dell’albero, allora i cammini minimi da v1 a v2 hanno lunghezza i e passano per i padri di v2 nell’albero. Il numero dei cammini minimi per v2 sarà dato dalla somma del numero di cammini minimi per vertici padri.
4. Si determina quanto flusso attraversa ogni arco del grafo. Per fare que-sto, in modalità bottom up ad ogni vertice viene assegnata un’unità di flusso a cui si somma il flusso che gli arriva dai vertici figli, successi-vamente ogni nodo ridistribuisce equamente il proprio flusso ai vertici padri.
Modularità La modularità[22] di una partizione non è altro che un valore calcolato come il numero di archi presenti all’interno di una community me-no il numero di archi ottenuti da una grafo random con lo stesso valore di degree medio dei vertici della community stessa. Attraverso questa valuta-zione è possibile stabilire se effettivamente il numero di archi intra-group sia maggiore di quanto ci si aspetterebbe da un grafo random.
Il valore della modularità è compreso tra -1 e 1 e solitamente i valori maggiori di 0.5 indicano l’effettiva presenza di una struttura di communi-ty, mentre valori intorno allo zero indicano che la distribuzione degli archi inter-group ed intra-group è molto simile a quella di un grafo random. La modularità viene calcolata con la seguente formula:
Q = 1 2m
Pij [A
ij- ki−kj2m ) δ (ci,cj)
Sebbene tramite la modularità vi sia la possibilità di individuare il miglior partizionamento di community all’interno di un grafo rimane il problema del ricalcolo della betweenness da effettuare a ogni iterazione dell’algoritmo, un’operazione che impatta sempre di più con il crescere delle dimensioni del grafo in analisi.
3.2
Label Propagation
Sulla base della classificazione effettuata possiamo introdurre l’algoritmo La-bel Propagation mettendo in evidenza che non gestisce l’overlapping delle community, i grafi orientati, e non consente di gestire l’evoluzione del gra-fo nel tempo. Per quanto concerne le caratteristiche richieste dall’algoritmo ai valori in input, va detto che di base richiede solamente il grafo stesso, non gestisce input multi dimensionali, e non lavora su input incrementali o multipartiti.
L’algoritmo in questione è stato presentato da Usha Nandini Raghavan, Réka Albert and Soundar Kumara con la pubblicazione "Near linear time al-gorithm to detect community structures in large-scale networks"[10]. Secondo quanto visto prima l’algoritmo viene inserito nella categoria Diffusion.
Per Diffusion si intende quel processo con cui le proprietà di archi o vertici di un grafo vengono prima valorizzate in modo casuale, per poi successiva-mente effettuare raggruppamenti, query e normalizzazioni sui modelli risul-tanti. Sulla base della seguente definizione, possiamo pensare di adattare il processo di Diffusion al concetto di community detection su reti complesse:
«Una diffusion community in una rete complessa è un insieme di nodi raggruppati dalla propagazione di una stessa azione, proprietà o informazio-ne»
L’idea di base degli algoritmi Diffusion è quella di effettuare una Diffusion Procedure in una rete, ovvero eseguire un preciso insieme di azioni in modo da attuare la propagazione delle informazioni, ed infine raggruppare tutti i nodi che a seguito della procedura sono terminati nello stesso stato.
Gli autori di Label Propagation si sono basati su una semplice idea, quella di estrarre le community di una rete raggruppando i vertici in base all’eti-chetta a cui sono associati. Inizialmente tutti i vertici vengono associati ad etichette univoche, poi, dopo aver effettuato uno shuffle della sequenza dei nodi della rete, questi vengono presi in considerazioni in maniera sequenziale per poter riassegnarvi una nuova etichetta.
Il calcolo dell’etichetta si traduce nell’estrarre l’etichetta che è assegnata alla maggioranza dei vertici vicini. Le fasi di shuffle dell’ordine dei vertici ed
CAPITOLO 3. ALGORITMI DI COMMUNITY DETECTION 35 il ricalcolo delle etichette vengono iterate finchè nessun vertice ha la necessità di aggiornare la propria etichetta.
Durante le diverse iterazioni effettuate dall’algoritmo il numero di etichet-te presenti nella reetichet-te diminuisce, questo è dovuto al fatto che alcune etichetetichet-te tenderanno a dominare la rete aggregando rapidamente molti vertici, altre invece scompariranno ed i vertici associati verranno assorbiti.
Come abbiamo già accennato ogni vertice ha un’etichetta associata, e questa per essere calcolata prende in considerazione i vertici vicini x1, x2, . . . , xk; l’informazione utile riguardo i vertici vicini è l’etichetta ad essi associata, la community di appartenenza. Ogni vertice della rete sceglie di far parte della community a cui la maggior parte dei sui vicini appartiene.
La modalità di aggiornamento dell’etichetta di ogni singolo vertice può essere effettuata in due modalità: sincrona ed asincrona. La scelta della modalità di aggiornamento fa variare durante l’esecuzione dell’algoritmo, il set di etichette e di vertici da prendere in considerazione ad ogni iterazione. L’aggiornamento delle etichette in modalità sincrona avviene, suppo-nendo di eseguire l’t-esima iterazione, tesuppo-nendo conto di tutte le etichette assegnate all’iterazione t-1 ai vertici vicini.
Consideriamo Cx(t) la funzione che restituisce l’etichetta da assegnare al vertice x per l’iterazione t:
Cx(t) = f(Cx1(t-1), . . . Cxk(t-1))
dove la funzione f non fa altro che determinare l’etichetta predominante in un insieme di etichette.
L’aggiornamento delle etichette in modalità sincrona, in determinate cir-costanze, può condurre l’algoritmo in una situazione di oscillazione continua delle etichette; è il caso in cui l’algoritmo agisce su grafi bipartiti, quasi bipartiti e a stella.
Figura 3.10: Oscillazione delle etichette su Label Propagation
In Figura 1.1 viene mostrato come l’algoritmo su un semplice grafo bi-partito, una delle situazioni appena citate, entra in una fase di oscillazione continua delle etichette.
La modalità asincrona di aggiornamento viene utilizzata proprio per evi-tare le situazioni di loop in cui la modalità sincrona può condurre l’algoritmo; viene quindi ridefinita la funzione Cx(t):
Cx(t) = f(Cxi1(t), . . . , Cxim(t), Cxi(m+1)(t-1), . . . ,Cxik(t-1))
A differenza della modalità sincrona, in questa modalità notiamo che i vertici vicini del nodo x vengono suddivisi in due insiemi, quelli che sono stati già aggiornati dalla corrente iterazione t (xi1, . . . , xim) e quelli che non sono stati ancora aggiornati per cui viene considerata l’etichetta a cui sono stati associati dall’iterazione t-1 ( xi(m+1), . . . , xik).
Sia nel caso della modalità sincrona che nel caso della modalità asincrona, se l’algoritmo si trova a dover scegliere tra più etichette presenti in egual modo tra i vertici vicini, la funzione Cx(t) ne sceglierà una tra queste in modalità random.
CAPITOLO 3. ALGORITMI DI COMMUNITY DETECTION 37 Algoritmo 3.3 Label Propagation
Inizializzazione delle etichetta del grafo: dato X insieme dei vertici del grafo, ∀ vertice x ∈ X Cx(0) = x.
1. t = 1.
2. Si genera un ordine casuale con cui aggiornare i vertici
3. ∀ vertice x ∈ X calcolare Cx(t) in modalità sincrona o asincrona 4. Se ∀ vertice x ∈ X Cx è l’etichetta che la maggiorparte dei vicini di x
detiene, allora l’algoritmo termina; altrimenti t = t + 1 e si prosegue con (2)
Al termine dell’algoritmo si ottiene una partizione della rete composta da community disgiunte rappresentate dall’insieme delle singole etichette associate ai vertici della rete.
Consideriamo C1, . . . , Cm le etichette presenti al termine dell’ultima fa-se di aggiornamento, indichiamo con diCjil numero di vicini del vertice i che hanno l’etichetta Cj, e N(i) l’insieme dei vertici vicini di i, possiamo formalizzare la condizione di terminazione dell’algoritmo:
∀ vertice i ∈ X con etichetta Ci =⇒ diCi ≥ diCj ∀ j ∈ N(i)
La condizione di terminazione proposta dagli autori, fa si che tutti i vertici di ogni community abbiano all’interno della community stessa almeno lo stesso numero di vicini che hanno in altre community; questa caratteristica è molto simile a quella che definisce una strong community, per cui ogni vertice di una community ha più vicini all’interno della community stessa rispetto a quelli appartenenti alle altre community.
La condizione di terminazione viene soddisfatta anche su grafi che presen-tano una sola community o grafi omogenei che non hanno alcuna struttura di community; anche in quest’ultimo caso l’algoritmo termina con una soluzione rappresentata da un’unica community.
E’ interessante notare che la condizione di terminazione di questo algo-ritmo non è una misura da dover minimizzare o massimizzare, ma è sempli-cemente una condizione.
Dato un grafo di partenza, la soluzione ottenuta da questo algoritmo non è univoca in quanto diverse partizioni del grafo potrebbero essere in grado di soddisfare la condizione di terminazione; è infatti possibile che per diverse esecuzioni dell’algoritmo si ottengano diverse strutture di community.
Prove effettuate dagli autori su grafi reali hanno dimostrato che le diverse partizioni ottenute da diverse esecuzioni dell’algoritmo, sono tutte simili tra loro.
La possibilità di ottenere diverse strutture di community è una conse-guenza della visita casuale effettuata sia sui vertici che sui vicini dei vertici in fase di aggiornamento delle etichette.
Osservando l’evolversi delle etichette attive durante l’esecuzione dell’algo-ritmo, possiamo notare che nella fase iniziale le principali etichette tendono ad acquisire velocemente la maggior parte dei vertici fino a quando le singole community che si stanno formando non si avvicinano ai bordi delle com-munity stessa, da quel momento in poi le comcom-munity adiacenti iniziano a contendersi i vertici presenti sulle loro frontiere; minore sarà il numero di vertici in comune tra due community adiacenti e maggiore sarà la velocità con cui raggiungeranno il loro consenso interno.
La condizione di terminazione si raggiunge in una prima fase quando si inizia a creare un consenso locale interno alle community e solamente dopo quando si raggiunge un consenso globale tra le community.
Una variante dell’algoritmo proposta dagli autori consente di ridurre il numero di possibili soluzioni ottenute a partire da un determinato grafo, l’idea è quella etichettare a priori un insieme di vertici cosiddetti centrali e lasciare tutto il resto dei vertici senza alcuna etichetta. Per vertici centrali si intende quei vertici che si pensa possano avere un ruolo centrale all’interno delle community.
Con questa variazione sull’input iniziale si nota che durante le prime iterazioni dell’algoritmo tutte i vertici non etichettati tendono ad acquisire l’etichetta del vertice centrale più vicino a loro. Si nota anche che minore è la cardinalità dell’insieme dei vertici centrali forniti in input all’algoritmo e minore è il numero di possibili soluzioni che questo potrà restituire.
CAPITOLO 3. ALGORITMI DI COMMUNITY DETECTION 39 non è semplice identificare i nodi centrali ancor prima di aver identificato le community di appartenenza, e per questo motivo la loro scelta iniziale è stata quella di non assegnare alcuna etichetta ai vertici, fornendo in input all’algoritmo solamente il grafo.
Valutazione delle soluzioni ottenute
Una delle possibili modalità per verificare la similarità di due soluzioni ottenute a seguito di due esecuzioni dell’algoritmo sullo stesso grafo è la valutazione della funzione fsame. La funzione fsame determina la percentuale di vertici che sono stati assegnati alla stessa community confrontando due differenti soluzioni ottenute. Si agisce creando una matrice M i cui elementi Mij corrispondono al numero di vertici che la community i ha in comune con la community j. La fuzione fsame è cosi ottenuta:
fsame = 12 (Pi maxj {Mij} + Pj maxi {Mij}) 100n
Tramite tale funzione possiamo fissare una soluzione come riferimento (supponendo essere quella che meglio ha descritto le community del grafo) e far variare tutte le altre soluzioni ottenute, in modo da valutare quanto vicine siano queste soluzioni tra di loro.
Vi sono comunque situazioni in cui la fuzione fsame non è molto accurata o per meglio dire poco sensibile ad alcune differenze tra le due soluzioni considerate.
E’ il caso per cui nella soluzione di riferimento abbiamo piccoli insiemi di vertici appartenenti a community differenti, che però nella soluzione che si sta comparando sono stati mappati all’interno di un’unica community; tale casistica non viene rilevata adeguatamente dalla funzione fsame .
Un’altra opzione per valutare la similarità tra due soluzioni ottenute, è quella suggerita dagli autori, e consiste nell’utilizzo degli indici di Jaccard in quanto risultano essere molto più accurati su tutte le possibili soluzioni da valutare. Supponiamo di avere α e β, due differenti insiemi di community estrapolate da due esecuzioni di Label Propagation e di volerne valutare la similarità. Consideriamo per il calcolo dell’indice sulle due soluzioni le seguenti variabili:
a - il numero di coppie di vertici assegnati alla stessa community sia α in che in β
b - il numero di coppie di vertici assegnati alla stessa community in α ma non in β
c - il numero di coppie di vertici assegnati alla stessa comminity in β ma non in α
L’indice di Jaccard è così definito:
a (a+b+c)
i valori ottenuti dall’indice variano tra 0 e 1, valori tendenti a 1 indicano una forte similarità tra le due soluzioni valutate.
E’ possibile quindi tramite l’indice di Jaccard osservare che le differen-ti soluzioni ottenute da Label Propagadifferen-tion possono effetdifferen-tivamente estrarre strutture di community sulle varie tipologie di rete.
Aggregazione delle soluzioni ottenute
Riguardo la molteplicità di soluzioni che si possono ottenere, gli autori di Label Propagation, sottolineano che a fronte di diverse esecuzioni dell’algo-ritmo, vi è la possibilità di ottenere alcune soluzioni in grado di far emergere community che nessun altra soluzione è riuscita ad estrapolare.
Da qui nasce l’idea di prendere in considerazione come ’finale’ un aggre-gato di tutte le soluzioni ottenute durante le varie esecuzioni dell’algoritmo. Supponiamo di valutare due soluzioni, per cui Cα è l’insieme delle etichet-te otetichet-tenuetichet-te nella soluzione α e Cβ quelle delle etichette trovata nella soluzione β; a questo punto per un dato vertice x possiamo definire una nuova etichetta Cx = (Cαx, Cβx).
L’aggregazione di due soluzioni porta alla creazione quindi di nuove etichette (community). Facendo riferimento alla Figura 3.11, possiamo notare come l’aggregazione di community più estese presenti in una soluzione portano a far emergere l’esistenza delle community più piccole, è il caso in cui una com-munity A della soluzione α, in fase di aggregazione, viene suddivisa in due
CAPITOLO 3. ALGORITMI DI COMMUNITY DETECTION 41 o più community presenti nella soluzione β dando modo di far emergere le community minori β1, β2.
Figura 3.11: Aggregazione di due soluzioni
Complessità
Per l’inizializzazione dei vertici il costo è pari a O(n), per la singola ite-razione e la propagazione delle etichette il costo è lineare in riferimento alla cardinalità degli archi del grafo O(m). Il costo di selezione dell’etichetta tra tutti i vertici vicini è pari a O(|N(x)|), operazione eseguita per tutti i vertici che può quindi essere considerata O(m).
Inoltre va tenuto conto della possibilità di ottenere community differenti che presentano la stessa etichetta e che vanno rietichettate usando una ricerca BFS sui sottografi dei singoli gruppi di vertici.
Questa casistica emerge a fronte di una soluzione comunque lecita che si è generata a causa di un nodo che in fase di aggiornamento delle etichette ha prima ceduto la sua etichetta a due gruppi distinti di vertici e poi ha recepito un etichetta differente da quella iniziale.
I due gruppi di vertici hanno poi formato due differenti community con la stessa etichetta. La casistica appena descritta rimane comunque un caso limite, ma comunque possibile, soprattutto se si è adottata la tecnica di aggregazione delle soluzioni, ma comunque possibile. L’introduzione della ricerca BFS finale porta la complessità a O(m + n).
Community overlapping
Uno dei limiti dell’algoritmo, comune a diversi algoritmi di community detection, è la possibilità di rilevare solamente community disgiunte. Steve Gregory nell’articolo ’Finding overlapping communities in networks by label propagation’[2] propone una generalizzazione di Label Propagation in grado di gestire anche l’overlapping.
La generalizzazione dell’algoritmo prende in input un altro parametro oltre al grafo stesso: il potenziale grado di overlapping tra community.
Supponendo di impostare questo parametro ad 1 otterremmo la stessa esecuzione dell’originale algoritmo Label Propagation.
L’idea di fondo è quella di rilassare il vincolo dell’associazione di una sola etichetta ad ad ogni vertice, in questo modo sarà possibile descrivere l’informazione di appartenenza a più community.
Così come l’algoritmo originale, i vertici vengono inizializzati con un iden-tificativo univoco e si procede per iterazioni ad aggiornare il set di etichette del vertice.
A differenza dell’originale Label Propagation, l’etichetta è formata un insieme di coppie chiave-valore, dove le chiavi rappresentano le etichette dei nodi vicini, ed i valori rappresentano il coefficiente di appartenenza.
La somma di tutti i coefficienti di appartenenza associati alle etichette deve risultare sempre pari ad 1.
Ad ogni iterazione tramite la funzione bt(c,x) viene calcolato il coefficiente di appartenenza di un vertice x ad una community C:
bt(C, x)= P
y∈N (x)bt−1(C,y)
|N (x)|
dove N(x) rappresenta l’insieme dei vertici vicini di x.
Questo calcolo viene effettuato per tutte le community di appartenenza del vertice x, il che corrisponde (almeno in fase iniziale) ad effettuate il calcolo su tutte le etichette dei vertici vicini.
In questa variante, l’algoritmo utilizza un aggiornamento sincrono, si con-siderano difatti tutti i vertici vicini di x tenendo conto delle loro etichette associate alla precedente iterazione t-1.
CAPITOLO 3. ALGORITMI DI COMMUNITY DETECTION 43 Senza l’introduzione dell’ulteriore parametro precedentemente menzionato, l’utilizzo della funzione bt(C,x) per calcolare i coefficienti di appartenza sulla base di tutte le coppie chiave-valore dei vertici vicini, ci porterebbe ad otte-nere come soluzione un numero di community pari al numero di vertici del grafo, in quanto ogni nodo manterrebbe nella propria etichetta la community di appartenenza dei suoi vicini.
Figura 3.12: Esecuzione algoritmo senza il parametro soglia
In Figura 3.12 notiamo come ogni vertice ha mantenuto una lista di coppie chiave-valore, ad esempio il vertice ’c’ ha mantenuto le etichette dei sui vertici vicini ’b’ e ’d’ ed entrambe le etichette sono associate ad un coefficiente di appartenenza pari a 1
2.
Il parametro aggiuntivo proposto in questa variante serve a calcolare il coefficiente che fungerà da soglia per tutte le coppie chiave-valore presenti nelle etichette dei vertici del grafo.
Ad ogni iterazione dell’algoritmo, dopo avere costruito l’etichetta del ver-tice che sappiamo essere formata da una serie di coppie chiave-valore, si eliminano dall’etichetta tutte quelle coppie il cui coefficiente di appartenenza è minore della soglia.
Possiamo quindi definire ’v’ come un ulteriore parametro dell’algoritmo. questo rappresenterà il numero massimo di community a cui un vertice può appartenere.
Introducendo il nuovo parametro ’v’ possiamo definire la soglia minima per cui una coppia chiave-valore per essere mantenuta nella lista di un vertice deve avere un coefficiente di appartenenza pari o superiore a 1
v.
Durante le varie fasi di calcolo delle etichette e verifica della soglia è possibile che tutte le coppie chiave-valore associate ad un vertice abbiano un valore inferiore alla soglia.
In questo caso si mantiene solamente la coppia con valore maggiore e si rimuovono le coppie restanti; nel caso in cui più di una coppia ha lo stesso valore massimo, allora la scelta della coppia da mantenere nell’etichetta viene effettuata in modalità random.
Figura 3.13: Prima iterazione di Label Propagation
Visto che l’algoritmo prevede che la somma dei coefficienti di tutte le coppie dell’etichetta associata ad un vertice sia pari ad 1, dopo aver rimosso le coppie con valore inferiore alla soglia, è necessario normalizzare i coefficienti delle coppie rimanenti nell’etichetta.
La figure successive mostrano in pochi passaggi come avviene la propa-gazione delle etichette associate ai vertici del grafo.
CAPITOLO 3. ALGORITMI DI COMMUNITY DETECTION 45
Figura 3.14: Seconda iterazione di Label Propagation
Figura 3.15: Ultima iterazione di Label Propagation
3.3
Scelta dell’algoritmo
L’idea che vogliamo mettere in pratica è quella di selezionare uno tra i due algoritmi analizzati, riformularlo in ottica block centric ed infine implemen-tarlo.
Gli algoritmi che abbiamo approfondito sono Edge Betweenness e Label Propagation ed entrambi presentano svariati aspetti da continuare ad appro-fondire. La nostra scelta è ricaduta su Label Propagation ed è stata dettata da diversi fattori.
Innanzitutto Label Propagation lavora con una logica molto lineare che facilita il riadattamento in ottica block centric, lo stesso non possiamo dire
della logica di Edge Betweenness che necessita di più passaggi per portare a termine una singola iterazione.
Un altro fattore che ha influito in questa scelta è la necessità di informa-zione che ogni singola iterainforma-zione dei due algoritmi presupporrebbe in ottica block centric.
Difatti in Label Propagation le informazioni necessarie ad ogni singola iterazione eseguita sul singolo nodo di elaborazione sono pressochè locali (etichette dei vertici vicini), mentre in Edge Betweenness potenzialmente potremmo avere bisogno di informazioni trasversali all’intero grafo e non alla singola partizione, come ad esempio il calcolo di tutti i cammini minimi dell’intero grafo.
Capitolo 4
Block centric label propagation
L’esecuzione dell’algoritmo Label Propagation, qualsiasi sia la sua implemen-tazione, necessita in input il grafo delle rete da cui vogliamo estrapolare le community. Nella maggior parte dei casi l’input consiste nella trasposizione del grafo in una Edge List.
Figura 4.1: Esempio di un grafo
Il formato edge list consiste in un elenco di archi rappresentati da coppie di nodi, si prenda d’esempio il grafo in figura, la sua rappresentazione nel formato descritto è la seguente:
0 1 0 2 1 2 1 3 2 3 3 4 4 5 4 7 5 6 5 7 6 7
Tabella 4.1: Rappresentazione di una edge list
L’algoritmo viene eseguito su di un insieme di nodi core che è variabile. Lo sviluppo di un applicazione block centric prevede anche la gestione dell’in-put, nella versione centralizzata di Label Propagation è possibile utilizzare un unico file di input per la rappresentazione del grafo consapevoli anche del fatto che sarà un solo nodo a gestire l’intera esecuzione dell’algoritmo a partire dalla lettura dell’input fino alla produzione delle community.
Per la versione distribuita, dato che ogni singola istanza avrà il compito di gestire solamente una porzione del grafo ed elaborare i dati parziali su questa, si è reso necessario prevedere una fase di preliminare per la gestione dell’input.
Strutturazione dell’algoritmo
L’idea è quella di suddividere l’edge list iniziale in n edge list quanti i nodi che partecipano all’esecuzione dell’algoritmo, in pratica quello che si vuole ottenere è assegnare ad ogni nodo una porzione di edge list del grafo evitando di fornire la visione globale del grafo.
Supponendo di voler avviare una simulazione che coinvolge 2 nodi prov-vederemo a produrre 2 partizioni del grafo in modo da poter consentire ad ogni nodo di lavore localmente sull’egde list che gli verrà assegnata.
I vari file di input prodotti saranno composti non solo da archi che coinvol-gono esclusivamente vertici interni alla partizione, ma vi saranno anche una serie di archi di cui solo uno dei due vertici appartiene alla partizione, l’altro
CAPITOLO 4. BLOCK CENTRIC LABEL PROPAGATION 49 vertice oltre ad essere riferito tramite il suo identificativo verrà associato al numero della partizione di cui fa parte.
Di seguito il macro codice che descrive il funzionamento di Block Centric Label Propagation.
Algoritmo 4.1 Block Centric Label Propagation
Dato X insieme dei vertici locali al nodo; C(x) funzione che calcola l’etichetta da assegnare al nodo x tenendo conto delle sole informazioni locali; D(x) funzione che calcola l’etichetta da assegnare al nodo x tenendo conto anche delle informazioni proveniente dagli altri nodi e V(X) funzione che valida la condizione di terminazione.
Inizializzazione: il grafo viene partizionato e vengono prodotte k partizioni quanti i nodi coinvolti.
1. Ogni nodo prende in carico la propria partizione
2. Ogni nodo esegue un numero configurabile di iterazioni locali:
(a) Si genera un ordine casuale con cui verranno aggiornati i vertici locali al nodo
(b) ∀ vertice locale x ∈ X si calcola C(x) in modalità asincrona 3. Tutti i nodi si scambiano le etichette dei vertici
4. ∀ vertice locale x ∈ X si calcola D(x) in modalità asincrona
5. Se la funzione V(X) non valida la condizione di terminazione su tutti i nodi l’algoritmo ritorna al punto (2)
6. Si raccolgono tutte le etichette dei vertici generate dai nodi, il loro raggruppamento genera le community
Sono stati implementati due differenti tool di partizionamento, questi preso in input l’edge list iniziale producono un numero arbitrario (k) di par-tizioni di edge list nel formato gestito dalla versione distribuita di Label Propagation.
Di seguito un esempio di un possibile output ottenuto dal partizionamento del grafo di Figura 4.1:
0 1 0 2 1 2 1 3 2 3 3 #1 4 4 #0 3 4 5 4 7 5 6 5 7 6 7
Tabella 4.2: Esempio di notazione su due partizioni di un grafo In tabella 4.2 notiamo che vi sono delle entry per cui oltre al vertice sorgente e di destinazione viene indicato anche un valore preceduto da #, questo valore indica la partizione di appartenenza del vertice di destinazione; (4 #0 3) indica che nella partizione corrente è presente un arco che va dal vertice locale 4 al vertice 3 presente nella partizione 0.
Sulla base del grafo in figura possiamo eseguire alcuni passaggi in modo da mostrare la logica che si è voluto dare alla versione block centric di Label Propagation.
Supponiamo di voler eseguire l’algoritmo su due nodi di elaborazione. Il primo passaggio, definito di preprocessing, consiste nel partizionare l’input (Tabella 4.1) in modo da ottenere due distinte partizioni (Tabella 4.2).
Si noti che le partizioni di edge list ottenute per ogni entry riportano l’identificativo del nodo sorgerte e l’identificativo del nodo target, solo per alcune di queste entry figura un terzo identificativio segnalato dal carattere ’#’ ed indica l’identificativo del nodo su cui si trova il nodo target.
Ognuna delle partioni ottenute viene presa in carico dai singoli nodi di elaborazione e questi hanno la possibilità di interfacciarsi tra di loro.
L’esempio che stiamo mostrando in Figura 4.2 lavora con due nodi di elaborazione, il nodo #0 ed il nodo #1.
Analizzando le partizioni che in questo caso abbiamo generato in modo arbitratrio possiamo notare che i vertici (0,1,2,3) del grafo verranno presi in carico dal nodo #0 ed i vertici (4,5,6,7) dal nodo #1.
Gli archi del grafo a seguito delle partizioni risultano essere tutti locali alle partizioni generate ad eccezione dell’arco (3,4) che vediamo figurare su emtrambe le partizioni con la notazione (3, #1, 4) e (4, #0, 3).
