Топ-100
Indietro

ⓘ Coefficiente di clustering. Nella teoria dei grafi, il coefficiente di clustering è la misura del grado in cui i nodi di un grafo tendono ad essere connessi fra ..




Coefficiente di clustering
                                     

ⓘ Coefficiente di clustering

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

Levidenza 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.

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

                                     

1. Coefficiente di clustering locale

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 G = V, E {\displaystyle G=V,E} consiste formalmente di un insieme V {\displaystyle V} di vertici e un insieme E {\displaystyle E} di collegamenti. Un collegamento e i j {\displaystyle e_{ij}} connette un vertice v i {\displaystyle v_{i}} con un vertice v j {\displaystyle v_{j}}.

Linsieme N i {\displaystyle N_{i}} dei vicini di un vertice v i {\displaystyle v_{i}} è definito come linsieme dei nodi direttamente connessi ad esso:

N i = { v j: ⟨ e j i, e i j ⟩ ∈ E 2 }. {\displaystyle N_{i}=\{v_{j}:\left\langle e_{ji},e_{ij}\right\rangle \in E^{2}\}.}

Definiamo k i {\displaystyle k_{i}} come la cardinalità di | N i | {\displaystyle |N_{i}|}, ovvero il numero di vicini di un vertice v i {\displaystyle v_{i}}.

Il coefficiente di clustering locale C i {\displaystyle C_{i}} di un vertice v i {\displaystyle v_{i}} è dato dal numero di collegamenti fra i membri di N i {\displaystyle N_{i}} fratto il numero di collegamenti potenziali fra loro.

In un grafo orientato, e i j {\displaystyle e_{ij}} è distinto da e j i {\displaystyle e_{ji}}, dunque per ogni N i {\displaystyle N_{i}} ci sono k i k i − 1 {\displaystyle k_{i}k_{i}-1} collegamenti possibili fra i suoi membri. Di conseguenza, il coefficiente di clustering locale per grafi orientati è dato da:

C i = | { e j k: v j, v k ∈ N i, e j k ∈ E } | k i k i − 1. {\displaystyle C_{i}={\frac {|\{e_{jk}:v_{j},v_{k}\in N_{i},e_{jk}\in E\}|}{k_{i}k_{i}-1}}.}

La proprietà caratteristica di un grafo non orientato è invece che e i j {\displaystyle e_{ij}} e j i {\displaystyle e_{ji}} sono considerati identici, dunque per ogni N i {\displaystyle N_{i}} ci sono k i k i − 1 2 {\displaystyle {\frac {k_{i}k_{i}-1}{2}}} collegamenti possibili fra i suoi membri. Di conseguenza, il coefficiente di clustering locale per grafi non orientati è dato da:

C i = 2 ⋅ | { e j k: v j, v k ∈ N i, e j k ∈ E } | k i k i − 1. {\displaystyle C_{i}={\frac {2\cdot |\{e_{jk}:v_{j},v_{k}\in N_{i},e_{jk}\in E\}|}{k_{i}k_{i}-1}}.}
                                     

2. Coefficiente di clustering globale

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. Questo metodo può essere applicato sia ai grafi orientati che non orientati.

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

Supponiamo che un nodo v {\displaystyle v} abbia k v {\displaystyle k_{v}} vicini; allora possono esistere massimo k v k v − 1 / 2 {\displaystyle k_{v}k_{v}-1/2} collegamenti fra loro ciò accade quando tutti i vicini di v {\displaystyle v} sono connessi fra loro. Denotando con C v {\displaystyle C_{v}} la frazione di tali collegamenti che effettivamente esiste, si definisce C {\displaystyle C} come la media dei C v {\displaystyle C_{v}} fratto il numero di nodi.

Questultima definizione è equivalente alla prima se si utilizza la media ponderata, pesando ogni C v {\displaystyle C_{v}} con il numero di triple in cui il nodo è centrale:

C = 3 ⋅ n Δ G n ∧ G = ∑ i = 1 n C i ⋅ w i ∑ i = 1 n w i {\displaystyle C={\frac {3\cdot n_{\Delta }G}{n_{\land }G}}={\frac {\sum _{i=1}^{n}C_{i}\cdot w_{i}}{\sum _{i=1}^{n}w_{i}}}}.

Dove:

  • w i {\displaystyle w_{i}} è il peso del vertice v i {\displaystyle v_{i}} numero di triple in cui il nodo è centrale;
  • n Δ G {\displaystyle n_{\Delta }G} è il numero di triangoli del grafo;
  • n ∧ G {\displaystyle n_{\land }G} è il numero complessivo di triple del grafo;

Notare che ∑ i = 1 n w i ≡ n ∧ G {\displaystyle \sum _{i=1}^{n}w_{i}\equiv n_{\land }G}.

                                     

2.1. Coefficiente di clustering globale Esempio

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

3 ⋅ n Δ G n ∧ G = 3 11 ; {\displaystyle {\frac {3\cdot n_{\Delta }G}{n_{\land }G}}={\frac {3}{11}};} ∑ i = 1 n C i ⋅ w i ∑ i = 1 n w i = 1 ⋅ 1 + 1 3 ⋅ 3 + 1 3 ⋅ 3 1 ⋅ 2 + 3 ⋅ 3 = 3 11 ; {\displaystyle {\frac {\sum _{i=1}^{n}C_{i}\cdot w_{i}}{\sum _{i=1}^{n}w_{i}}}={\frac {1\cdot 1+{\frac {1}{3}}\cdot 3+{\frac {1}{3}}\cdot 3}{1\cdot 2+3\cdot 3}}={\frac {3}{11}};} ⇒ C = 3 11. {\displaystyle \Rightarrow C={\frac {3}{11}}.}
                                     
  • 1998 pubblicato su Nature in cui, insieme a Steven Strogatz, ha introdotto il coefficiente di clustering locale. EN Duncan Watts su Microsoft Research
  • avere un alto coefficiente di clustering globale. Questa teoria generalizza ed esplora le caratteristiche di insieme che hanno reti connesse di elementi
  • cresce si riduce e si avvicina a 1 - 1 evidenziando l esistenza di uno spatial clustering dei valori alti e o bassi e quindi autocorrelazione spaziale positiva
  • Reynolds number scaling of particle clustering in turbulent aerosols, su iop.org. Numero di Brinkman Numero di Fanning EN IUPAC Gold Book, Stokes
  • confrontare i clustering Corregge l effetto dell accordo tra i clustering dovuto unicamente al caso, simile al modo in cui l indice di Rand aggiustato
  • ad 1 perché è il coefficiente di correlazione di una variabile con se stessa. È pure una matrice simmetrica perché il coefficiente di correlazione tra
  • nei problemi di clustering ed altre tecniche di classificazione statistica. È strettamente legata alla Variabile casuale T - quadrato di Hotelling, usata
  • confrontare e valutare i metodi di clustering in citometria a flusso e per stabilire linee guida sull uso appropriato di questi metodi. Questa tecnologia
  • sviluppata per separare oggetti ed osservazioni in classi distinte clustering e per allocare nuove osservazioni in una delle classi precedentemente