METODI PER DATI COMPLESSI:Modulo B

INTRODUZIONE

L’analisi condotta ha come oggetto lo studio di diversi algoritmi di community detection nell’ambito delle reti sociali.

La SNA (Social Network Analysis) si è sviluppata a partire dagli anni ’30, e si fonda sulle relazioni e le dinamiche sociali.
L’analisi delle reti sociali si basa sui dati relazionali, ovvero contatti,collegamenti, vincoli che mettono in relazione più soggetti tra loro, che prendono il nome di attori. Segue quindi che l’unità di analisi è l’individuo e i legami che esso instaura con tutti gli altri attori della rete. Mediante questi collegamenti si assiste alla formazione di gruppi più o meno ampi, tra cui si possono evidenziare piccoli gruppi, come le coppie di attori, le diadi, oppure gruppi di tre individui che prendono il nome di triadi, oppure sottogruppi più ampi.
Una rappresentazione grafica delle reti sociali può essere effettuata introducento il concetto di Grafo. Un grafo G è costituito da all’insieme dei vertici, o nodi, N collegati tra loro tramite un insieme di archi L:

\[ G(N,L) \]

La figura successiva è un esempio di grafo direzionato e non pesato. Quindi per questo grafo si ha un set di attori pari a \(N=4\) e un numero di legami direzionati pari a \(L=9\), quindi sarà un grafo \(G(4,9)\). Nella figura di esempio, sussistono alcuni legami che hanno una sola direzione, ed altri che risultano essere bidirezionali per la coppia di nodi. Inoltre c’è la possibilità che ogni legame abbia un contributo, come sarà visto in seguito, tuttavia in questo esempio ogni legame ha la stessa importanza. 

## IGRAPH a316db6 DN-- 4 9 -- 
## + attr: name (v/c)
## + edges from a316db6 (vertex names):
## [1] Luca   ->Docente Luca   ->Antonio Antonio->Andrea  Andrea ->Luca   
## [5] Antonio->Luca    Luca   ->Andrea  Andrea ->Antonio Antonio->Docente
## [9] Andrea ->Docente

CASE STUDY

L’analisi è stata effettuata su un set di dati provenienti dal repository del sito Kaggle, un’ampia banca di dati in cui chiunque può accedervi per effettuare ricerche e analisi di dati. In particolare il dataset utilizzato fa riferimento ad una rete sociale che consiste nell’uso di molteplici tag, che quotidianamente vengono utilizzati dagli sviluppatori di tutto il mondo sul noto sito Stack Overflow.
Questi tag sono stati raccolti dalle cosidette developer stories di StackOverflow, ovvero una sorta di lista di tag che ogni utente della piattaforma può pubblicare sul proprio profilo in maniera tale da comunicare agli altri gli applicativi che maggiormente utilizza. Questi hashtag fanno riferimento ad una serie di applicativi e programmi che vengono utilizzati nell’ambito della computer science, nello sviluppo web, nella progettazione di applicazioni mobile e molto altro.
Il dataset è così strutturato:

  • Stacknodes: rappresenta la node list, una tabella in formato .csv che contiene informazioni relative ai vertici della rete, come i nomi dei nodi, la loro grandezza e le etichette dei gruppi a cui ognuno appartiene . 
    • ## 'data.frame':    115 obs. of  3 variables:
##  $ name    : Factor w/ 115 levels ".net","agile",..: 42 23 41 90 84 85 45 95 43 18 ...
##  $ nodesize: num  272.4 341.2 29.8 52.8 70.1 ...
##  $ Gruppi  : Factor w/ 14 levels "Python","C#",..: 6 6 8 8 3 3 4 4 6 1 ...
  • Stacklinks:è l’edge list, sempre in formato .csv, è un set di dati che contiene invece informazioni sui legami instaurati da ogni nodo e il valore assegnato ad ogni arco che sta ad indicare la forza del legame tra le coppie di nodi. 
