G comme graphe
Ces billets visent à définir le plus clairement et le plus précisément possible des termes clés en analyse de réseau. Ils s’adressent à un public débutant et évitent autant que possible toute formalisation mathématique (pour cette dernière, voir les synthèses fmr sur Hal-Shs).
Au sens étymologique, le terme “graphe” fait référence à la graphie et désigne un mode d’écriture dit graphique, sur un support (papier, écran) dont on dirait aujourd’hui qu’il est plutôt vectoriel. Il s’agit d’une manière de communiquer une information, à l’aide de signes et de caractères conventionnels, le point et la ligne, là où les lettres correspondent à l’orthographe, les pas de danse à la chorégraphie.
Ce terme “graphe” , aujourd’hui si populaire, est pourtant un terme ambigu. Il désigne, en effet, à la fois 1) la structure particulière des données relationnelles archivées dans une matrice d’adjacence (voir M comme matrice) 2) un mode de représentation des structures matricielles et 3) une fonction mathématique. Dans le premier cas, le graphe correspond à un réseau de relations sociales, spatiales, etc.. Dans le second, le graphe fait référence au diagramme Lien-Noeud auquel il s’est progressivement substitué dans le langage courant. Il caractérise alors un mode de représentation des matrices, parmi d’autres (le tableau croisé, la liste de sommets, le diagramme circulaire, etc.). Si l’acceptation commune du terme se réfère à la Théorie des graphes, le graphe désigne également une fonction mathématique. Dans la Théorie des ensembles, on parle de graphe ensembliste pour désigner une structure formée de deux ensembles : celui des sommets et celui des liens, qu’ils soient munis – ou pas – d’attributs particuliers. Ce graphe ensembliste désigne donc l’ensemble des couples d’entités qui vérifient une relation donnée, ainsi que la représentation de cette relation sous la forme d’un schéma, le graphe.
On l’a tous compris, la particularité du graphe est d’être formée d’un ensemble nécessairement fini de sommets (ou noeuds) mis en relation par des liens (ou arcs ou arêtes). Il est défini par un ordre de rang k qui correspond au nombre de ses sommets. Ses liens traduisent l’existence d’une relation – ils sont binaires -, mais pas forcément (voir L comme liens) ; ils peuvent aussi être orientés ou encore valués (voir F comme flux) comme les graphes de flux et décrire un graphe simple, un graphe complexe (voir C comme (réseau) complexe) ou un graphe multiple (voir infra). De la même façon, les sommets peuvent correspondre à une catégories d’entités (des acteurs, par exemple) ou à plusieurs entités (des chercheurs et des revues), comme dans le cas des graphes bipartites composés de deux groupes d’acteurs distincts (voir B comme biparti).
Le graphe est, en réalité, une projection dans un plan – qui n’est pas nécessairement assorti d’une métrique – de tout (voir C comme (graphe) complet) ou partie de la structure archivée dans une matrice. C’est la raison pour laquelle on parle également de sous-graphe pour en désigner une partie ou, plus généralement et pour généraliser, d’hypergraphe (et donc d’hypergraphe partiel, dual, etc.).
Le graphe renseigne sur l’existence d’au moins une relation entre deux entités (voir S comme graphe simple), ce qui suggère l’existence potentielle de plusieurs relations. Dans ce cas, on parle de multigraphe (ou de graphe multiple) lorsque plusieurs arêtes qui correspondent à des liens de différentes natures relient deux sommets. Ces arêtes sont aussi qualifiées d’arêtes multiples ou d’arêtes parallèles ; à noter que certains auteurs utilisent le terme de pseudo-graphe pour qualifier le multigraphe.
L’intérêt du graphe réside dans les différents problèmes opérationnels qu’il permet de résoudre, les plus communs étant liés à : la recherche du plus court – ou du plus long – chemin, très connu sous l’expression de “Problème du Voyageur de Commerce” (PVC) ; la coloration du graphe et le nombre chromatique ; la connexité ; la vulnérabilité ; l’extraction de communautés (ou modélisation par blocs) ; la recherche d’un arbre de recouvrement minimal, pondéré ou pas, etc.
Pour aller plus loin :
Représentation graphique des matrices : graphe et/ou carte de flux ; La visualisation des réseaux : principes, enjeux et perspectives ; Multigraphes, multiplexes et réseaux couplés, disponibles sur hal-shs.
Billets liés : B comme (graphe) biparti, C comme (graphe) complet, C comme (réseau) complexe, F comme flux , M comme matrice, S comme (graphe) simple.
OpenEdition vous propose de citer ce billet de la manière suivante :
Françoise Bahoken (17 septembre 2013). G comme graphe. groupe fmr (flux, matrices, réseaux). Consulté le 19 janvier 2025 à l’adresse https://doi.org/10.58079/p835
2 réponses
[…] G comme Graphe et R comme Réseaux, billets de Françoise Bahoken et Laurent Beauguitte […]
[…] L’expression représentation graphique (de données statistiques) provient du latin : repraesentare (rendre présent) et du grec : graphein, qui signifie la graphie, l’écriture. Il s’agit donc d’une manière de rendre compte visuellement du contenu d’un tableau de données, à l’aide de symboles conventionnels propres au type d’écriture employée (des lettres pour un texte, un point et des lignes pour un graphe, … voir G comme graphe). […]