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