Coefficiente di clustering: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
nuova voce in preparazione
 
Riga 43:
Watts e Strogatz, invece, definirono il coefficiente di clustering come la media dei coefficienti locali:<ref>{{Cite journal|author=[[Duncan Watts|D. J. Watts]], [[Steven Strogatz|S. H. Strogatz]]|title=Figure 2 : Collective dynamics of 'small-world' networks|year=1998|url=http://www.nature.com/nature/journal/v393/n6684/fig_tab/393440a0_F2.html|journal=[[Nature (journal)|Nature]]|volume=393|pages=440&ndash;442|month=June|doi=10.1038/30918|pmid=9623998|issue=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>
 
Quest'ultima definizione è equivalente alla prima se si utilizza la [[media ponderata]], pesando ogni <math>C_v</math> con il numero di triple in cui il nodo è centrale:
:<math>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}</math>.
Dove:
*<math>n_\Delta(G)</math> è il numero di triangoli del grafo;
*<math>n_\land(G)</math> è il numero complessivo di triple del grafo;
*<math>w_i</math> è il peso del vertice i-esimo (numero di triple in cui il nodo è centrale);
Notare che <math>\sum_{i=1}^{n} w_i \equiv n_\land(G)</math>.
 
=== Esempio ===
[[File:6n-graf-clique.svg|thumb|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:
{| class="wikitable" style="text-align:center"
! Vertice !! Collegamenti<br />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,5⟩, ⟨5,4,6⟩
|-
| 5 || 1/3 || 3 || ⟨1,5,2⟩, ⟨1,5,4⟩, ⟨2,5,4⟩
|-
| 6 || 0 || 0 || —
|}
:<math>\frac{3\cdot n_\Delta(G)}{n_\land(G)} = \frac{3}{11};</math>
:<math>\frac{\sum_{i=1}^{n} (C_i \cdot w_i)}{\sum_{i=1}^{n} w_i} = \frac{1\cdot1+\frac{1}{3}\cdot3+\frac{1}{3}\cdot3}{1\cdot2+3\cdot3} = \frac{3}{11};</math>
:<math>\Rightarrow C = \frac{3}{11}.</math>
 
== Note ==