L'une des plus importantes contributions
de l'article de Watts et Strogatz a été de
présenter un modèle simple pour
la formation des réseaux en petit monde.
C'est-à-dire, comment former un réseau qui
aie une longueur moyenne assez basse,
mais aussi un grand nombre de structures.
Voici comment cela fonctionne:
on commence avec un treillis régulier.
Régulier, c'est-à-dire que chaque nœud
suit le même schéma de connectivité.
Par exemple, ce nœud-ci est connecté
à chacun de ses voisins, de chaque côté.
Et ceux-ci le sont de la même manière.
Il y a donc un total N de nœuds,
m voisins par nœud,
M étant le nombre de liens.
Dans cet exemple,
nous avons 10 nœuds,
chaque nœud à 2 voisins,
et il y a un total de 10 liens.
Ce qui va se passer ici,
c'est que certains de ces liens,
qui sont actuellement entre proches voisins,
vont être reconnectés.
Ils vont être détachés et rattachés
à un autre voisin plus distant,
de manière à représenter une connexion lointaine.
Dans ce modèle, il y a un paramètre
appelé beta, qui correspond à
la probabilité de reconnexion de chaque noeud.
Dans cet exemple, disons que beta = 0.2.
Chaque nœud a donc une probabilité de 0.2
d'être reconnecté.
Maintenant, nous allons choisir au hasard beta * M liens,
ce qui vaut 0.2 * 10, soit 2.
Donc je choisis deux liens.
Vous les voyez en rouge.
Ils ont été choisis au hasard.
Et je vais reconnecter l'une des extrémités
à un autre nœud choisi au hasard.
Je détache l'une des extrémités existantes,
et je la rattache à un autre nœud pris au hasard.
Voici notre nouveau réseau.
La plupart des connexions se font
entre voisins proches, mais
il y a deux exceptions, des connexions de longue distance.
Comme d'habitude, nous allons voir comment
implanter ce modèle dans NetLogo.
Voici à quoi ressemble l'interface.
Nous avons les paramètres:
"node-count" - le nombre total de nœuds;
"neighbor-count" - le nombre de voisin par nœud;
et "beta", la probabilité de reconnexion.
Si je clique sur "setup",
j'ai 10 nœuds,
connectés à leurs plus proches voisins,
donc chaque nœud a deux liens,
et j'ai mis beta à zéro,
donc il n'y a aucune probabilité de reconnexion.
Personne n'est rattaché.
Ici, on peut voir la distribution de degré.
Tous les dix nœuds ont un degré de 2.
On le savait déjà.
On voit aussi la distance moyenne globale,
entre paires de nœuds,
2.5 sauts.
Et le coefficient de clustering:
0, pas de clustering ici.
On peut faire d'autres choses,
par exemple en cliquant sur "show neighborhood",
puis sur un nœud,
on voit alors son voisinage direct.
On peut aussi voir la distance des liens:
en cliquant sur un nœud,
on voit la distance qui le sépare de tous les autres.
C'est donc ce que l'on peut faire.
Je clique à nouveau sur "setup" pour remettre à zéro.
Maintenant, je peux changer la valeur de beta.
Que se passe-t-il si je le mets à 0.1?
C'est-à-dire qu'un des nœuds va être reconnecté.
Je clique de nouveau sur "setup" et
on peut voir que ce lien à été rattaché.
La distance moyenne globale est plus élevée,
parce que nous avons peu de nœuds.
Faisons cela pour un réseau plus réaliste,
mettons 100 nœuds.
Beta de nouveau à zéro,
setup.
Vous voyez le même schéma régulier de liens,
avec cent nœuds.
La distance moyenne globale est de 25 sauts.
Changeons beta à 0.5, 5%,
et remontons le réseau.
Rappelez-vous que beta correspond à la probabilité
qu'un nœud soit redirigé.
Chaque nœud a 5% de chances d'être reconnecté.
Beaucoup d'entre eux ont été rattachés.
Et la distance moyenne globale a fort baissé,
de 25 à 9,24.
Un nombre relativement petit de reconnexions
a permis à la distance de diminuer drastiquement.
Cela a aussi changé la distribution de degré.
Essayons de reconnecter 10% des liens.
La distance a augmenté,
mais si on recommence,
elle baisse, car c'est aléatoire.
Il y a toujours peu de clustering.
Les structures apparaissent quand
il y a plus de voisins.
Mettons le nombre de voisins à 4,
et beta à zéro.
Chaque nœud est connecté à 2 voisins de chaque côté,
la distance est de 12,75.
Mettons beta à 5%.
Ici, la distance moyenne globale a fortement baissé,
et le clustering a augmenté.
Vous pourrez jouer avec ce petit modèle de petit monde,
dans votre exercice individuel.
Terminons cette sous-unité
avec un résumé sur les réseaux en petit monde.
Nous avons vu qu'il y a une progression de réseaux,
de plus régulier au plus aléatoire.
Les réseaux réguliers ont une haute distance moyenne
entre les nœuds, et un haut clustering.
Celui-ci apparaît quand on a plus de deux voisins,
ici, il y en a 4 par nœud.
Les réseaux aléatoires ont une petite distance moyenne,
mais un faible clustering.
Par contre, les réseaux en petit monde sont,
d'une certaine façon, plus réalistes.
Ils ont une petite distance moyenne et
un fort taux de clustering.
Comme les réseaux du monde réel
que Watts et Strogatz ont étudiés.