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 iterazione 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).
CAPITOLO 4. BLOCK CENTRIC LABEL PROPAGATION 51
Figura 4.2: Il grafo partizionato su due nodi
All’avvio dell’algoritmo, in questo caso stiamo considerando due istanze, ogni nodo prende in input la propria partizione di edge lista e sulla base di essa genera una struttura interna utile a descrivre la partizione di grafo.
Nella pratica, ogni qualvolta che viene processato una entry dell’edge list, se non esistono il nodo sorgente ed il nodo target, questi vengono creati, altrimenti vengono utilizzati per generare l’arco.
Nel caso in cui la entry dell’edge list riporta l’identificativo con ’#’ il nodo genera un nodo marcato come ’esterno’. In riferimento al grafo di Figura 4.1 il nodo #0 avrà in carico il vertice esterno 4 ed il nodo #1 avrà in carico il vertice esterno 3.
A questo punto entrambi i nodi #0 e #1 hanno tutte le informazioni necessarie per procedere con l’estrazione delle community. In questa fase ogni nodo di elaborazione svolge determinati passaggi che possiamo riassumere in: elaborazione delle informazioni locali ed aggiornamento delle etichette recupero delle informazioni dagli altri nodi
riaggiornamento delle etichette
verifica della condizione di terminazione Simulazione dell’algoritmo
locali al nodo di elaborazione, l’idea è quella di eseguire Label propagation solamente sulla partizione senza tener conto delle informazioni inerenti ai vertici gestiti da altri nodi, come ad esempio per gli archi (3, #1, 4) e (4, #0, 3).
La fase di elaborazione dei nodi locali viene iterata per un numero arbi- trario di volte in modo da far stabilizzare localmente le etichette dei vertici.
Figura 4.3: Inizializzazione delle etichette
Così come mostrato in Figura 4.3 inizialmente entrambi i nodi inizializ- zano le etichette dei vertici con il loro identificativo e si preparano alla prima iterazione.
CAPITOLO 4. BLOCK CENTRIC LABEL PROPAGATION 53 In Figura 4.4 viene mostrato il risultato della prima iterazione, tutti i ver- tici hanno variato la loro etichetta ed il calcolo è stato effettuato utilizzando solamente le informazioni locali, non è stata quindi effettuata comunicazione tra i due nodi.
Figura 4.5: Seconda iterazione di Block Centric Label Propagation In Figura 4.5 viene mostrato il risultato della seconda iterazione, hanno variato la loro etichetta solo i vertici (0,3,4,5,6); anche in questa iterazione non è stata effettuata comunicazione tra i due nodi.
Figura 4.6: Scambio di etichette tra nodi
In Figura 4.6 si nota come entrambi i nodi si scambiano le etichette dei vertici i cui archi sono condivisi tra le partizioni. In questo caso il nodo #0
invia l’etichetta del vertice 3 al nodo #1 ed il nodo #1 invia l’etichetta del vertice 4 al nodo #0.
Fatto ciò entrambi i nodi ricalcolano le etichette dei propri nodi avendo tutte le informazioni necessarie; in questo caso lo scambio delle etichette trai i due nodi non ha innescato alcuna variazioni all’informazione locale in quanto il vertice 3 con etichetta 3 doveva scegliere casualmente tra le etichette (1,3,4) ma essendo la sua etichetta presente tra quelle disponibili preferisce non variarla, lo stesso avviente per il vertice 4 con etichetta 6 che si trova a scegliere casualmente tra le etichette 3,5,6,9.
Figura 4.7: Ultima iterazione di Block Centric Label Propagation In Figura 4.7 entrambi i nodi hanno già ricalcolato le loro etichette ed entrambi i nodi hanno validato la condizione di terminazione per cui tutti i vertici detengono l’etichetta detenuta dalla maggioranza dei vertici vicini. Un controller che gestisce lo stato di tutti i nodi in esecuzione verifica che tutti i nodi abbiano terminato la loro esecuzione.
Le informazioni prodotte fino a questo momento vengono fatte confluire, i vertici vegono raggruppati sulla base della loro etichetta finale in modo da generare un l’elenco di tutte le community del grafo.
Per l’esempio che abbiamo seguito Block Centric Label Propagation ha generato la community {3} per i vertici (0,1,2,3) e la community {6} per i vertici (4,5,6,7).
Capitolo 5
Descrizione tecnica dell’algoritmo
e valutazione
Per poter realizzare una versione Block Centric di un algoritmo e riuscire a testarlo pur non disponendo di una reale rete di nodi abbiamo pensato di utilizzare un framework che ben si presta a questo genere di attività: PeerSim. Un’altro strumento che abbiamo deciso di utilizzare è Metis, grazie ad esso abbiamo potuto applicare una tecnica di partizionamento che ci consente di ottenere delle partizioni bilanciate.
5.1
PeerSim
PeerSim1[11] è un framework single threaded sviluppato in Java che consente di effettuare simulazioni su reti, permette di variare facilmente il numero di nodi della rete.
Questo framework non implementa nessun tool grafico per la rappresen- tazione della rete o per il tracciamento dei pacchetti scambiati tra i vari nodi, di fatto la simulazione della rete e quindi l’interazione trai i vari nodi viene gestita con l’invio di messaggi o la generazioni di eventi; è comunque possibile tenere traccia delle interazioni tra i vari nodi implementando delle apposite utility di logging o persistendo queste informazioni su database.
1http://peersim.sourceforge.net
PeerSim per il suo funzionamento definisce uno stack di protocolli che possono essere estesi in modo da poter definire il comportamento dei no- di della rete. Per facilitare la simulazione di una rete, PeerSim mette a disposizione alcuni template di rete che è possibile inglobare nella propria implementazione.
Il punto di forza di questo framework sta nelle ottime prestazioni di simu- lazione su reti di grandi dimensioni e nel fatto che è proprio l’utente a gestire l’estensione dei componenti che governano la simulazione. Le simulazioni vengono gestite tramite un apposito file di configurazione che ne descrive le fasi ed i parametri con cui vengono eseguite.
Supporta due differenti modelli di simulazione, la cycle-based e la event- based. La prima tipologia lavora su un modello ciclico, in modo sequenziale e periodico ogni nodo coinvolto nella simulazione esegue una serie di azioni.
Figura 5.1: PeerSim cycle-based
La modalità event-based si basa sull’invio di messaggi che vengono scam- biati direttamente tra i vari nodi, poi i nodi eseguono le loro azioni nell’ordine con cui i messaggi sono stati inseriti in un’apposita coda.
CAPITOLO 5. DESCRIZIONE TECNICA 57
Figura 5.2: PeerSim event-based
PeerSim fornisce l’interfaccia Node, questa ci consente di accedere alle istanze dei nodi della simulazione. I singoli nodi vengono istanziati tramite il medoto clone() di Java in modo da velocizzare la fase di inizializzazione della simulazione in presenza di numeri consistenti di nodi.
Il protocollo messo a disposizione da PeerSim per la gestione cycle-based è CDProtocol, l’utente può implementare questa interfaccia per poter definire le azioni che periodicamente i nodi della rete dovranno eseguire.
L’interfaccia Linkable espone i medoti necessari a fornire i servizi agli altri protocolli come ad esempio fornire l’accesso ai nodi vicini. É già disponibile la classe peersim.core.IdleProtocol che implementa l’interfaccia Linkable.
L’interfaccia Control descrive un oggetto che può essere schedulato in determinati istanti dell’esecuzione della simulazione. Tipicamente, ma non necessariamente, le istanze di oggetti Control sono utilizzate per apportare modifiche ai comportamenti degli altri protocolli durante il loro funziona- mento.
Una simulazione Peersim inizia sempre con la lettura del file di configura- zione fornito come unico input, questo serve a definire una serie di parametri e protocolli da utilizzare durante la simulazione. Subito dopo la lettura della configurazione, ha luogo la fase di inizializzazione con cui vengono istanziati tutti i nodi necessari alla simulazione.
Successivamente sulla base della configurazione vengono alternate le ese- cuzioni di controlli e protocolli sui nodi attivi della simulazione, il tutto si ri- pete finchè non viene validata una condizione di terminazione o si è raggiunto il numero prestabilito di cicli da effettuare.