Coefficiente di clustering: differenze tra le versioni

Versione delle 16:39, 30 apr 2019

Versione delle 11:15, 25 feb 2020

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–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 (journal)|Nature]]|volume= 393|pp= 440–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 30:

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–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 (journal)|Nature]]|volume=393|pp=440–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>