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 rete diminuisce, questo è dovuto al fatto che alcune etichette 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, tenendo 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 community 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 Propagation possono effettivamente 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 ottenute 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