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

La représentation mentale d'un graphe est généralement aisée et la notion de noeud et liaison est le plus souvent comprise de manière intuitive. Cependant, l'utilisation d'une terminologie précise se révèle nécessaire dès qu'il s'agit d'approfondir l'étude de ces ensembles.

Voici listées les notions utilisées dans notre contexte de travail ; à noter que certaines définitions données peuvent tenir compte de notre point de vue. Pour une information plus complète il est possible de consulter plusieurs ouvrages de référence tels que [Berge-1958] [Berge-1970] [Bollobas-1998].

Un arc est le nom donné à une liaison ou à une arête dans un graphe dirigé.

Élément reliant deux points d'un graphe. Généralement représenté par un segment de droite. Dans la matrice d'adjacence du graphe la présence de l'arête est représentée par un 1 et son absence par un 0.

Une arête orientée est une arête présentant un sens. Un des pairs est un émetteur l'autre un récepteur. On parle aussi d'arc. Les arêtes orientées sont des éléments des graphes orientés.

Une arête pondérée est une arête présentant un poids. Ce poids est une valeur numérique permettant de comparer la validité des arêtes. Les arêtes pondérées sont des éléments des graphes pondérés.

La centralité d'une arête e, notée cB(e), est définie comme le nombre de plus court(s) chemin(s) entre toutes paires de noeuds contenant e : ainsi, si la centralité d'une arête est grande, on peut s'attendre à ce qu'elle se trouve à l'interface entre deux communautés du graphe considéré. Cette notion peut facilement être étendue aux noeuds en considérant le nombre de plus court(s) chemin(s) passant par un noeud donné. Une arête à forte centralité est considérée comme un séparateur possible de communautés.

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

Liste des plus courts chemins passant par l'arête [C-X/X-C] en considérant le graphe comme dirigé

A-W	A-X	A-Y	A-Z	W-A	X-A	Y-A	Z-A
B-W	B-X	B-Y	B-Z	W-B	X-B	Y-B	Z-B
C-W	C-X	C-Y	C-Z	W-C	W-C	Y-C	Z-C
D-W	D-X	D-Y	D-Z	W-D	W-D	Y-D	Z-D

Figure 1.3 : Exemple d'arête ayant une centralité élevée et étant susceptible de séparer deux communautés.

Un chemin d'un noeud A à un noeud Z est une suite de noeuds reliés par des arêtes tel qu'il est possible de se déplacer du noeud A au noeud Z en parcourant les noeuds du chemin.

Une clique peut être définie comme une figure connectée de trois noeuds minimum d'un graphe non dirigé dans laquelle on ne peut rajouter ni lien ni noeud. En effet, chacun des noeuds doit être connecté à tous les autres noeuds et il ne doit pas exister de noeud connecté à tous ces noeuds qui ne seraient pris en compte. La clique est aussi définie comme un sous-graphe complet.

Figure 1.4 : Exemple de clique de 5 sommets. Figure 1.5 : En noir, un exemple de clique formée par

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

Une composante connexe est une partie du graphe où il existe au moins un chemin pour rejoindre tous les noeuds de la composante connexe. Si un graphe est seulement et totalement composante connexe, on utilise le terme de graphe connexe.

Dans un graphe dans lequel un noeud ne peut pas recevoir de liaison avec lui-même, le degré d'un noeud est simplement le nombre de noeuds avec lequel il existe une liaison. On parle aussi du nombre de noeuds voisins.

Si le graphe est défini comme acceptant des liaisons autoportées, ses liaisons autoportées ont par convention un poids double.

Degré des noeuds du graphe		Graphe
Noeud	Degré
A	3
B	3

C	4
D	3
E	3

Figure 1.7 : Exemple de valeur de degré pour les noeuds d'un graphe incluant une liaison autoportée.

