L comme lien

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 composé de sommets symbolisant des acteurs et de liens (edges, ties) symbolisant une relation entre ces acteurs. Lorsque la relation a une direction, et qu’une relation de a vers b n’implique pas nécessairement une relation de b vers a, on parle d’arc et on a affaire à un graphe orienté (directed graph ou digraph). Lorsque la relation est symétrique (si a est lié à b alors b est nécessairement lié à a), on parle d’arête et le graphe est non orienté.

Un lien d’un sommet vers lui-même est appelé une boucle (loop ou self-tie). Lorsque plusieurs liens de nature différente lient les sommets (relation amicale, familiale et professionnelle par exemple), on parle de multigraphe. Dans ces deux cas, le graphe cesse d’être simple – mais ne devient pas pour autant complexe ! Un graphe dit simple suppose en effet l’absence de boucles et de liens multiples.

Tout comme les sommets, les liens peuvent porter des attributs. Lorsque le lien symbolise une intensité plus ou moins forte (flux commerciaux ou financiers par exemple), le graphe est dit valué (valued ou weighted graph). Quand le lien symbolise l’attraction ou le rejet, on parle alors de graphe signé (signed graph, + pour l’attraction et – pour la répulsion).

Dans la figure ci-dessous – où la couleur des sommets a un objectif exclusivement décoratif – on  trouve de haut en bas et de gauche à droite une boucle, un lien non orienté, un lien orienté non réciproque, un lien orienté réciproque (on parle également de lien symétrique ou mutuel), des liens valués, des liens signés et enfin des multi-liens. Les analyses possibles seront en partie fonction du type de liens présents dans un graphe.

Types de liens

La distance entre deux  sommets se mesure généralement en nombre de liens nécessaires pour les joindre.

Si de nombreuses mesures s’appliquent aux sommets, celles relatives aux liens sont beaucoup moins nombreuses. Ces dernières années, la mesure de l’intermédiarité des liens a été de plus en plus fréquemment employée pour partitionner les graphes (c’est à dire repérer dans un graphe les ensemble de sommets fortement connectés les uns aux autres). Cette mesure permet de savoir si un lien est un passage obligé pour joindre plusieurs paires de sommets.

Enfin, tout comme il existe des points d’articulation dont la suppression augmente le nombre de composantes connexes, il existe des liens nommés ponts ou isthmes qui jouent le même rôle (les termes anglais sont bridge, cut-edge et, plus rarement utilisé, isthmus). Dans le graphe ci-dessous, supprimer les liens oranges augmente en effet le nombre de composantes connexes.

Exemple de pont

 

Billets liés : C comme centralité(s), S comme (graphe) simple, S comme sommet

Retour au glossaire


Laisser un commentaire

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