## 'data.frame':    490 obs. of  3 variables:
##  $ source: Factor w/ 115 levels ".net","agile",..: 15 94 13 31 112 56 108 19 96 22 ...
##  $ target: Factor w/ 115 levels ".net","agile",..: 1 1 1 1 1 1 1 1 2 3 ...
##  $ value : num  20.9 32.3 48.4 24.4 32.4 ...

Da come si evince la rete presa in esame è del tipo one-mode, cioè che presenta un solo set di attori \(N=\{{g_{1},g_{2},...,g_{115}}\}\), e ha un numero di relazioni dicotomiche e pesate pari a \(L=\{{l_{1},l_{2},...,l_{245}}\}\), in quanto non si distingue tra i legami \([n_{i},n_{j}]\) ed \([n_{j},n_{i}]\).
In particolare il valore attribuito ad ogni legame, è stato assegnato sulla base della frequenza in cui 2 tag apparivano insieme nella stessa developer story, di conseguenza ad un elevato valore dell’arco corrisponde una maggiore frequenza dell’uso simultaneo dei due tag.

DESCRIPTIVE STATISTICS

Prima di analizzare le comunità presenti nella rete abbiamo opportunamente creato delle rappresentazioni grafiche al fine di comprendere la struttura delle relazioni presenti nella rete.
Dal grafico in basso si può osservare la taglia di ogni nodo distinta per gruppo. Il grafico è stato reso interattivo al fine di poter fare una comparazioni tra le taglie dei nodi. In particolare si nota che in determinate classi ci sono dei vertici che hanno una nodesize molto elevata non solo all’interno del loro gruppo, ma anche rispetto alla totalità degli attori. Un chiaro esempio sono i nodi java,javascript e python.


Per quanto riguarda gli archi, la variabile value presente nell’edge list, indica la forza del legame tra ogni coppia di vertici.
Essendo questa una rete non direzionata, ogni legame si presenta due volte e ha lo stesso valore; è stato quindi necessario eliminare la metà dei legami, per poi eseguire un plot di facile interpretazione.

E’ stato eseguito uno scatter plot interattivo per evidenziare le coppie di nodi con i legami più forti e quelli più deboli.
La distribuzione dei legami presenta in media una forza pari a 34.968 (linea blu); si nota che la maggior parte delle coppie (il 67.75%) ha una forza nel legame al di sotto della media.

Inoltre, i primi 3 legami più forti corrispondono anche a coppie di nodi che si trovano nello stesso gruppo.

NODO 1 NODO 2 FORZA DEL LEGAME STESSO GRUPPO?
HTML CSS 126.57 Si
SPRING HIBERNATE 103.26 Si
RUBY ON RAILS RUBY 95.36 Si

A questo punto si arriva all’ultima variabile di interesse per l’analisi, ovvero quella dei Gruppi.
Dal grafico a ciambella si nota che non c’è un’equa ripartizione tra le varie classi; le due classi più numerose contano rispettivamente 23 e 18 applicativi.

NETWORK ANALYSIS

Mediante la library igraph è possibile costruire un grafo dando come input una node list ed un’edge list:

La rete così costruita non è orientata, ciò comporta un particolare approccio all’analisi, per quanto riguarda la fase di community detenction.
Un estratto della lista degli archi mostra i collegamenti tra i nodi su ogni riga.

## + 6/490 edges from a5be4fc (vertex names):
## [1] .net   --azure            .net   --sql-server      
## [3] asp.net--.net             .net   --entity-framework
## [5] .net   --wpf              .net   --linq

Di seguito si riporta una prima rappresentazione grafica riguardante i vari applicativi. Mediante la library networkD3 è possibile “navigare” nella rete per osservare i vari collegamenti tra i nodi presenti.

Una migliore visualizzazione della rete può essere fatta in funzione della variabile Gruppi, la quale consente una migliore visualizzazione e interpretazione delle relazioni tra i nodi della rete.

Come si evince dalla figura, diversificando i vertici in base ai rispettivi labels, si giunge alla conclusione che la maggior parte dei 14 gruppi che sussistono sono tra loro ben diversificati.

CENTRALITY MEASURES

