9.3 - Réseaux small-world
Nous avons tous déjà entendu quelque chose similaire à cette phrase;
"le monde est petit!"
Souvent vous avez des connections
inattendus avec quelqu'un que vous venez de rencontrer,
ou vous avez des amis en commun,
ou des proches.
Ça semble être une incroyable coïncidence!
La notion des réseaux "small world" (petit monde)
essais de quantifier ce phénomène;
à quel point sommes nous réellement connectés.
Pour illustrer ceci, nous pouvons jouer à un petit jeu
que vous pouvez jouer vous-même.
L'idée est
de vous prendre -
Ici c'est moi en Oregon a Portland -
et de vous demander; comment puis-je atteindre
une personne, disons, très très bien connue.
Je vais prendre notre président, Barack Obama.
Via un réseau d'amis et de famille
ou de personnes que vous connaissez bien.
Alos, la question est:
Puis-je trouver un chemin dans mon réseau social,
jusqu'à Barack Obama,
et combien long le chemin doit-il être.
La question est de comment commencer,
quelle est la première personne à aborder.
J'ai choisit ma mère, qui vit à Los Angeles,
car, premièrement,
elle est avocate,
et Barack Obama est un avocat,
donc il y a une connexion.
Aussi, ma mère est quelqu'un
de très sociable;
elle connait beaucoup de personnes,
ce qui aide aussi.
Donc l'idée est de choisir
quelqu'un qui est connecté
à votre personne cible
et qui possède peut-être aussi un large cercle d'amis.
J'ai donc demandé à ma mère;
"Qui connais-tu qui pourrait connaitre Barack Obama,
ou qui pourrait connaitre quelqu'un qui connait Barack Obama?"
Et elle y pensa pour un moment
et elle dit
"Oh, peut-être que mon amie Nancy Bekavas,
qui était présidente du Scripps College,
à Claremont en Californie,
pourrait avoir une connexion".
Et il s'avéra qu'elle a étudié en loi,
avec Hilary Clinton,
qui, évidement, connait Barack Obama.
Donc, incroyablement, ma connexion avec Barack Obama
prend seulement
un,
deux,
trois,
quatre hops!
Je ne pense pas qu'il y ait quelque chose de spécial à propos de moi.
Je pense que n'importe qui d'entre vous peut prendre une personne connue
dans votre propre pays
et trouvé un court chemin
pour atteindre cette personne.
Plus tard, après y avoir réfléchit plus,
j'ai réalisé que j'avais peut-être un chemin encore plus court.
J'ai pensé à mon cousin,
Matt Dunne, qui est un politicien
au Vermont.
Il était un membre
du conseil législatif de l'état du Vermont
et il s'avère qu'il connait
le sénateur Patrick Leahy,
qui connait Barack Obama.
Donc nous voici avec,
1,2,3 hops!
Et j'étais émerveillée.
Vous pouvez l'essayer vous même,
c'est un jeu amusant,
et vous pouvez réaliser qu'il s'agit
d'un chemin relativement court,
de vous jusqu'à probablement
plusieurs personnes connues.
Et la raison pourquoi il est court,
est du aux personnes que vous connaissez
qui pourraient être étiquetées comme étant des hubs
dans le réseau social,
comme mon cousin ou ma mère.
Dans les années 1950,
le psychologue sociale Stanley Milgram
d'Harvard essaya une expérience
pour quantifier ce phénomène de small world.
Il réalisa l'expérience suivante;
dans le temps avant les emails,
il cibla une personne,
son courtier financier de Boston.
Donc il était à Boston, à Harvar,
et il connaissait un courtier financier.
Ensuite il recruta un groupe de personne
qu'il pensait être très éloignées,
socialement parlant,
d'un courtier financier de Boston,
c'est à dire, des fermiers du Nebraska.
Il a donc mit une annonce dans les journaux du Nebraska,
essayant de recruter des personnes pour cette expérience.
Leur but serait de transmettre une lettre
au courtier financier de Boston -
ils savaient seulement son nom et qu'il était un courtier financier -
via des personnes qu'ils connaissaient bien,
c'est à dire, des personnes qu'ils connaissaient
par leur prénom.
Et donc on leur donna la lettre
et ils devaient trouvé à qui la donner.
Cette personne devait ensuite la donner
à quelqu'un d'autre, et ainsi de suite,
pour créer une chaîne d'amis
ou de proches par laquelle
ces fermiers du Nebraska peuvent
voir leur lettre atteindre la personne cible,
le courtier financier de Boston,
qu'ils ne connaissent pas.
Et ce que Milgram trouva était que,
en moyenne,
il y avait approximativement
ce qu'il nommait 6 degrés de séparation.
Il s'agit d'une phrase maintenant bien connue,
l'idée selon laquelle nous sommes tous séparés par 6 degrés.
Voici l'idée,
de l'un de ces articles,
il regarda au nombre
de chaines complétées
et au nombre d'intermédiaires
nécessaire pour atteindre la personne cible
et il trouva que cela prenait entre
2 et 10 connaissances intermédiaires.
Et la médian était 5,
et c'est de là que viens la notion
des 6 degrés de séparation,
que ça prenait 6 hops pour se rendre là.
Donc ceci illustre la propriété small world,
l'idée qu'un réseau à relativement peu
de liens à long distance,
mais il y a des chemins courts
entre la plupart des pairs de noeuds,
ce qui créé habituellement des hubs.
Et ce qui était intéressant
c'est que ce n'était pas seulement les réseaux sociaux,
mais plusieurs autres types de réseaux,
en fait la plupart des réseaux complexes présent dans le monde réel
semble possédé cette propriété de small world.
Dans les années 1990,
2 mathématiciens,
Duncan Watts et Steven Strogatz,
ont écrit un article sur ce phénomène
sous une perspective mathématique.
L'article parut dans la revue Nature en 1998;
"Collective dynamics of 'small-world' networks".
Voici Watts et Strogatz.
Et cet article fut peut-être le déclencheur
qui a véritablement débuté l'étude
des réseaux de manière interdisciplinaire.
Voici l'idée;
Watts et Strogatz se penchaient sur
3 types de réseaux du monde réel.
Un réseau d'acteurs de films,
où chaque noeud représente un acteur,
et deux noeuds sont sont liés si
les deux acteurs sont apparus dans un même film.
Ils ont aussi regarder un type de réseau très différent,
le réseau électrique des USA,
où les noeuds étaient des générateurs, transformateurs, sous-stations
et 2 noeuds étaient liés s'il y avait
une ligne de transmission entre eux.
Et finalement le réseau dont nous avons vue une photo précédemment,
le cerveau du ver C. Elegans,
où les noeuds sont des neurones
et 2 noeuds sont liés
s'ils sont connectés par une synapse chimique
ou par une synapse électrique.
Donc, y a-t-il une raison pourquoi ces
3 extrêmement différents types de réseau
devraient avoir quelque chose en commun?
Et bien, ce que Watts et Strogatz trouvèrent
était qu'ils avaient cette structure commune
qu'ils ont nommé la propriété de "small world" (petit monde).
Pour expliquer ceci, regardons une naïve supposition
sur ce que la structure de réseau
des réseaux du monde réel pourrait être.
Une supposition est qu'ils seraient
très réguliers.
Ici vous avez une image abstraite
d'un réseau avec nos noeuds.
Ici les noeuds sont placés en cercle,
et chaque noeud est connecté
à ses 2 voisins les plus près
de chaque coté.
Donc ce noeud, par exemple,
est connecté à ce voisin,
et à ce voisin.
Et ce noeud est connecté, de ce coté
à ce voisin
et à ce voisin.
Et exactement le même type de connections pour chaque noeud.
Donc ceci se nomme un réseau régulier,
et il s'avère que ce réseau,
si vous l’agrandissez proportionnellement à plusieurs noeuds,
a une moyenne de distance entre les noeuds très élevée.
Ça prend un long moment pour se rendre via des hops
d'un noeud à un autre noeud aléatoire
dans le réseau,
mais à une moyenne de clustering élevé,
ce qui veut dire,
ce noeud par exemple
ces deux voisins sont connectés l'un à l'autre
et ses voisins dans ces environs
sont connectés aussi.
Donc ceci à un coefficient de clustering élevé.
À l'autre extrême,
vous pourriez considérer un réseau aléatoire,
où chaque noeud à le même nombre de connexions,
mais ils sont connectés aléatoirement au lieu d'être connectés avec leurs voisins.
Et ce genre de réseau à une moyenne de distance
entre noeuds faible, ce qui veut dire
que ça ne prend pas longtemps pour se rendre, via des hops,
d'un noeud à l'autre,
mais possède un coefficient de clustering faible.
Et donc, ce que Watts et Strogatz ont trouvé
pour les 3 réseaux du monde réel qu'ils ont étudié,
était qu'aucun de ces modèles naïfs étaient correct.
Voici quelques résultats rapportés dans l'article de Watts et Strogatz;
Ils rapportèrent que pour chacun des 3 réseaux qu'ils ont observé
la distance moyenne entre les pairs de noeuds dans le réseau donné.
Donc voici ce qu'ils ont trouvé pour la distance moyenne
dans ces réseaux,
et ils comparèrent ceci
avec un réseau connecté aléatoirement,
qui possède le même nombre de noeuds et de liens.
Et vous pouvez voir que
la moyenne de longueur de chemin pour le réseau aléatoire,
la longueur du plus court chemin,
est un peu plus bas,
mais pas beaucoup plus bas.
Donc chacun de ceux-ci à relativement
une longueur de chemin aléatoire faible,
pour le nombre de noeuds donné,
ou un énorme nombre de noeuds dans chacun de ceux-ci.
Et ensuite ils regardèrent le coefficient de clustering
de ces réseaux
et le coefficient de clustering
dans les réseaux du monde réel,
étaient beaucoup plus élevés
que le coefficient de clustering dans le réseau aléatoire.
Pour résumé,
si nous comparons les deux extrêmes,
le réseau régulier et le réseau aléatoire,
nous pouvons voir que ces soit-disant réseaux small world,
comme définis par Watts et Strogatz,
ont une moyenne de distance de chemin faible,
et un clustering élevé,
comparé à chaque des extrêmes.
Et il semble que ce juste milieu
est où se situe la plupart des réseaux du monde réel.
Ce qui veut dire que les réseaux small world peuvent être définis
comme ayant une moyenne faible de distance entre les noeuds,
mais un coefficient de clustering élevé.