WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

Agrégats de mots sémantiquement cohérents issus d'un grand graphe de terrain


par Christian Belbèze
Université Toulouse 1 Capitole - Doctorat en informatique 2012
  

précédent sommaire suivant

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

précédent sommaire suivant







Rassembler les contraires c est creer l harmonie