Il grado (degree) di un nodo è il numero di archi che il nodo possiede.
Nel grafo riportato in figura, il grado del nodo N3 è pari a 4, il grado del nodo N6 è pari a 3 e il grado del nodo N4 è pari a 2.
Formalmente, per un grafo indiretto di n nodi, il grado di ciascun nodo può essere calcolato a partire dalla sua matrice di adiacenza, così come espresso dalla formula seguente:
\(k_{i} = \sum_{j=1}^n A_{i, j} \)
dove \(k_{i} \) indica il grado del nodo i. Per cui, rispetto al grafo della figura precedente, abbiamo che \(k_{3} = 4 \), \(k_{6} = 3\) e \(k_{4} = 2\).
Se chiedessimo ad un nostro amico “hai dei fratelli o delle sorelle?”, la sua risposta stabilirebbe il suo grado, che sarà pari a 0 nel caso in cui il nostro amico è figlio unico, 1 se ha un fratello o una sorella, 2 se ha più di un fratello o una sorella e così via.
Nei grafi indiretti come quelli che stiamo analizzando, il verso degli archi non è importante. Ogni arco, non è altro che un segmento da un nodo a ad un nodo b. Ogni vertice di questo segmento è detto estremità.
In un grafo di m archi esisteranno in totale 2m estremità, come è possibile constatare dalla figura che segue, dove le estremità di ogni arco sono state evidenziate in giallo.
Da qui una prima semplice intuzione: il numero di estremità di un grafo indiretto corrisponde alla somma dei gradi di tutti i nodi del grafo. Ricordando che \(k_{i} \) rappresenta il grado del nodo i-esimo, possiamo formalizzare il concetto appena descritto con la seguente formula:
\(2m = \sum_{i=1}^n k_{i}\)
Dalla formula appena riportata possiamo ricavare una nuova formula (equivalente alla precedente):
\(m = \frac{1}{2} \sum_{i=1}^n k_{i} = \frac{1}{2} \sum_{i, j} A_{i, j}\)
che formalizza così una seconda importante intuizione: il numero di archi in una rete indiretta può essere espresso come somma dei gradi dei nodi del grafo diviso 2.
L’utilizzo del fattore \(\frac{1}{2} \) ci permette di evitare di contare due volte lo stesso arco.
Il grado medio dei nodi
In un grafo indiretto
Sulla scia delle semplici formule appena descritte è possibile calcolare il grado medio (mean degree) c di un nodo in un grafo indiretto con la seguente formula:
\(c = \frac{1}{n} \sum_{i=1}^n k_{i}\)
Se sostituiamo a questa formula \(\sum_{i=1}^n k_{i} \) con 2m, otteniamo una relazione che ci sarà utile più avanti:
\(c = \frac{2m}{n} \)
Definiamo così il grado medio dei nodi di una rete in funzione del rapporto tra le estremità del grafo (2m) ed il numero totali di nodi (n).
In un grafo diretto
In un grafo diretto, è importante distinguere il grado degli archi entranti \(k_{i}^{in} \) dal grado degli archi uscenti \(k_{i}^{out} \).
Il grado totale di un nodo i sarà data dalla somma dei suoi archi entranti più la somma dei sui archi uscenti. Per cui:
\(k_{tot} = k_{i}^{in} + k_{i}^{out}\)
da cui
\(k_{tot} = \sum_{i=1}^n k_{i}^{in} + \sum_{i=1}^n k_{i}^{out} \)
Il numero totale di archi in una rete diretta invece, è dato da:
\(m = \sum_{i=1}^n k_{i}^{in} = \sum_{i=1}^n k_{i}^{out} \)
da cui si ricava la formula del grado medio dei nodi in una rete diretta:
\(c^{in} = \frac{1}{n} \sum_{i=1}^n k_{i}^{in} = c_{out} = \frac{1}{n} \sum_{i=1}^n k_{i}^{out} \)
Degree distribution
La distribuzione dei gradi (degree distribution) di una rete è la probabilità \(p_{k} \) per cui, scegliendo in maniera casuale un nodo i della rete, esso possieda esattamente un grado k.
La probabilità \(p_{k} \) va normalizzata in modo che
\(\sum_{k=1}^\infty p_{k} = 1 \)
In una rete con n nodi, la distribuzione dei gradi è data dall’istogramma normalizzato della relazione
\(p_{k} = \frac{N_{k}}{N} \)
dove \(N_{k} \) è il numero di nodi con grado k, mentre \(N \) è il numero di nodi totali .
La degree distribution è un concetto molto importante nello studio delle reti. Essa ci sarà utile quando parleremo ad esempio di scale-free networks e di altri concetti legati alle dinamiche di sviluppo di alcuni fenomeni su reti. Ad esempio, lo studio della diffusione di un’epidemia fa uso di questo concetto.