La densité est le rapport entre le nombre d'arêtes présentes dans le graphe étudié sur le nombre maximal d'arêtes possible sur un graphe contenant le même nombre de noeuds. Dans le cas où le nombre de liaisons par noeud n'est pas limité, ce nombre maximal est, pour un graphe de n éléments, le nombre de paires possibles que l'on peut noter (combinaison de n

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

Le diamètre d'un graphe est la distance la plus élevée entre deux noeuds en utilisant le chemin le plus direct. Une géodésique est l'un des plus courts chemins entre deux sommets donnés. Le diamètre d'un graphe peut être défini comme le plus long chemin géodésique du graphe.

Le diamètre d'un graphe est défini comme une distance maximale et peut donc être une valeur non représentative car trop marginale. Pour éviter cette dérive, plusieurs auteurs proposent de mesurer le diamètre effectif ou petit diamètre [Leskovec&al-2005]. Le diamètre effectif ou petit diamètre est le nombre minimum de sauts ou liaisons dans lequel une fraction (ou quantile q, par exemple q = 90%) de toutes les paires de noeuds connectés sont présentes.

Un graphe est, dans sa représentation dessinée, un ensemble de points dont certaines paires sont reliées par un lien. Le positionnement des points et la longueur des liaisons ne sont pas significatives. Ainsi, le graphe de la figure 1.8 est le même quelles qu'en soient les représentations.

Il est aussi possible de représenter un graphe par une représentation matricielle. Plusieurs types de matrices [matrix] existent. La plus connue et usuelle est la matrice d'adjacence MA. Les noeuds sont présents en abscisses et ordonnées, la jonction de deux noeuds étant alors par convention représentée par un 1 si une liaison existe et un 0 si ce n'est pas le cas.

La matrice des degrés est aussi couramment utilisée. Elle donne, en plus de la matrice des liaisons, des informations sur la valeur des degrés des noeuds. La matrice Laplacienne non normalisée L est la matrice résultante de _MD- MA.

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

On utilise aussi la matrice Laplacienne normalisée. Dans ce cas-là, la fonction de normalisation N(x,y) est égale à 0 si x et y ne partagent pas de liaison, égale à 1 si x= y et

	MA-Matrice d'adjacence	MD-Matrice des degrés du graphe ou matrice diagonale.	ML-Matrice Laplacienne non normalisée		Matrice Laplacienne normalisée

					v	v
	]	[ ]		v			v