La centralità permette di identificare all’interno di una rete i nodi più importanti.
Esistono diverse misure per quantificare la centralità di una rete:

  • DEGREE CENTRALITY
    Il degree di un nodo, \(d(i)\), in un grafo è dato dal numero di linee ad esso incidenti e può assumere un minimo di \(0\), se privo di legami con altri nodi, ed un massimo di \(g-1\) cioè connesso a tutti gli altri nodi.
    La degree centrality è la misura più semplice di centralità, ed è data dal numero di archi che si collegano ad un nodo.

    \[C_{degree}(n_{i})=d(n_{i})\]

    dove \(d(n_{i})\) è il grado calcolato per ciascun nodo.

  • CLOSENESS CENTRALITY
    Misura la distanza di un nodo da tutti gli altri nodi, quindi è considerata una misura di centralità globale.
    Il valore di closeness di un nodo stima il grado di vicinanza del nodo dal resto dei nodi del grafo. Di conseguenza un vertice avrà un grado di centralità tanto elevato quanto più sarà vicino agli altri nodi.

    \[C_{centrality}(n_{i})=\Bigg(\sum_{k=1}^g(n_{i},n_{j})\Bigg)^{-1}\] questa misura varia tra 0 e 1.

  • BETWEENNESS CENTRALITY
    Misura l’importanza di un nodo della rete sulla base della quantità di shorthest paths, ovvero distanze geodesiche, di cui fa parte. La centrality betweenness quantifica il ruolo di mediatore di ogni nodo nella rete. \[C_{Betweenness}(n_{i})=\sum \dfrac{g_{ab}(n_{i})}{g_{ab}}\] dove \(g_{ab}(n_{i})\) sono il numero di shorthest paths tra due nodi che includono sul loro cammino il nodo \(n(i)\).

  • EIGENVECTOR CENTRALITY
    L’eigen centrality differisce dalla degree centrality perchè quest’ultima tiene solo conto di quanti nodi sono collegati ad un dato nodo. Per l’eigen centrality invece, non è detto che un nodo con molti legami abbia un punteggio di centralità.
    Data la matrice di adiacenza \(A\) di un grafo, e \(\lambda\) è l’autovalore più grande di \(A\), l’eigen centrality del nodo \(i\) sarà: \[x_{i}=\dfrac{1}{\lambda}\sum_{j=1}^NA_{i}x{}j\] lo score della centralità per l’\(i-esimo\) nodo sarà proporzionale alla somma dei punteggi di tutti i nodi collegati ad \(i\).
    Il punteggio del nodo dipende non con “quanti” ma “da chi” è in relazione; infatti un nodo sarà importante (cioè avrà un elevato punteggio) se è collegato ad altri nodi importanti, e viceversa.

Mediante un barplot è possibile osservare la distribuzione delle frequenze in relazione alla degree centrality.

Inoltre, con la funzione which.max si perviene al nodo che presenta il degree massimo nella rete, in questo caso jquery che ha 16 collegamenti.

## jquery 
##     16

NETWORK STRUCTURE

La densità è il numero attuale di archi in proporzione al numero massimo di possibili archi. Più sono numerose i nodi direttamente collegati fra loro più un grafo è denso. La densità di un grafo si calcola come rapporto tra il numero di legami osservato e il numero di tutti i legami possibili tra i nodi, data la numerosità dei nodi.

\[Density(G)=\dfrac{L}{\dfrac{g(g-1)}{2}}\]

dove L sono le linee, g è il numero di nodi nel grafo. Tale misura è compresa tra 0 e 1

## [1] 0.0747521

Un’altrà interessante caratteristica di una rete è quella di verificare il livello di assortatività.
Il coefficiente di assortatività misura la tendenza di un nodo nella rete a collegarsi a dei nodi ad esso simili per diversi motivi.
L’assortatività viene spesso associata ad una misura di correlazione tra due nodi in relazione al loro grado, infatti essa può variare tra -1 e 1.
Se l’assortatività è elevata significa che i vertici collegati tendono ad avere una stessa categoria di riferimento, viceversa se è negativa.
Per calcolare l’assortatività globale si è utilizzata la variabile Gruppi, per capire se effettivamente nodi con la stessa etichetta avessero una tendenza a legarsi, oppure no.

