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 Grands graphes de terrain

La recherche sur les graphes est un domaine transversal. En effet, les graphes peuvent être constitués de noeuds représentant toutes sortes d'objets en relation. Cependant, il apparaît que la plupart des grands graphes de terrain partagent des caractéristiques communes.

1.4.1 Définition

Par définition, ces graphes venus du monde réel ne sont donc pas issus d'une formule mathématique. Ils existent sur le « terrain » et les noeuds se doivent d'avoir une existence physique.

Matthieu Latapy [Latapy-2007] considère la phrase de Watts et Strogatz, en 1998, [Watts&al-1998] « la plupart des graphes de terrain ont des propriétés non-triviales en commun » comme la consécration de leur domaine d'étude.

C'est à partir de ces propriétés communes que l'on définit les grands graphes de

terrain.

Bruno Gaume qui nous apparaît comme l'inventeur de la formule « graphes de terrain » résume ces caractéristiques à quelques points essentiels [Gaume-2004].

Les graphes de terrain :

? Présentent un L faible où L représente la distance moyenne entre deux sommets. Autrement dit, on va généralement trouver un nombre de sommets faible dans le chemin d'un sommet à un autre.

? Présentent un C élevé où C est le coefficient de « clusterisation ». Ce qui signifie que deux sommets connectés à un troisième seront le plus souvent connectés entre eux créant ainsi une triade.

S'il est vrai que l'immense majorité des graphes de terrain répond à ces critères M. Latapy préfère plus prudemment définir ces objets par ce qu'ils ne « doivent pas posséder » [Latapy-2007].

Selon ses travaux, les graphes de terrain ne doivent pas posséder :

? de structure apparente simple (comme des cliques ou des arbres) ;

Chapitre 1. État de l'art, notions, définitions et vocabulaire sur les graphes

? de structure comparable à des graphes aléatoires.

1.4.2 Caractéristiques

Certaines caractéristiques données dans la définition des « Grands Graphe de Terrain » ne sont précisées que par un ordre de grandeur ou une tendance. Il existe cependant un consensus autour de certaines de ces tendances. D'autres mériteraient d'être mieux précisées. Les exemples sont pris dans le domaine des réseaux sociaux dans le but de permettre au lecteur non spécialiste de mieux les visualiser.

Grands graphes

Les graphes de terrain que nous considérons ici sont dits « grands », notion toute relative. Historiquement la plupart des « grands graphes de terrain » étudiés sont constitués de quelques centaines à quelques centaines de milliers de sommets. L'étude récente de grands graphes de terrain, constitués de millions d'objets ou plus, pose de nouvelles difficultés. Ces difficultés se retrouvent dans la manipulation, l'étude et la visualisation de ces objets. C'est pourquoi, afin de marquer cette nouvelle étape, nous proposons de nommer les graphes constitués d'un à plusieurs millions de sommets « Méga-graphes de Terrain ». On pourra alors aller jusqu'à parler de « Giga-graphes » pour des objets d'études comme Internet [Barabas&ali-2000] vu comme un graphe de 109 sommets.

Une faible densité

Une faible densité correspond à une probabilité très faible que deux noeuds choisis aléatoirement soient directement connectés. Les valeurs rencontrées dans les graphes de cette étude (inférieur à .001) sont effectivement assez faibles. Il n'y a pas à notre connaissance d'ordre de grandeur fixé pour définir cette caractéristique comme « faible ».

Une composante connexe majoritaire

Cette composante est un ensemble de noeuds connectés présentant plus de 90% du nombre des sommets. De plus, cette composante connexe devra présenter un diamètre faible et donc fournir au graphe un diamètre effectif faible.

Une distance moyenne, un diamètre faible et un diamètre effectif faible

Il n'y a pas, à notre connaissance, d'ordre de grandeur fixé ni de seuil pour définir ces caractéristiques comme « faibles ». Cependant, d'une manière générale leurs évaluations relatives ne posent pas de problème. Par exemple, les diamètres effectifs et diamètres de Méga-graphes de terrain mesurés ici sont tous inférieurs à 15. Cette valeur comparée à un maximum théorique pouvant approcher le nombre de noeuds du graphe (supérieur à 106) est sans aucun doute faible.

1.4. Grands graphes de terrain 40

Une distribution de degrés très hétérogène.

1.4. Grands graphes de terrain 41

Chapitre 1. État de l'art, notions, définitions et vocabulaire sur les graphes

Cette caractéristique possède le plus souvent un écart type très important. Cependant, la nature des liaisons fournit parfois ses limites naturelles propres. Par exemple, dans un réseau social où la relation serait « est l'enfant de... », on comprend aisément que chaque noeud ne possédera que deux liens entrants et que le nombre de liens sortants « est le parent de ... » ne peut pas atteindre de valeur très importante.

M. Latapy donne cependant comme système d'approximation de cette valeur une loi de puissance, telle que :

Pk = fraction des noeuds de degré k ;

k = degré, A est l'exposant de la loi : Pk~K-A où il estime A étant généralement entre 2

et 3.

La fraction de noeuds de degré k est proportionnelle (quand k varie) à une puissance négative de k. Le fait de suivre une telle loi (loi de puissance) est une marque de l'hétérogénéité. La constante A donne une indication de la force de cette hétérogénéité [Latapy-2007].

Un coefficient de clustering élevé

Cette caractéristique n'est pas citée par tous les auteurs comme déterminante des grands graphes de terrain. Elle est liée à la nature du graphe. Dans les réseaux sociaux, par exemple, il semble naturel que mes amis soit davantage amis entre eux que deux personnes choisies aléatoirement.

précédent sommaire suivant







Rassembler les contraires c est creer l harmonie