La théorie des graphes et l'expérience de Milgram

L'expérience de Milgram, en 1967 que l'on appelle « effet du petit monde » pour la distinguer d'une autre expérience du même sociologue Stanley Milgram, est une hypothèse selon laquelle toute personne peut être reliée à n'importe qui d'autre par une courte chaîne de relations sociales.

En 2015, un jeu télévisé suédois a démontré cette hypothèse en donnant pour mission à ses participants de serrer fictivement la main de l'Américain Buzz Aldrin, deuxième homme à avoir marché sur la Lune, en passant au maximum par six relations intermédiaires. Et les participants y sont parvenus !

L'émergence d'Internet et des contenus Web a permis de vérifier cette hypothèse du « petit monde ». En 1998, l'université de Cornell a mené une étude sur 240 millions d'utilisateurs d'une messagerie de Microsoft pour évaluer le degré de séparation moyen entre chacun d'eux. Ils sont arrivés à la conclusion que, sur cette messagerie, le degré de séparation était de 6,6 relations.

C'est avec la démocratisation des réseaux sociaux que ce degré de séparation a pu être fortement réduit. En 2011, Facebook, qui comptait alors 720 millions d'utilisateurs, a publié une étude sur ce sujet et a évalué que le degré de séparation sur son réseau social s'était abaissé à 4,74 relations. Aujourd'hui, avec près de 3 milliards d'utilisateurs à son actif et des algorithmes de recommandation toujours plus perfectionnés, ce degré s'est encore réduit.

Pour représenter simplement les relations entre les utilisateurs des réseaux sociaux, on peut utiliser des graphes. Les graphes n'utilisent que deux éléments différents : les sommets, qui correspondent aux différents utilisateurs, et les arêtes, correspondant à leur mise en relation sur le réseau social.

La distance entre deux sommets correspond au nombre minimal d'arêtes entre eux. Il s'agit, pour faire écho à la notion développée par Milgram, du degré de séparation. Dans l'exemple ci‑contre, Mohamed et Yasmine ont une distance de 2 arêtes entre eux, soit un degré de séparation de 2.

À partir de là, on peut définir les notions d'écartement, de centre, de rayon et de diamètre :

• l'écartement d'un sommet est la distance qui le sépare du sommet le plus éloigné de lui : dans cet exemple, Nathan a un degré de séparation maximal avec Tony et Arnaud correspondant à une distance de 3 arêtes, il s'agit donc de son écartement dans le graphe présenté ;
• le centre d'un graphe désigne un sommet qui possède le plus faible écartement : dans l'exemple présenté, Jean et Lisa sont les seuls à posséder un écartement de 2, ils sont donc les centres du graphe ;
• le rayon d'un graphe désigne l'écartement d'un centre, à savoir 2 dans l'exemple correspondant donc à l'écartement de Jean ou celui de Lisa ;
• le diamètre quant à lui correspond à la distance maximale entre deux sommets du graphe : ici, il pourrait s'agir de la distance entre Yasmine et Tony, soit 3 arêtes.