## [1] 0.8770734

L’ouput mostra un’elevata tendenza dei nodi simili a collegarsi tra loro.
A questo punto si è calcolata l’assortatività nell’ipotesi che i labels di Gruppi fossero assegnate in modo casuale ai nodi del grafo.

A questo punto si è costruita una rappresentazione grafica mediante un istogramma della distribuzione teorica dell’assortatività (estremamente bassa) messa a confronto con l’assortatività osservata.

COMMUNITY DETENCTION

Per comunità, nell’ambito delle reti sociali, si intende strutture nascoste che sono composte da nodi fortemente connessi tra loro e scarsamente connessi con nodi appartenenti ad altre comunità nella stessa rete relazionale.
In letteratura un’altra possibile definizione delle comunità, è quella di considerarle come delle strutture autonome che singolarmente vanno ad influenzare la globalità della rete.  Di conseguenza lo scopo della community detection è quello di identificare gruppi di nodi con un’elevata intra-connettività, ovvero legami forti all’interno del gruppo, mediante l’analisi della topologia della rete. Il dataset utilizzato in questo studio presenta la variabile Gruppi che è stata ottenuta mediante l’implementazione dell’algoritmo Walktrap alla rete.

Walktrap Algorithm

L’algoritmo Walktrap è stato ideato da Pascal Pons, e permette di identificare le comunità in grandi reti tramite l’implementazione di random walks.
Innanzitutto al fine di comprendere il funzionamento dell’algoritmo è indispensabile introdurre il random walk. Il random walk è un processo che inizia da un vertice e ad ogni passo si muove verso un altro vertice. Nei grafi non pesati il “camminatore” sceglierà tra i nodi vicini a quello su cui si trova al momento, il vertice su cui spostarsi in modo del tutto casuale con la stessa probabilità tra tutti i possibili vicini. Considerato invece un grafo \(G(V,E)\) pesato e non orientato, il random walker deciderà su quale nodo spostarsi in relazione al peso dell’arco che collega i nodi: maggiore è la forza del legame tra due nodi, tanto è più probabile che il camminatore sceglierà di passare su quell’arco. In formule, la probabilità del random walker di passare dal nodo \(i\) al tempo \(t\), al nodo \(j\) al tempo \(t+1\) è data da: \[p_{t+1}(j)=\sum_{(j,i) \in E} \dfrac{w(j,i)}{d(i)}p_{t}(i) \] dove \(w(j,i)\) è il valore dell’arco che lega i \(n_{j}\) e \(n_{i}\), \(d(i)\) è il degree del nodo \(i\) e \(p_{t}(i)\) è la probabilità che il camminatore era al tempo \(t\) sul \(n_{i}\).

Tornando all’algoritmo, esso consiste in un clustering gerarchico di tipo bottom-up (agglomerativo) basato sui random walks per quantificare la distanza tra i nodi. L’idea di base è che il percorso più breve fatto dai random walkers sia circoscritto in una comunità, ovvero che il punto di partenza e quello di arrivo facciano parte del medesimo cluster; questo perchè in una comunità tendono ad esserci molti più legami tra i nodi al suo interno che tra due nodi di comunità differenti.
L’algoritmo inizia considerando l’inesistenza di una partizione nella rete, e vengono calcolate tutte le distanze tra i nodi adiacenti, dopodicchè sulla base dei risultati ottenuti dai random walkers immessi nella rete, 2 comunità adiacenti verranno unite, e verranno aggiornate nuovamente tutte le distanze.

Leading Eigen Algorithm

