Apri il menu principale

Coefficiente di clustering

Nella teoria dei grafi, il coefficiente di clustering (o transitività) è la misura del grado in cui i nodi di un grafo tendono ad essere connessi fra loro.

L'evidenza suggerisce che nella maggior parte delle reti del mondo reale, e in particolare nelle reti sociali, i nodi tendono a creare gruppi fortemente uniti e caratterizzati da una densità di collegamenti relativamente alta; il coefficiente di clustering delle reti reali tende quindi ad essere maggiore rispetto a quello dei grafi in cui i collegamenti sono generati casualmente.[1][2]

Può essere misurato in due modi diversi: globale e locale. Quello globale descrive in generale l'intensità del fenomeno di clustering nella rete, mentre quella locale riguarda il livello di radicamento dei singoli nodi.

Coefficiente di clustering localeModifica

 
Esempio di coefficiente di clustering locale in un grafo non orientato:
1. Nel primo caso, i collegamenti fra i vicini del nodo blu sono tre su tre, quindi il coefficiente risulta essere 1.
2. Nel secondo caso, i collegamenti sono uno su tre, quindi il coefficiente è 1/3.
3. Nel terzo caso i collegamenti sono inesistenti, quindi il coefficiente è nullo.

Il coefficiente di clustering locale di un nodo in un grafo è una misura di quanto i suoi vicini tendano a formare una cricca (o un grafo completo). Duncan J. Watts e Steven Strogatz introdussero questa misura nel 1998 per determinare se un grafo sia o meno una rete rientrante nella teoria del mondo piccolo.

Un grafo   consiste formalmente di un insieme   di vertici e un insieme   di collegamenti. Un collegamento   connette un vertice   con un vertice  .

L'insieme   dei vicini di un vertice   è definito come l'insieme dei nodi direttamente connessi ad esso:

 

Definiamo   come la cardinalità di  , ovvero il numero di vicini di un vertice  .

Il coefficiente di clustering locale   di un vertice   è dato dal numero di collegamenti fra i membri di   fratto il numero di collegamenti potenziali fra loro.

In un grafo orientato,   è distinto da  , dunque per ogni   ci sono   collegamenti possibili fra i suoi membri. Di conseguenza, il coefficiente di clustering locale per grafi orientati è dato da:[2]

 

La proprietà caratteristica di un grafo non orientato è invece che   e   sono considerati identici, dunque per ogni   ci sono   collegamenti possibili fra i suoi membri. Di conseguenza, il coefficiente di clustering locale per grafi non orientati è dato da:

 

Coefficiente di clustering globaleModifica

Il concetto di coefficiente di clustering globale è basato su triple di nodi. Una tripla consiste di tre nodi connessi da due (tripla aperta) o tre (tripla chiusa) collegamenti. Ogni tripla è incentrata su un nodo. Un triangolo consiste di tre triple chiuse incentrate sui tre stessi nodi che le compongono.

Il coefficiente di clustering globale è, dunque, il numero di triple chiuse (o 3 volte il numero di triangoli) fratto il numero totale di triple (somma di quelle aperte e chiuse). Il primo tentativo di misurarlo fu effettuato da Robert D. Luce e Albert D. Perry (1949).[3] Questo metodo può essere applicato sia ai grafi orientati che non orientati.[4]

Watts e Strogatz, invece, definirono il coefficiente di clustering come la media dei coefficienti locali:[5]

Supponiamo che un nodo   abbia   vicini; allora possono esistere massimo   collegamenti fra loro (ciò accade quando tutti i vicini di   sono connessi fra loro). Denotando con   la frazione di tali collegamenti che effettivamente esiste, si definisce   come la media dei   fratto il numero di nodi.

Quest'ultima definizione è equivalente alla prima se si utilizza la media ponderata, pesando ogni   con il numero di triple in cui il nodo è centrale:

 .

Dove:

  •   è il numero di triangoli del grafo;
  •   è il numero complessivo di triple del grafo;
  •   è il peso del vertice   (numero di triple in cui il nodo è centrale);

Notare che  .

EsempioModifica

 
Grafo non orientato a sei nodi. I vertici cerchiati in rosso sono centri di triple chiuse.

Nell'esempio sulla destra c'è un solo triangolo, formato dai vertici 1, 2 e 5. Le caratteristiche del grafo sono le seguenti:

Vertice Collegamenti
fra vicini
Peso Triple in cui il nodo è centrale
1 1 1 ⟨2,1,5⟩
2 1/3 3 ⟨1,2,3⟩, ⟨1,2,5⟩, ⟨3,2,5⟩
3 0 1 ⟨2,3,4⟩
4 0 3 ⟨3,4,5⟩, ⟨3,4,6⟩, ⟨5,4,6⟩
5 1/3 3 ⟨1,5,2⟩, ⟨1,5,4⟩, ⟨2,5,4⟩
6 0 0
 
 
 

NoteModifica

  1. ^ P. W. Holland, S. Leinhardt, Transitivity in structural models of small groups, in Comparative Group Studies, vol. 2, 1971, pp. 107–124.
  2. ^ a b D. J. Watts, S. H. Strogatz, Collective dynamics of 'small-world' networks, in Nature, vol. 393, nº 6684, giugno 1998, pp. 440–442, Bibcode:1998Natur.393..440W, DOI:10.1038/30918, PMID 9623998.
  3. ^ R. D. Luce, A. D. Perry, A method of matrix analysis of group structure, in Psychometrika, vol. 14, nº 1, 1949, pp. 95–116, DOI:10.1007/BF02289146, PMID 18152948.
  4. ^ Stanley Wasserman, Kathrine Faust, 1994. Social Network Analysis: Methods and Applications., p. 243. Cambridge: Cambridge University Press.
  5. ^ D. J. Watts, S. H. Strogatz, Figure 2 : Collective dynamics of 'small-world' networks, in Nature, vol. 393, nº 6684, giugno 1998, pp. 440–442, Bibcode:1998Natur.393..440W, DOI:10.1038/30918, PMID 9623998.

Altri progettiModifica