Ora parlermo di un altro
concetto delle reti chiamato clustering.
L'idea del clustering è
di misurare per intero a quale,
se voi foste un nodo,
a quale grado sono i vostri amici
anche amici con un altro.
Allora definiamo il clustering
rispetto al particolare nodo V.
É la frazione della coppia dei vicini
che sono connessi l'uno con l'altro.
Per esempio, guardate a questo nodo qui:
ha 2 vicini, e i suoi vicini
sono connessi tra di loro.
Quindi il clustering è uno; tutti
i vicini sono connessi l'uno con l'altro.
La frazione delle coppie dei vicini
che sono connessi l'uno con l'altro è 1.
Mentre per questo nodo, ha 3 vicini,
ma nessuno dei suoi vicini è connesso l'uno con l'altro.
Queste 2 sono connesse, ma questa non è connesso
all'altro vicino. Matematicamente, sappiamo che
un nodo V ha K_v vicini, ci sono
K_v * (K v - 1)/2 coppie di vicini.
Se non siete inclini alle cose matematiche,
non dovete preoccuparvi da dove derivano queste
ma abbiate fede.
In termini di questo,
definiamo C_v come la frazione di tutte
le coppie possibili che sono legate.
Diamogli un'occhiata.
Questo nodo, ha solo 1 vicino.
E così per definizione, se hai solo 1 vicino,
il tuo clustering è 0,
dal momento che non avete particolari coppie di vicini.
Questo nodo ha 3 vicini,
questo,
e questo.
Ok, questo vuol dire che
3*2/2 coppie di vicini,
possibili coppie, uguale a 3, 6/2.
Ma solo una delle coppie dei vicini
è legata. Ovvero, mancano il legami
tra questa coppia di vicini e qusta coppia.
Quindi solo 1 tra 3 possibili coppie
sono legate. Quindi il suo clustering è 1/3.
Come abbiamo detto prima,
il clustering rispetto a questo nodo è 1,
poiché i 2 vicini hanno un legame
tra loro, quindi tutte le possibili
coppie di vicini sono legate a questo nodo.
Per questo, simili a questo,
è 1/3.
Questo 0, ha 2 vicini,
ma non sono legati,
quindi nessuna delle possibili coppie
di vicini sono legate.
E in maniera similare, questa
ha un solo vicino,
quindi non ha nessuna coppia di vicini,
quindi il suo clustering è 0.
E ora noi possiamo definire
il coefficiente di clustering
dell'intera rete,
che è semplicemente la media del clustering
rispetto ad ogni nodo.
Quindi il coefficiente di clustering,
la media C_v su tutti i nodi,
quindi aggiungiamo queste,
e devidiamo per il numero di nodi,
e otteniamo il coefficiente di clustering 0.278.
Ora possiamo contrastare una rete come questa,
con una rete come questa che
è completamente connessa, cioè
ogni nodo è connesso ad ogni nodo.
Quindi gli amici di tutti sono anche amici gli uni degli altri
e con questo il coefficiente di clustering è 1,
o una rete come questa,
nella quale ogni nodo è connesso
ad altri 2 nodi,
ma nessuna delle coppie dei nodi vicini
è connessa.
E questo ha un coefficiente di clustering di 0.
Il coefficiente di clustering può essere indicativo
delle cose come quanto ci mette l'informazione per viaggiare
da una parte della rete ad un'altra,
o anche, quanto male il sistema si disgrega
se un nodo è distrutto.
Fermamioci per un veloce quiz sul clustering.