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.
È un’analisi che si basa sui dati relazionali, ovvero contatti,collegamenti, vincoli che mettono in relazione più soggetti tra loro, che prendono il nome di attori.
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. È possibile notare che 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 fd9a111 DN-- 4 9 -- 
## + attr: name (v/c)
## + edges from fd9a111 (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. Essi 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 ...

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.

Mediante la library igraph è possibile costruire il grafo dando come input la node list e l’edge list:

La rete così costruita non è orientata, ciò comporta un particolare approccio all’analisi, per quanto riguarda la fase di community detenction.

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.

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.

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 delle 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.

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.

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.
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.
Il random walk è un processo che parte da un vertice e ad ogni passo si muove verso un altro vertice.
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}\).

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.
L’algoritmo parte 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\).

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, ed è un metodo top-down e il suo operato può essere quindi visualizzato mediante un dendogramma.
Il suo principio è quello di trovare comunità di vertici in una rete cercando gli archi che si trovano tra le comunità.

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.
La sua più interessante caratteristica è l’essere un algoritmo semi-supervisionato, in quanto, di default ad ogni nodo viene assegnata un’etichetta univoca che lo contraddistingue, tuttavia un’altra opzione è quella di assegnare delle etichette preliminari ai nodi per inizializzare l’algoritmo. Infatti quando abbiamo applicato l’algoritmo alla rete, sono state date in input le etichette della variabile \(Gruppi\) presente nel dataset.

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.