Maintenant, nous allons parler d'un autre
concept des réseaux qui se nomme "clustering".
L'idée du clustering est
de mesurer dans quel mesure,
si vous étiez un noeud,
dans quel mesure vos amis sont-ils
aussi des amis mutuels.
Alors, définissons clustering selon
un noeud 'V' particulier.
Il s'agit de la fraction de paires de voisins
qui sont connectés l'un à l'autre.
Par exemple, regardez ce noeud ci;
il a deux voisins, et ses voisins
sont mutuellement connectés.
Donc son clustering est de 1; tous ses
voisins sont connectés l'un à l'autre.
Donc la fraction de paires de voisins
qui sont mutuellement connectés est de 1.
Alors que pour ce noeud, il a 3 voisins,
mais pas tous ses voisins sont mutuellement connectés.
Ces deux-ci sont connectés, mais celui-ci n'est pas connecté
avec ses autres voisins. Mathématiquement, nous savons que si
un noeud V possède K_v voisins, il y a
K_v * (K v - 1)/2 paires de voisins.
Si vous n'est pas adepte des mathématiques,
vous n'avez pas a vous souciez de comment ceci est dérivé,
croyez le seulement.
En terme de ceci,
nous définitions C_v comme la fraction de toutes
les paires possibles qui sont liées.
Alors regardons ceci;
Ce noeud, il n'a qu'un seul voisin,
donc par définition, si vous avez seulement un voisin,
votre clustering est de 0,
car vous n'avez pas de paire de voisins.
Ce noeud a 3 voisins,
Celui-ci,
celui-ci
et celui-ci.
Ok, donc cela signifie qu'il possède
3*2/2 paires de voisins,
paires possibles; ce qui égal 3, ou 6/2.
Mais seulement l'une de ses paires de voisins
est lié. Donc, il manque des liens entre
cette paire de voisins et cette paire de voisins.
Donc seulement 1 paire possible sur 3
est liée. Donc son clustering est de 1/3.
Comme dit précédemment,
le clustering selon ce noeud est de 1,
car ses 2 voisins ont un lien
entre eux, donc toutes les paires
possibles sont liées à ce noeud.
Celui-ci, similaire à celui-ci,
possède un tier.
Celui ci, 0; il a 2 voisins,
mais ils ne sont pas liés,
donc aucune paire de voisins
possible n'est liée.
Et similairement, celui-ci
possède seulement un voisin,
donc il n'a pas de paire de voisins,
donc son clustering est de 0.
Et maintenant nous pouvons définir
le coefficient de clustering
du réseau en entier,
qui est simplement la moyenne de clustering
selon chaque noeud.
Donc le coefficient de clustering,
la moyenne C_v de tous les noeuds,
donc nous additionnons ceux-ci,
et divisons par le nombre de noeuds,
et nous obtenons un coefficient de clustering de 0.278.
Maintenant nous pouvons contraster un réseau comme celui-ci,
avec un réseau comme celui-là qui
est complètement connecté, où
chaque noeud est connecté à tous les autres noeuds.
Donc tout le monde est amis avec tout le monde,
et avec ceci vous obtenez un et nous obtenons un coefficient de clustering de 1,
ou un réseau comme celui-ci
où tous les noeuds sont connectés
à deux autres noeuds,
mais aucune des paires de noeuds voisins
sont connectées.
Et celui-ci a un coefficient de clustering de 0.
Le coefficient de clustering peut être indicatif
de chose comme; combien de temps ça prend pour voyager
d'une partie du réseau à une autre partie,
ou encore, à quel point le système s'écroulera
si l'un des noeuds est éliminé.
Arrêtons ici pour un court quiz sur le clustering.