Densità di un grafo

Sia definito il grafo G=(N,A) come coppia dei due insiemi N:={1,2,3,...,n} ed A sottinsieme del prodotto cartesiano N×N. N sarà l'insieme degli n nodi che compongono il suddetto grafo e A l'insieme degli archi.

  • sia n la cardinalità di N (ovvero il numero dei nodi di un dato)
  • sia L la cardinalità di A (ovvero il numero degli archi dello stesso grafo)

Se le coppie di nodi si considerano ordinate il grafo è detto orientato o digrafo, altrimenti non orientato o semplice. Il grafo è detto pesato se ad ogni arco è associato un peso o costo.

La densità di un grafo semplice (Δ) o non orientato è definita come:

Δ = 2L / n(n-1)

La densità di un grafo (Δ) orientato è definita come:

Δ = L / n(n-1)

Nel caso di grafi pesati ad L occorre sostituire la sommatoria dei pesi di ciascun arco.

La densità di un grafo assume valori compresi tra 0 ed 1 e pertanto si può ricollegare facilmente al concetto di probabilità. La densità di un grafo misura la probabilità che una qualsiasi coppia di nodi sia adiacente, mentre la connessione di un grafo dipende dalla distribuzione degli archi tra i nodi.

Un grafo disconnesso può avere densità maggiore di uno connesso a causa della concentrazione degli archi tra un ristretto numero di nodi.

EsempiModifica

Grafi completi non orientatiModifica

Si abbia un grafo completo non orientato   con n=1,2,3,...,8.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

La densità del grafo completo monopartito   è sempre pari ad uno.

Grafi bipartitiModifica

Supponiamo di considerare il seguente grafo non orientato ciclico (detto grafo bipartito):   . È possibile facilmente verificare che la sua densità è circa uguale a 0,28.

Applicazione alle reti socialiModifica

Un gruppo di individui tra cui esistano o meno delle relazioni è rappresentabile matematicamente attraverso un grafo. Anche più gruppi di individui sono schematizzabili in egual maniera.

In generale:

  1. Diversi attori (entità sociali) instaurano o meno tra loro delle relazioni.
  2. Gli attori non coincidono necessariamente con le singole persone, ma possono essere enti, città, nazioni, ecc.
  3. Le relazioni possono essere di tipo emozionale (amicizia, amore, autorità, discendenza, rapporti di lavoro)

oppure possono esprimere connessioni fisiche (ponti, strade) o ancora trasferimenti di risorse.
La densità nel grafo che rappresenta una rete sociale può essere un parametro che rappresenta l'efficienza nello scambio di informazioni e l'utilità per i singoli individui. Nelle opere di Mark Granovetter inoltre è evidenziato come reti piccole e dense possono essere meno utili di reti costituite da legami deboli, perché queste ultime sono più flessibili prestandosi quindi a un miglior scambio di idee e opportunità.

RiferimentiModifica

Voci correlateModifica