Matrice di adiacenza

7 minuti - per Elisa Barisani

La matrice di adiacenza di una rete di N nodi ha N righe e N colonne.

Esempio: la matrice di adiacenza per i nodi e i collegamenti delle reti della Figura 1 ha 3 righe e 3 colonne, corrispondenti ai nodi.

La matrice di adiacenza di una rete è diversa tra reti dirette (in cui la distinzione tra source, il nodo di origine di un collegamento, e target, il nodo che è la destinazione del collegamento, è significativa per tutti i nodi della rete) e indirette (in cui la direzione di tutti i collegamenti non è significativa).

Esempio: nella Figura 1-A è rappresentata una rete sociale indiretta in cui il collegamento indiretto è quello di ‘amicizia’ (o ‘è amica/o di’): se Sofia è amica di Andrea, allora Andrea è amico di Sofia. Nel caso rappresentato in questa rete, Andrea e Sofia sono legati da un legame di amicizia, così come Sofia e Greta; quest’ultima, tuttavia, non ha un legame di amicizia con Andrea.

Un esempio di rete sociale diretta è invece rappresentato nella Figura 1-B, dove il collegamento diretto è quello di ‘corrispondenza per mail’ (o ‘invia una mail’). In questo caso è necessario specificare la distinzione tra mittente e destinatario e la direzione del collegamento è significativa. In questa rete Sofia invia una mail ad Andrea e riceve una mail da Greta.

Gli elementi della matrice di adiacenza di una rete indiretta sono :

• A_ij = 1, se c'è un collegamento tra il nodo j e il nodo i

• A_ij = 0, se non c’è un collegamento tra il nodo j al nodo i

Nel caso di una rete indiretta, la matrice di adiacenza ha due voci per ogni collegamento. Quindi, la matrice di adiacenza di una rete indiretta è simmetrica.

Esempio: il collegamento (Sofia, Andrea) nella rete della Figura 1-A è rappresentato come A_Sofia,Andrea = 1 e A_Andrea,Sofia = 1 e la matrice di adiacenza della rete è quindi simmetrica: A_Sofia,Andrea = A_Andrea,Sofia (Figura 2).

Nella matrice di adiacenza di una rete diretta, gli elementi sono:

• A_ij = 1, se c'è un collegamento che punta dal nodo j al nodo i

• A_ij = 0, se non c’è un collegamento che punta dal nodo j al nodo i

È possibile rappresentare la matrice di una anche in forma tabulare.

Esempio: di seguito viene rappresentata la matrice in forma tabulare della rete indiretta illustrata nella Figura 1-A:

Figura 1-a. Matrice tabulare della figura 1-a.

Questa matrice, quindi, indica che Andrea ha un legame con Sofia ma nessuno con Greta; Sofia, a sua volta, ha legami con Andrea e Greta che ha un legame solamente con Sofia.

Di seguito viene invece rappresentata la matrice in forma tabulare della rete sociale diretta della Figura 1-B:

Figura 1-b. Matrice tabulare della figura 1-b.

Questa matrice indica che Sofia invia una mail ad Andrea e che Greta, a sua volta, invia una mail a Sofia.

Come si può vedere dagli esempi precedenti, il rapporto di una persona con se stessa è sempre "zero".

A partire da una matrice è possibile estrarre numerose misure da un grafo ed è possibile ricavare alcune metriche di ‘potere’ degli individui all’interno di una rete sociale. Per esempio, è possibile estrarre il degree (k), che indica il numero di collegamenti di un nodo (o attore sociale) all’interno di una rete, e che quindi misura quanto un attore sociale è connesso rispetto agli altri. Per le reti non dirette il degree di un nodo è la somma sulle righe o sulle colonne della matrice, e corrisponde a:

Esempio: il degree del nodo Greta nella rete 1-A è 1, perché la somma sulle righe della matrice è uno (ed è uguale alla somma sulle colonne della matrice):

A_ij = A_ji

Per le reti dirette, le somme sulle righe e sulle colonne della matrice di adiacenza forniscono rispettivamente i degree in entrata e in uscita:

Esempio: il nodo Greta nella rete 1-B ha il degree in entrata uguale a zero, e quello in uscita uguale a uno:

Maggiore è il degree di un nodo maggiore sarà la sua influenza all’interno della rete, dal momento che maggiore è il degree, maggiore è la libertà del nodo nella scelta dei legami e la sua indipendenza da altri.

A partire dalla matrice di adiacenza di una rete è possibile anche individuare il numero di archi totali. Dal momento che in una rete indiretta il numero di collegamenti in uscita è uguale al numero di collegamenti in entrata, si ha:

Il numero di elementi non nulli della matrice di adiacenza è 2L, ovvero il doppio del numero degli archi. Infatti, un collegamento indiretto che collega i nodi i e j appare in due voci: A_ij = 1, un collegamento che punta dal nodo j al nodo i, e A_ji = 1, un collegamento che punta da i a j (Figura 1-B).

Dunque, per una rete indiretta è possibile ricavare il numero di archi totali a partire da una matrice con la seguente formula:

E per una rete diretta è possibile ricavare il numero di archi totali a partire da una matrice con la seguente formula:

Le matrici di adiacenza implementano un tipo di dato molto diverso dai data frame che vengono generalmente utilizzati per compiere analisi sulle reti sociali, per esempio attraverso appositi software di analisi delle reti sociali. Oltre alla rappresentazione con matrici di adiacenza, i dati di una rete sociale possono essere rappresentati attraverso nodelist o edgelist. Sarebbe infatti consigliabile avere un elenco che indichi i nodi e le loro relazioni e quindi creare una edgelist, che può essere integrata attraverso una nodelist che contiene informazioni aggiuntive sulle caratteristiche dei nodi.

Esempio: per la Figura 1 una edgelist corrisponde a un elenco che indica le persone e le loro relazioni, mentre una nodelist corrisponde ad un elenco che indica tutte le persone nella rete ed eventualmente dei loro attributi.

Bibliografia e sitografia

Citazione di questo articolo

Come citare: BARISANI, Elisa . "Matrice di adiacenza". In: CLIOMATICA - Portale di Storia Digitale e ricerca. Disponibile in: http://lhs.unb.br/cliomatica/index.php/Matrice_di_adiacenza. il giorno: 27/06/2024.

Informare errori in questa pagina