Questo algoritmo è stato proposto da Newman nel 2006, il suo nome deriva dall’utilizzo dello spettro della matrice di modularità, ovvero usando gli autovalori e autovettori della matrice. Considerando la matrice di adiacenza \(A\) di un grafo, gli autovalori \(\lambda\) si ottengono come soluzione dell’equazione \(|A-\lambda I|=0\) e, per ogni valore di \(\lambda\) si otterrà il relativo autovettore mediante l’identità \(Au=\lambda u\).
Tuttavia quest’algoritmo non usa direttamente la matrice di adiacenza, bensì quella di modualità \(M\), dove ogni elemento \(M_{ij}\) sarà ottenuto come: \[M_{ij}=\dfrac{ A_{ij}-d_{i}d_{j}}{2m}\] dove \(m\) è il numero totale di archi nella rete, mentre \(d_{i}\) e \(d_{j}\) sono i gradi rispettivamente del nodo \(i\) e \(j\).
Una volta trovati gli autovalori \(\lambda\) e i relativi autovettori si \(M\), si considera l’autovettore con l’autovalore più grande, da qui il nome leading eigenvector, e si creano due partizioni della rete in base al segno dell’elemento corrispondente sull’autovettore, in questo modo si è andati a massimizzare la modularità rispetto al primo autovettore. Successivamente viene nuovamente calcolata la matrice \(M\) e si esegue uno split della rete osservando lo stesso criterio del passo precedente. L’algoritmo si ferma quanto il contributo della modularità diventa negativo.

Edge-Betweenness Algorithm

L’algoritmo Edge-Betweenness fu proposto da Girvan e Newman nel 2011 e, il suo funzionamento si basa sul concetto della edge-betweenness centrality, descritta nel capitolo precedente.
Un modo alternativo per trovare comunità di vertici in una rete è cercare gli archi che si trovano tra le comunità.
Si calcolano i punteggi edge-betweenness di tutti gli archi nella rete, quindi si individua l’arco con il punteggio più alto e lo si rimuove. Rimuovendo l’arco si modificheranno i punteggi edge-betweenness di altri archi, perché tutti i percorsi più brevi che in precedenza attraversavano l’arco rimosso dovranno ora essere reindirizzati in un altro modo.
A questo punto si ricalcolano i punteggi edge-betweenness di tutti gli altri dopo la rimozione, e verrà individuato nuovamente l’arco che presenta la centralità edge-betweenness più elevata, e verrà rimosso. Questo procedimento verrà iterato finchè ogni nodo non rappresenta una comunità a sè stante. Il progresso dell’algoritmo può essere rappresentato utilizzando un dendrogramma, dove per ogni suo livello si può osservare come l’algoritmo ha lavorato scindendo la rete in gruppi.
Spetta all’utente decidere quale delle tante divisioni rappresentate è più utile per i propri scopi, tuttavia di default il software R seleziona la partizione che va a massimizzare la modularità della rete.

Propagating Label

A differenza di altri algoritmi di rilevamento della comunità, il Propagating Label non ottimizza alcuna funzione obiettivo e non richiede di avere informazioni a priori sulla struttura della rete.
Inizialmente ogni nodo ha la sua etichetta univoca (corrispondente alla sua comunità) e durante un processo iterativo i nodi ottengono l’etichetta che è frequente nel loro vicinato, ovvero i nodi ad esso più prossimi. Ad ogni iterazione, ogni nodo aggiorna la sua etichetta in relazione all’etichetta più frequente tra i suoi vicini. Man mano che le etichette si propagano, i nodi nel medesimo gruppo raggiungono rapidamente un consenso su un’etichetta, a questo punto l’algoritmo si fermerà, producendo gruppi densamente connessi al loro interno e fortemente sconnessi tra di loro.
L’intuizione alla base dell’algoritmo è che una singola etichetta può rapidamente diventare dominante in un gruppo di nodi densamente connesso, ma avrà problemi ad attraversare una regione scarsamente connessa. Le etichette rimarranno “intrappolate” all’interno di un gruppo di nodi estremamente collegati, e i nodi aventi la stessa etichetta, al terminare delle iterazione dell’algoritmo, verranno considerati parte della stessa comunità.
Ad ogni nodo viene assegnata un’etichetta di comunità univoca ed identificativa. Tuttavia una caratteristica interessante di questo algoritmo è che ai nodi possono essere assegnate etichette preliminari per inizializzare l’algorimto; ciò rende quest’approccio sia supervisionato che non.

