S comme (graphe) simple

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

Un graphe est dit simple (simple graph) quand il remplit deux conditions :

  • il n’existe pas de boucle, c’est-à-dire de lien d’un sommet vers lui-même ;
  • il n’existe pas de liens multiples, c’est-à-dire de liens de natures différentes entre les sommets.

Le graphe simple peut être orienté ou non.

Lorsque le graphe étudié comprend des liens multiples (multiple edges), on parle alors de multigraphe (multigraph). Il n’existe par contre pas de terme spécifique pour désigner les graphes comprenant des boucles.

Dernier point de cette courte définition, un graphe non-simple (multigraphe ou avec boucle) n’est pas un graphe complexe (complex network). Cette dernière catégorie désigne dans la littérature soit de grands graphes (plusieurs milliers voire centaines de milliers de sommets et de liens), soit des graphes dont on observe la croissance (développement des liens entre sites web par exemple). Mais, et cela fait partie des nombreux petits soucis terminologiques en analyse de réseau, les graphes complexes sont pour la plupart des graphes simples…

Billets liés : C comme (réseau) complexe, L comme lien

Retour au glossaire


Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *