L comme lien
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.
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.
Billets liés : C comme centralité(s), S comme (graphe) simple, S comme sommet
OpenEdition vous propose de citer ce billet de la manière suivante :
Laurent Beauguitte (6 mars 2013). L comme lien. groupe fmr (flux, matrices, réseaux). Consulté le 20 mars 2025 à l’adresse https://doi.org/10.58079/p81p
3 réponses
[…] liés : L comme lien, C comme centralité(s), D comme […]
[…] liés : F comme flux, L comme lien, S comme […]
[…] Billets liés : C comme (réseau) complexe, L comme lien […]