Louvaine

L’algoritmo Louvaine fu proposto proposto da Blondel, esso cerca di partizionare la rete in modo iterativo, migliorando la qualità del partizionamento finchè il guadagno in termini di modularità non diventa trascurabile.
La modularità è una misura ampiamente utilizzata per valutare la bontà di un partizionamento di una rete in comunità. L’idea fondante è che prendendo una rete casuale al suo interno non esisterà una struttura di comunità e, tale struttura potrà essere usata per confrontare reti che invece hanno una struttura divisibile in comunità.
Teoricamente la modularità viene definita come la porzione di archi che cadono nei gruppi identificati (dall’algoritmo che si usa) meno la porzione attesa di archi se questi ultimi fossero distribuiti in maniera casuale. In formule il valore della modularità si calcola come:

\[ M=\frac{1}{2E}\sum \Bigg(A_{ij}-\frac{k_{i}k_{j}}{2E}\Bigg)\delta(c_{i},c{j}) \] \(A_{ij}\) è la matrice di adiacenza della rete e il suo elemento \(a_{ij}\) rappresenta il numero di archi che connettono i nodi \(i\) e \(j\).
I gradi dei nodi \(i\) e \(j\) sono indicati rispettivamente da \(k_{i}\) e \(k_{j}\), ed \(E\) rappresenta il numero totale di archi nella rete.
La quantità \(\delta(c_{i},c{j})\) vale \(1\) se i due nodi considerati si trovano nella stessa comunità, altrimenti \(0\).
E’ diviso in 2 fasi: ottimizzazione della modularità e aggregazione della comunità.

  1. OTTIMIZZAZIONE DELLA MODULARITÀ

    Inizialmente, ogni vertice è assegnato ad una propria comunità, ad ogni iterazione, per ciascuno dei vertici nella rete viene calcolato il guadagno in termini di modularità \(\Delta Q\) se venisse spostato ciascun vertice nelle comunità ad esso prossime. Se questo guadagno è positivo allora il vertice viene spostato in quelle comunità dalla sua attuale. La prima fase dell’algoritmo procede finché il guadagno in termini di modularità tra due iterazioni successive non risulta essere significativo, fissata una soglia specificata dall’utente.

    2. \[ \Delta M=\Bigg[\frac{\sum_{in}+2k_{i,in}}{2m}-\Bigg(\sum_{tot}+k_{i}^2\Bigg)\Bigg]-\Bigg[\frac{\sum_{in}}{2m}-\Bigg(\frac{\sum_{tot}}{2m}\Bigg)^2-\Bigg(\frac{k_{i}}{2m}\Bigg)^2\Bigg] \]

    Dopo che il primo passaggio è stato completato, segue il secondo. Entrambi verranno eseguiti fino a quando non ci saranno più modifiche nella rete e non verrà raggiunta la massima modularità.

  2. AGGREGAZIONE DI COMUNITA’

    Nella seconda fase tutti i nodi appartenenti alla stessa comunità vengono raggruppati in un unico grande nodo, e gli archi che collegano i nodi più grandi sono la somma di quelli che collegavano in precedenza i nodi delle stesse comunità. Quando una fase termina, il grafo per la fase successiva viene ricostruito, facendo collassare tutti i vertici all’interno di una comunità in un unico meta-vertice, e il processo viene continuato fino a quando non si ottiene alcun guadagno apprezzabile di modularità tra fasi consecutive.

COMPARISONS

La complessità degli algoritmi può essere trattata con la notazione matematice del Big O. Mediante questa scrittura è possibile osservare per i vari algoritmi di community detection diverse soglie di complessità computazionale, dove con \(N\) si indica il numero di vertici ed \(E\) il numero di archi:

ALGORITMO CRITERIO COMPLESSITA’
WALKTRAP RANDOM WALK \(O(N^2E)\)
LABEL PROPAGATION NEIGHBORHOOD \(O(N+E)\)
LEADING EIGENVECTOR EIGEN VECTORS \(O(N(N+E))\)
LOUVAIN MODULARITY \(O(E)\)
EDGE BETWEENNESS CENTRALITY \(O(NE^2)\)

Di seguito invece è possibile osservare per ogni nodo nella rete, come i diversi algoritmi utilizzati precedentemente si sono comportati nel classificare quel vertice in confronto alle etichette iniziali assegnate dall’algoritmo Walktrap.

Per comparare questi diversi approcci si è ricorsi a misure di valutazione esterne, quali: l’Adjusted Rand Index, Normalized Mutual Information e Variation of Information.

  • Adjusted Rand Index: E’ una misura di similarità per due differenti partizioni compresa tra \(0\) e \(1\). Dato un set di elementi \(S={N_{1},N_{2},...,N}\), e due partizioni di \(S\), \(X\) e \(Y\), l’indice ARI è definito nel seguente modo:
    \[Adj\ Rand\ Index= \dfrac{SS+DD}{SS+SD+DS+DD}\] dove \(SS\) è il numero di coppie di elementi in \(S\) che si trovano nello stesso sottogruppo sia in \(X\) che in \(Y\), \(DD\) è invece il numero di coppie di elementi in \(S\) che si trovano in sottogruppi differenti sia in \(X\) che in \(Y\). \(SD\) invece è il numero di coppie in \(S\) che si trovano nello stesso sottoinsieme in \(X\) ma in diversi sottoinsiemi in \(Y\), viceversa per \(DS\). Nel nostro caso l’algoritmo Walktrap, rappresentante la partizione iniziale \(S\), è stato comparato con gli altri \(4\) algoritmi. Un valore dell’indice maggiore implica una maggiore similarità tra le comunità ottenute.
  • Normalized Mutual Information: E’una misura d’informazione che quantifica la mutua dipendenza tra 2 variabili casuali \(X\) e \(Y\), e può essere applicata anche a 2 partizioni al fine di valutare quanta informazione può essere ottenuta in una partizione mediante l’altra.
    Si calcola come: \[NMI(X,Y)= \dfrac{2\ I(X,Y)}{H(X)+H(Y)}\] dove l’informazione \(I(X,Y)\) è ottenuta con la divergenza di Kullback-Leibler della distribuzione di probabilità congiunta delle due variabili \(X\) e \(Y\). Se la distribuzione congiunta è nulla significa che le due variabili sono indipendenti e il prodotto dei loro marginali coincide con la loro distribuzione congiunta.
    Al denominatore del rapporto c’è la somma delle entropie delle singole variabili/partizioni. Maggiore è il suo valore maggiore è la similarità tra X e Y.
  • Variation of Information: Quest’indice è molto simile al NMI in quanto misura anch’esso l’informazione tra due variabili casuali. La differenza sta nel fatto che la Variation of Information è una vera e propria metrica, così definita:
    \[VI(X,Y)= H(X|Y)+H(Y|X)\] dove X ed Y sono due diverse partizioni della rete, il VI indica il differenziale dell’informazione che sussiste tra esse. Al contrario degli altri due indici, le due partizioni saranno tanto simili al minimizzarsi del VI.

Dopo aver calcolato i 3 indici per tutti e 4 gli algoritmi usati è emerso che il peggiore è stato quello basato sulla matrice di autovettori e autovalori, mentre gli algoritmi basati sulla modularità e sulla centralità edge-betweenness hanno avuto discreti risultati. Il migliore sembra essere l’algoritmo basato sulla propagazione delle etichette, in quanto per gli indici ARI e NMI presenta i valori più elevati e minimizza più degli altri l’indici VI.
Il risultato di quest’algoritmo può trovare una risposta nel fatto che esso non è un vero e proprio approccio non supervisionato, in quanto in fase di costruzione dell’algoritmo sono state date le etichette trovate dal Walktrap per inizializzare il Label Propagating, e si deduce che ciò può aver portato all’identificazione di comunità molto simili tra i due algoritmi.