[			[ ]	v			v
								]
					v
				[		v

Ensemble d'objets naturels ou existants physiquement dans le monde réel dont les interactions sont exprimables par des arêtes entre paires d'objets. Les graphes de terrains sont ainsi constitués d'éléments aussi divers que des personnes humaines échangeant des mails, des ordinateurs échangeant des trames IP, des mots présents dans la même définition, etc.

Un graphe dirigé est un graphe dont les liaisons appelées arcs ont un sens. Un des noeuds est un émetteur et l'autre un récepteur. Un exemple bien connu de graphe dirigé est l'arbre généalogique inversé. Se lisant du haut vers le bas, le sens de l'arc du haut vers le bas signifie « Parent de ».

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

Un graphe pondéré est un graphe dans lequel les noeuds et les liaisons peuvent recevoir une valeur numérique. Ces valeurs peuvent être soit calculées par des informations sur le graphe lui-même soit être des informations complémentaires. Par exemple dans un réseau social d'échange par Emails, les acteurs peuvent être pondérés par la somme de tous les Emails reçus et chaque liaison par le nombre d'Emails échangés.

Figure 1.10 : Graphe de villes de France. Les villes sont pondérées par le nombre d'habitants et les liaisons par la distance à vol d'oiseau.

Un graphe pondéré et dirigé va cumuler des arcs et des pondérations. Le graphe d'un site web est naturellement un graphe dirigé et pondéré. Les pages du site représentent ici les noeuds et les arcs représentent les liens. La pondération des noeuds peut être donnée par le nombre de liens sortant de chaque page du site, les arêtes seront dirigées comme le sont les liens entre les pages et pondérées par le nombre de liens.

Figure 1.11 : Exemple de graphe dirigé et pondéré d'un site web d'E-commerce.

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

Un graphe est dit bi-connexe s'il existe entre chaque noeud au moins deux chemins complètement distincts. Une autre définition possible est que la suppression de n'importe quel lien permet au graphe de rester une composante connexe.

Une K-clique est une clique de K sommets. Chaque sommet possédant un degré de valeur k-1, le nombre de liaisons est donc de k * (k-1)/2.

Figure 1.13 : Exemple de K-clique avec K= 9. Le graphe est constitué de 9 noeuds et 36 liaisons.

Afin d'indiquer rapidement un ordre de grandeur du nombre de noeuds inclus dans un (grand) graphe, on peut parler de Méga-graphe pour les graphes contenant plus d'un million d'objets.

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

La notion de modularité a été développée par Newman [Newman-2004-2]. Son but est de comparer la proportion relative de liaisons d'un sous-graphe avec le nombre de liens d'un sous-graphe de même taille construit aléatoirement en respectant la valeur statistique de présence de liaisons de l'ensemble du graphe.

La valeur de modularité d'un sous-graphe est comprise entre [-1,1]. La valeur est supérieure à 0 si le nombre de liens intra sous-groupe est supérieur au nombre de liens du sous-graphe aléatoire créé en respectant la proportionnalité de liaisons présente dans le graphe complet.

Pour un sous-graphe S, le nombre de liens internes à S est noté LS, le nombre de liens dans le graphe est noté LG. La somme des degrés des noeuds présents dans le sous-graphe S est notée DS. La modularité du sous-graphe S sera considérée comme valide si la modularité de S est supérieure à 0 soit : MS = (LS / LG) - (DS / (2LG))² > 0

Dans l'exemple de la figure 1.14, nous sélectionnons arbitrairement 3 sous-graphes. Sachant que LG=26,

Pour S1, _LS1=^6,_DS1 =14 on a donc _MS1= 6/26 - (14/52)² = + 0.158 Pour S2, _LS2=^1, DS2 = 12 on a donc _MS2= 1/26 - (12/52)² = - 0.014 Pour S3, _LS3=^5,_DS3 =12 on a donc _MS3= 5/26 - (12/52)² = + 0.139

Comme on peut le constater, les sous-graphes S1 et S3 sont bien des modules. S2 n'en est pas un, son score de modularité étant négatif. Ce critère de modularité est aujourd'hui très utilisé.

Une partition est un élément constitutif d'un graphe, structuré de telle sorte que chaque partition contient un nombre proche de noeuds et que l'ensemble des partitions contient tous les noeuds.

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

Le taux de clustering ou d'agrégation d'un graphe est la moyenne du rapport pour chaque noeud du nombre réel de liaisons existantes entre ses voisins et le nombre maximum théorique possible de ces liaisons.

Par exemple, pour un noeud X, il existe K noeuds avec lesquels il est connecté. Si le nombre de liaisons n'est pas limité pour chacun des noeuds, le nombre de liaisons maximales entre ces noeuds est K(K-1) /2. Le coefficient de clustering pour le noeud X dans un graphe non pondéré où le nombre de liaisons entre les noeuds voisins de X est égal à LK sera alors de :

Le coefficient de clustering du graphe sera la moyenne de ces valeurs pour l'ensemble des noeuds n du graphe.

Ce coefficient peut être vu comme une mesure statistique de la transitivité. Plus ce coefficient est élevé, plus la probabilité que les noeuds soient liés entre eux est forte. Autrement dit, pour rester dans un exemple des réseaux sociaux plus le taux de clustering est élevé plus il y de chance « que les amis de X soient amis entre eux ».

La triade, est une figure connectée de trois éléments comprenant trois sommets et trois liaisons. Les triades ont une importance particulière dans les réseaux sociaux, notamment car elles sont garantes de phénomènes impossibles aux diades, tels que la médiation et, de plus, sont porteuses de transitivité [Faust-2010].

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

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

1.3 Notions et définitions