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é.