Dopo aver ottenuto la partizione dei nodi della rete con un algoritmo di community detection, è utile valutare la qualità del risultato. Un limite degli algoritmi di ottimizzazione è, infatti, la loro capacità di individuare in ogni rete una partizione di massima modularità o che, in generale, fornisca il valore ottimo di una data funzione obiettivo. É possibile, allora, che per favorire l’ottimizzazione globale metodi di questo tipo forzino partizioni dei nodi che possono risultare difficilmente interpretabili e che non mettano in evidenza in una comunità nodi particolarmente connessi. Un altro problema che tipicamente si riscontra nell’analisi di reti grandi è il limite di risoluzio- ne: l’algoritmo non è in grado di individuare comunità, benchè significative, che abbiano cardinalità al di sotto di una certa soglia. Si rende necessaria, dunque, una verifica a posteriori che valuti la significatività della partizione e la qualità delle singole comunità ottenute.
Nei prossimi paragrafi descriveremo i metodi utilizzati nel lavoro per valutare la qualità delle comunità individuate (probabilità di persistenza), e confron- tare diverse partizioni (matrici di precision e recall e indici di similarità). Si precisa che il confronto può avvenire tra una partizione fissata e basata su caratteristiche note dei nodi e una partizione indotta da un algoritmo, o tra partizioni ottenute con due metodi diversi. Nel primo caso il confronto ha come scopo la valutazione della capacità dell’algoritmo di ricostruire la struttura nota della rete, nel secondo è possibile mettere in evidenza eventua- li differenze di performance e di risultati a supporto della scelta del metodo più efficace e adatto alla rete in analisi.
Probabilità di Persistenza Data una partizione dei nodi in K comunità, è possibile valutare la loro coesione calcolando la probabilità di persistenza α. In una rete non diretta pesata, la probabilità di persistenza della comunità Ck è definita dalla seguente espressione:
αk= P i∈Ck P j∈Ckwij P i∈Ck P j∈{1,2,...K}wij (4.21)
La probabilità di persistenza è, dunque, pari alla frazione di strength dei nodi di Ck che rimane all’interno di Ck. In letteratura questa quantità
è indicata anche come embeddedness. Il termine probabilità di persistenza deriva dal fatto che αk coincide con la probabilità che un random walker che
Nel nostro lavoro seguiremo l’approccio utilizzato in [14], dove si valuta la probabilità di persistenza per la rete, non diretta e pesata, dei partecipanti a organizzazioni criminali. Per ogni comunità individuata viene calcolato il valore di αk: tale comunità è tanto più coesa quanto più è grande la sua
probabilità di persistenza. In questo contesto, un raggruppamento di nodi si può definire comunità se la probabilità di persistenza risulta > 0, 5. É da sottolineare il fatto che il valore di αk tende a aumentare con la cardinalità
Nk della comunità Ck, fino a risultare pari a 1 se si considera la partizione
(banale) che assegna tutti i nodi della rete alla stessa comunità. É opportuno valutare, per questo, oltre al valore della probabilità di persistenza della comunità Ck, la sua significatività dal punto di vista statistico mediante lo
z-score così definito:
zk =
αk− µ( ¯αk)
σ( ¯αk)
(4.22) dove αkè la probabilità di persistenza della comunità Cke ¯αkè la probabilità
di persistenza empirica di una sottorete connessa di cardinalità Nk, pari a
quella di Ck. I termini µ(¯αk)e σ(¯αk)rappresentano rispettivamente la media
e la deviazione standard delle probabilità di persistenza empiriche calcolate su un campione casuale di sottoreti connesse di cardinalità Nk. Una comunità
che presenta valori alti di αke di z risulta, quindi, coesa non per motivazioni
legate alla sua cardinalità, ma in quanto presenta valori di probabilità di persistenza significativamente più grandi rispetto a altre sottoreti di pari cardinalità. Un valore di z che, tipicamente, è da ritenere significativamente alto è 3.
Indici di similarità delle partizioni Date due diverse partizioni X = {X1, X2. . . XH} e Y = {Y1, Y2. . . YK} della stessa rete, rispettivamente in
H e K comunità, è possibile valutare la loro similarità calcolando opportuni indici. Per un quadro completo sull’argomento rimandiamo a [17], mentre descriveremo di seguito in dettaglio le quantità utilizzate durante il lavoro. Introduciamo in primo luogo la matrice di confusione NX Y, di dimensione
H × K, i cui elementi nhk indicano il numero di nodi appartenenti alla co-
munità Xh nella partizione X e alla comunità Yk nella partizione Y.
Due indici di similarità utilizzati diffusamente in letteratura per valutare le performance degli algoritmi di community detection sono la Informazione Mutua Normalizzata (NMI, Normalized Mutual Information) e la Variazio- ne di Informazione (VI). Entrambi gli indici si basano sul calcolo, data una partizione, della quantità di informazione aggiuntiva necessaria per inferire l’altra partizione. L’entità dell’informazione richiesta fornisce una misura della similarità o dissimilarità delle partizioni.
Per definire l’indice, si introducono gli assegnamenti {xi} e {yi}, dove xi
e yi rappresentano le comunità a cui il vertice i risulta assegnato rispet-
tivamente nelle partizioni X e Y, e si indicano con x e y i valori di due variabili aleatorie X e Y che rappresentano due partizioni della rete. É possibile a questo punto definire una distribuzione di probabilità congiunta P (x, y) = P (X = x, Y = y) = nxy/N, con N numero totale dei nodi della re-
te e nxynumero dei nodi appartenenti alle comunità x e y rispettivamente del-
le partizioni X e Y. Le distribuzioni marginali di X e Y sono invece definite come P (x) = P (X = x) = nX
x/N e P (y) = P (Y = y) = nYy/N: la probabili-
tà della comunità x della partizione X è data dalla frazione di nodi assegnati alla comunità x. Da ultimo si introducono anche le quantità H(X), detta en- tropia di Shannon della variabile X, pari a − PxP (x) logP (x), e l’entropia condizionale di X dato Y , pari a H(X|Y ) = − Px,yP (x, y) logP (x|y). La misura di similarità Informazione mutua di due variabili aleatorie è, infine, data dall’espressione:
I(X, Y ) = H(X) − H(X|Y ) (4.23)
Il significato dell’informazione mutua è, intuitivamente, legato all’ammon- tare di informazione che la conoscenza di una delle due variabili, nel nostro caso, di una delle partizioni, fornisce riguardo all’altra. L’entropia H(X) è, infatti, una misura dell’incertezza riguardo a X e H(X|Y ) quantifica l’incer- tezza riguardo a X nota la variabile Y . L’espressione di I(X, Y ) può essere dunque interpretata come l’ammontare di incertezza nella variabile X meno l’ammontare di incertezza in X che rimane data Y , equivalente all’ammon- tare di incertezza in X eliminata conoscendo Y .
L’informazione mutua, tuttavia, risulta poco adatta come misura di similarità tra partizioni: infatti, data una partizione X , tutte le partizioni ottenute divi- dendo alcune delle comunità di X presentano, pur essendo partizioni diverse, lo stesso valore di informazione mutua, a causa del valore nullo dell’entropia condizionale. Per avere a disposizione una misura che tenga conto esplici- tamente della eventuale dipendenza presente tra le partizioni, si introduce l’Informazione mutua normalizzata (NMI), così definita:
N M I(X , Y) = 2I(X, Y )
H(X) + H(Y ) (4.24)
è pari a 0 se solo totalmente indipendenti.
Un altro indice, introdotto in [23], è la Variazione di Informazione (VI), così definita:
V (X , Y) = H(X|Y ) + H(Y |X) (4.25)
dove H(X|Y ) e H(Y |X) sono le entropie condizionate definite sopra. L’indi- ce è costituito dalla somma di due termini che quantificano rispettivamente l’ammontare di informazione che si perde riguardo a X e l’ammontare di in- formazione che si guadagna riguardo a Y nel passare dalla partizione X alla partizione Y . L’importanza di questo indice è dato dal fatto che costituisce una metrica nello spazio delle partizioni e possiede le proprietà di una distan- za (non negatività, simmetria e disuguaglianza triangolare). Sottolineiamo che due partizioni risultano tanto più simili quanto più l’indice Variazione di Informazione assume valori vicini a 0, cioè quanto più la distanza tra le due partizioni è piccola.
Matrici di Precision e Recall Un strumento immediato per valutare la similarità di due partizioni è dato inoltre dalle matrici di Precision e Recall. Date due partizioni X e Y della stessa rete costituite rispettivamente da H e K comunità, sia nhk l’elemento {hk} della matrice di confusione tra le due
partizioni, pari al numero di nodi appartenenti alla comunità h nella prima partizione e alla comunità k nella seconda.
L’elemento phk della matrice di Precision, di dimensioni H × K, è:
phk =
nhk
|Yk| (4.26)
con |Yk|cardinalità della comunità Yk, ed è pari alla frazione di elementi
di Yk che appartengono a Xh.
L’elemento rhk della matrice di Recall, anch’essa di dimensioni H × K, è,
invece:
rhk =
nhk
|Xh| (4.27)
con |Xh|cardinalità della comunità Xh, ed è pari alla frazione di elementi
di Xh che appartengono a Yk.
Il metodo risulta efficace perchè consente un confronto a due a due tra le comunità individuate dalle due partizioni. In particolare, è interessante notare i casi in cui phk = rhk = 1, dove si ha perfetta corrispondenza tra le
comunità Xh e Yk. Risulta, invece, phk → 1 se un numero grande di nodi
della comunità Yk appartiene anche a Xh, e rhk → 1se, viceversa, un numero
grande di nodi della comunità Xh appartiene anche a Yk. Tipicamente la
partizione X è la partizione nota della rete (nel nostro lavoro, come vedremo nel Capitolo 5, sarà data dalla classificazione nelle 5 categorie MDC) e la partizione Y quella ottenuta con un algoritmo di community detection.