1.4.4 Des petits mondes ou la légende des six
poignées de mains
En 1969, Travers Jeffrey et Stanley Milgram effectuent une
expérience qui donnera à penser que « notre monde est tout
petit ». L'expérience a donné naissance au lieu commun
« nous sommes tous à une distance de six poignées de main de
quiconque sur la planète ». Il convient de rappeler les faits :
Millgram donne un paquet à 296 personnes avec la consigne de de
l'envoyer à une personne qu'elles « connaissent », la
définition de cette connaissance étant « vous l'appelez par
son prénom » ; chaque destinataire devant à son tour envoyer
le paquet à un destinataire « connu » d'eux et ainsi de suite
jusqu'à ce que le paquet parvienne au destinataire final commun, un
agent de change, vivant à une adresse fournie, dans la ville de Sharon
dans le Massachusetts. Les personnes qui « connaissaient » le
destinataire final
1.5. Les communautés 43
Chapitre 1. État de l'art, notions, définitions et
vocabulaire sur les graphes
pouvaient le lui envoyer directement. Sur 296 paquets, 64 sont
arrivés à destination. Pour ces 64 paquets, la moyenne du nombre
de personnes ayant porté le paquet jusqu'à destination
était alors de 5.5. La conclusion aurait pu être : dans la
même composante connexe, la distance moyenne entre deux individus semble
être de 5.5 sauts.
Depuis cette expérience [Millgram&al-1969],
les grands graphes de terrain présentant un diamètre
faible sont nommés « Small Word » ou petit monde
[Watts-1999]. Le concept de petit monde est donc
lié à la notion de diamètre faible en regard du nombre de
noeuds. Cette caractéristique est accompagnée d'une faible
distance entre deux sommets quelconques et une forte connectivité
locale. Elle provient initialement de la célèbre
expérience de Stanley Millgram. La notion de petit monde est
peut-être réelle, mais construite en partie sur ce qu'il est
convenu d'appeler une « légende urbaine ».
Toutefois, le coût en temps CPU d'un calcul exact du
diamètre est prohibitif lorsqu'on utilise les algorithmes classiques sur
des réseaux de plusieurs millions de noeuds. Nous pouvons citer ici la
méthode proposée par C. Magnien [Magnien-2009]
qui effectue une estimation du diamètre par un encadrement
entre deux valeurs : une valeur haute obtenue par une simplification
préalable du graphe en arbre et une valeur basse correspondant à
la distance maximale parcourable depuis des noeuds sélectionnés
aléatoirement. Nous avons aussi proposé une autre piste
d'estimation basée sur la mesure de la distance maximale mesurable en
prenant comme noeuds de départ des noeuds
prédéterminés ayant une forte potentialité à
être une des extrémités du diamètre du graphe
[Belbeze&al-2012].
| 
