Coefficiente di clustering: differenze tra le versioni

Versione delle 11:22, 18 giu 2020

Versione attuale delle 19:04, 15 mar 2025

Riga 1:

Nella [[teoria dei grafi]], il '''coefficiente di clustering''' (o '''transitività''') è la misura del grado in cui i [[Vertice (teoria dei grafi)|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.<ref>{{Cita pubblicazione|autore= P. W. Holland, S. Leinhardt|titolo= Transitivity in structural models of small groups|anno= 1971|rivista= Comparative Group Studies|volume= 2|pp= 107–124107-124}}</ref><ref name=WattsStrogatz1998>{{Cita pubblicazione|autore= [[Duncan Watts|D. J. Watts]], [[Steven Strogatz|S. H. Strogatz]]|titolo= Collective dynamics of 'small-world' networks|anno= 1998|url= https://www.nature.com/nature/journal/v393/n6684/full/393440a0.html|rivista= [[Nature]]|volume= 393|pp= 440–442440-442|mese= giugno|doi = 10.1038/30918|pmid = 9623998|numero= 6684|bibcode=1998Natur.393..440W}}</ref>

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.

Riga 28:

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 Duncan Luce|Robert D. Luce]] e Albert D. Perry (1949).<ref>{{Cita pubblicazione|autore= [[Robert Duncan Luce|R. D. Luce]], A. D. Perry|titolo= A method of matrix analysis of group structure|anno= 1949|rivista= Psychometrika|volume= 14|pp= 95–11695-116|doi = 10.1007/BF02289146|numero= 1|pmid=18152948}}</ref> Questo metodo può essere applicato sia ai grafi orientati che non orientati.<ref>Stanley Wasserman, Kathrine Faust, 1994. ''Social Network Analysis: Methods and Applications.'', p. 243. Cambridge: Cambridge University Press.</ref>

Watts e Strogatz, invece, definirono il coefficiente di clustering come la media dei coefficienti locali:<ref>{{Cita pubblicazione|autore=[[Duncan Watts|D. J. Watts]], [[Steven Strogatz|S. H. Strogatz]]|titolo=Figure 2 : Collective dynamics of 'small-world' networks|anno=1998|url=https://www.nature.com/nature/journal/v393/n6684/fig_tab/393440a0_F2.html|rivista=[[Nature]]|volume=393|pp=440–442440-442|mese=giugno|doi=10.1038/30918|pmid=9623998|numero=6684|bibcode=1998Natur.393..440W}}</ref>

:<dfn>Supponiamo che un nodo <math>v</math> abbia <math>k_v</math> vicini; allora possono esistere massimo <math>k_v(k_v - 1)/2</math> collegamenti fra loro (ciò accade quando tutti i vicini di <math>v</math> sono connessi fra loro). Denotando con <math>C_v</math> la frazione di tali collegamenti che effettivamente esiste, si definisce <math>C</math> come la media dei <math>C_v</math> fratto il numero di nodi.</dfn>