P comme (graphe) planaire

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 « planaire » est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu’aucune arrête se croise. En revanche, si cette représentation n’existe pas, le graphe est considéré comme « non-planaire ». Attention, s’il existe une représentation non-planaire d’un graphe, cela ne permet pas de conclure que ce graphe est non-planaire, car cette représentation ne présage pas de l’existence d’une représentation planaire. C’est pourquoi il peut sembler plus facile de déterminer qu’un graphe est planaire, puisqu’il « suffit » de trouver une représentation planaire.

planaire1

Analyse visuelle

Pour déterminer si un graphe est non-planaire, il existe parfois des formules mathématiques. Ainsi, pour un graphe simple (voir S comme (graphe) simple) connexe (voir C comme Connexité) de plus de trois nœuds, un graphe planaire doit respecter la majoration suivante : a ≤ 3n – 6 (où a correspond au nombre d’arcs et n correspond au nombre de nœuds). Si le graphe ne respecte pas cette condition, le graphe est non-planaire.

planaire2

Analyse mathématique

Plus généralement, pour déterminer si un graphe est planaire ou non-planaire, il faut avoir recours à des algorithmes qui détectent la présence de certaines structures topologiques que l’on sait non-planaires (caractérisation de Kuratowski). A titre d’exemple, dans la figure ci-dessus, le graphe de droite est précisément une des structures topologiques recherchées. Ce graphe porte le doux nom de K: graphe complet (voir C comme (graphe) complet) à 5 sommets.

planaire3

Analyse algorithmique

Néanmoins, ce n’est pas parce que l’on sait qu’un graphe est planaire qu’il est pour autant facile de trouver une représentation planaire de ce graphe. Ainsi, vous pouvez essayer pour le graphe situé au centre de la figure ci-dessus (une réponse ici). Si vous n’avez pas trouvé, sachez que cette solution est pourtant considérée comme facile.

Pourquoi est-il important de déterminer si un graphe est planaire ou non ? Tout simplement parce que certains indicateurs sont influencés par ce caractère particulier. Par exemple, deux des indicateurs de Kansky, très utilisés en géographie des transports, sont influencés par ce caractère. Ainsi, l’indice γ, qui mesure la densité d’un graphe (voir D comme densité), vaut dans le cas général 2a/(n(n-1)) et pour un graphe planaire a/(3(n-2)). Quoi qu’il en soit, l’intérêt de déterminer si un graphe est planaire n’est pas forcément à chercher dans l’analyse de réseau stricto sensu. Les méthodes associées aux graphes planaires permettent notamment de résoudre des problèmes mathématiques très difficiles comme le théorème des quatre couleurs.

Billets liés : C comme (graphe) complet, C comme connexité, D comme densité, S comme (graphe) simple.

Retour au glossaire

Serge Lhomme

Maitre de conférences à l'université Paris Est Créteil - Docteur en géographie de l'université Paris VII spécialité "dynamique des milieux et risques"

More Posts - Website

M comme multigraphe

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

A l’inverse du graphe simple (simple graph), le multigraphe (multigraph) est un graphe qui autorise des liens multiples –aussi appelés liens parallèles- (multiple edges ou parallel edges). En d’autres termes, dans un multigraphe, deux sommets peuvent être connectés par plus d’un lien.

Le multigraphe est dit orienté (multidigraph) s’il autorise des liens orientés (arcs) parallèles. On appelle pseudographe (pseudograph) un multigraphe qui accepte les boucles.

Un graphe dipôle (dipole graph) est un multigraphe qui est composé uniquement de deux sommets, reliés par un nombre n de liens parallèles.

Multigraphe

Le multigraphe ci-dessus comporte des liens parallèles (en rouge) et des boucles (en bleu)

Les multigraphes peuvent être utilisés pour la modélisation de réseaux de transport multimodaux, pour rendre compte de différents types de relations entre les acteurs du réseau (eg. superposer relations sociales et économiques)…

Pour aller plus loin :  Synthèse FMR « Multigraphes, multiplexes et réseaux couplés »

Billets liés : L comme lien, S comme (graphe) simple

Retour au glossaire

Matthieu Drevelle

Doctorant en Géographie-Aménagement à l'Université Paris 1, UMR Géographie-cités, équipe CRIA - Transamo

More Posts

F comme (lien) faible

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

La Théorie sur les liens faibles a été énoncée au début des années 1970 par le sociologue Mark Granovetter (1973a et 1973b). C’est en articulant les deux niveaux complémentaires auxquels un individu interagit avec d’autres individus, le niveau micro-social et celui des processus macro sociaux, que la notion de lien faible émerge. D’après l’auteur, les liens forts correspondent au niveau micro-social caractérisé par des relations de proximité (au sens large), qui peuvent être interprétées en termes de  fréquence (qui est une contrainte de l’analyse des réseaux), de niveau de connaissance. Il s’agit, par exemple, des relations que l’on entretient avec les membres de sa famille ou de son environnement professionnel immédiat. Ainsi, plus le lien entre deux individus est fort et plus les réseaux formés par les liens qu’ils entretiennent par ailleurs sont superposés et présentent des zones de recouvrement.

Ces liens forts s’opposent aux liens faibles situés au second niveau, ils sont caractérisés par une certaine distance sociale, une fréquence moindre de relations. Ce sont, par exemple, les liens maintenus avec des personnes appartenant à la même association d’anciens élèves et avec lesquels nous n’interagissons que ponctuellement, mais qui peuvent nous apporter beaucoup (nous mettre en relation avec notre futur employeur, par exemple). C’est aussi le cas de ces relations amicales qui sont susceptibles d’apporter de nouvelles informations aux liens forts que nous entretenons avec les membres de notre réseau familial. Ainsi, le passage d’un réseau de relation à un autre (d’une clique à une autre) se ferait plutôt par le biais des liens faibles, les liens forts ne permettant qu’une circulation interne (au sein d’une même clique).

D’après Granovetter, ces liens faibles entretenus avec des individus distants présentent donc la force de permettre d’enrichir son réseau, en jouant le rôle de pont vers les relations des individus avec lesquels on est lié. L’intérêt des liens faibles n’est donc pas immédiat, il est nécessairement inscrit dans la durée. De la même façon que la Théorie des six degrés (6,2) nous met potentiellement en relation avec n’importe lequel des individus connectés … mais de là à ce que l’on soit en relation directe avec le pape (!), il y a tout de même un pas… qui n’est pas infranchissable puisque, de ce point de vue, nous sommes au cœur d’un réseau multi niveaux.

Granovetter a montré l’intérêt de sa théorie, en l’appliquant à différents réseaux de relations pris dans des milieux sociaux, techniques et professionnels variés. En 1985, il met, par exemple, en évidence « l’encastrement » (embededdness) des relations économiques dans des réseaux sociaux, celles des stratégies des firmes face au marché (Granovetter, 1985). Pour finir, on peut considérer que la Théorie sur la force des liens faibles, en introduisant l’encastrement de différents niveaux complémentaires où les relations entre individus sont fondées sur une acceptation de la proximité (sociale, spatiale etc.), constitue donc un cadre d’analyse des réseaux.

Références :

(a) Granovetter M.,  Strength of Weak Ties, American Sociological Review, pp. 1360-1380, May, 1973

(b) Granovetter M.,  The Strength of Weak Ties : A Network Theory Revisited, Sociological Theory, 78 (6), pp. 203-233, Sept. 1973.

Granovetter M.,  Economic Action and Social Structure :  The Problem of Embededdness, American Journal of Sociology, 91 (3), pp. 481-510, 1985.

Billets liés : L comme Lien

Retour au glossaire

Françoise Bahoken

Géographe et cartographe, Chargée de recherches à l'IFSTTAR et membre-associée de l'UMR 8504 Géographie-Cités.

More Posts

R comme réseau

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

Le terme réseau, et cela a été souligné maintes fois, est flou, polysémique et chargé d’idéologie (voir l’excellent ouvrage de Pierre Musso, 2003, Critique des réseaux, PUF). Sans prétendre à l’exhaustivité, on peut distinguer au moins quatre grandes acceptations du terme :

  • le réseau comme installation matérielle et technique (réseau de transport, d’électricité, d’eau etc.) ;
  • le réseau comme symbole de la fluidité et de la circulation (chez certains géographes, la stérile opposition territoire – réseau est une grille de lecture commode) ;
  • le réseau comme métaphore d’un ensemble de relations entre des entités (réseau social, réseau boursier, etc.) ;
  • le réseau comme méthode d’analyse s’appuyant sur la théorie des graphes.

Il est donc tout à fait possible de travailler sur des réseaux sans utiliser des méthodes d’analyse de réseau et, inversement, d’utiliser des méthodes d’analyse de réseau pour étudier des objets non réticulaires stricto sensu (graphes lexicaux par exemple).

La différence entre graphe et réseau est ténue : on peut opposer le graphe au sens mathématique (ensemble fini et non vide de sommets et ensemble fini éventuellement vide de liens) au réseau en soulignant que ce dernier suppose des attributs (nom des sommets, valeur des liens etc.). Néanmoins, en pratique, les termes sont souvent employés l’un pour l’autre.

De multiples phénomènes (sociaux, physiques, biologiques etc.) peuvent être représentés par des points et des lignes : il est donc logique que l’analyse de réseaux soit employée dans de très nombreuses disciplines. Si cette souplesse explique son succès, elle crée aussi des incompréhensions fréquentes entre praticien-ne-s, chacun ayant tendance à développer un vocabulaire, voire des méthodes, autonomes. Ces divergences s’expliquent également par la nature et surtout la taille des réseaux étudiés : des méthodes canoniques de la Social network analysis, adaptées à des réseaux comptant quelques dizaines de sommets, ne peuvent être appliquées à des réseaux de taille plus imposante.

Dernière précision : l’analyse de réseau n’implique pas nécessairement la visualisation du réseau sous forme de graphe. Produire un diagramme lien-nœud n’est ni une condition nécessaire ni une condition suffisante pour analyser un réseau. Il faut noter que lorsque les physiciens ont commencé à étudier des réseaux comprenant plusieurs (dizaines de) milliers de sommets, la visualisation classique n’apportait rien et d’autres moyens de synthétiser l’information ont dû être imaginés (distribution des degrés par exemple).

Billets liés : A comme attributs, G comme graphe, L comme lien, S comme sommet.

Retour au glossaire

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) completC comme (réseau) complexe, F comme flux , M comme matrice, S comme (graphe) simple.

Retour au glossaire

Françoise Bahoken

Géographe et cartographe, Chargée de recherches à l'IFSTTAR et membre-associée de l'UMR 8504 Géographie-Cités.

More Posts

E comme ERGM

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

Les méthodes disponibles en analyse de réseau sont innombrables, qu’il s’agisse d’effectuer des mesures d’ensemble, des mesures sur les sommets et les liens ou de rechercher des sous-graphes fortement connexes. Un point commun existe entre la plupart de ces méthodes : elles sont d’abord et avant tout descriptives. Les modèles ERGM (Exponential Random Graph Model – prononcer  air-guème) visent au contraire à déterminer, dans un graphe donné, quels sont les éléments qui déterminent et expliquent sa structure. Ces modèles sont mathématiquement complexes – ils supposent une bonne connaissance en analyse de réseau,  en régression multiple et en régression logistique -, délicats à paramétrer et la prudence est nécessaire dans l’interprétation : ce billet vise donc seulement à fournir une explication très grossière et nécessairement approximative des principes et de l’intérêt de ces modèles.

En simplifiant à outrance, un modèle ERGM permet de déterminer dans un graphe donné (de préférence one-mode, orienté et non valué – des possibilités existent cependant pour les graphes multiples, bipartis etc.) quelles sont les variables explicatives de sa structure. Ces variables peuvent être relatives aux propriétés du graphe (densité, degré, nombre de liens symétriques etc.) et/ou aux propriétés attributaires des sommets. La recherche de formes spécifiques (triades, sous-graphes étoilés) facilite l’interprétation des résultats car elle suppose des hypothèses fortes relatives à la nature des données collectées.

La démarche suppose plusieurs étapes :

  • sélectionner les paramètres à entrer dans le modèle ;
  • générer x centaines des graphes aléatoires (d’où le R de Random) de taille et de densité comparables au graphe étudié ;
  • comparer statistiquement la distribution des paramètres dans le graphe étudié et dans les graphes aléatoires générés  ;
  • mesurer la qualité globale d’ajustement (goodness of fit) du modèle.

La démarche est le plus souvent itérative, l’objectif étant d’obtenir le modèle le plus performant (qualité globale maximale) et le plus économe (nombre minimal de paramètres inclus dans le modèle). Bien entendu, comme pour toute régression multiple, les interactions entre variables explicatives existent et peuvent compliquer l’interprétation des résultats.

Cette famille de modèles est développée depuis plus de 30 ans et a porté des noms différents au cours du temps et des améliorations successives (modèle p1, p2, p*). Les logiciels sont maintenant au point (voir statnet et la famille de logiciels PNet), la documentation abondante et les études empiriques nombreuses, y compris en français (voir les travaux de Lazega et de ses élèves). Cet outil développé par des mathématiciens et des sociologues a jusqu’ici eu du mal à franchir les barrières disciplinaires, notamment parce qu’il est adapté à des réseaux de taille réduite. Physiciens et informaticiens ont développé ces dernières années des outils d’analyse grosso modo équivalents. Enfin, Tom Snijders a développé une variante adaptée à l’étude longitudinale des réseaux, le modèle SIENA.

Pour aller plus loin : Analyse de graphe et modèles statistiques. Du modèle p1 à l’ERGM sur hal-shs.

Billets liés : M comme modèle, S comme (modèle) SIENA

Retour au glossaire

k comme k-core et k-plex

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

La recherche de sous-graphes de sommets densément connectés, et nommés selon les disciplines cliques, clusters ou communautés, est l’un des objectifs privilégiés de  l’analyse de réseaux. Outre les cliques, abordées dans un billet précédent, de nombreuses méthodes existent et deux sont ici abordées : la recherche des k-cores et celle des k-plexes.

Un k-core est un sous-graphe où chaque sommet est adjacent à au moins k autres sommets de ce sous-graphe. La valeur de k est fixé par le ou la chercheur-e en fonction de la densité du graphe étudié. Cela revient à assouplir la définition de la clique en imposant une contrainte relative au nombre de liens devant être présents. Un k-plex est un sous-graphe maximal (i.e. on ne peut ajouter de sommets sans qu’il ne perde ses propriétés) contenant g sommets dont chaque sommet est adjacent à au moins g – k sommets de ce sous graphe, les valeurs de g et k étant fixées par le ou la chercheur-e. Autrement dit, quand le k-core fixe un nombre minimum de liens devant être présent, le k-plex autorise un certain nombre de liens à être absents. Si la démarche peut sembler proche, les résultats sont différents.

Dans le graphe ci-dessous, si l’on recherche les k-plexes d’au moins quatre sommets (g = 4) où 2 liens peuvent manquer (k = 2), on  trouve le seul quadruplé {abcd} : chacun de ces sommets est relié à au moins 2 autres sommets (4-2) de ce sous-graphe.  Si k est fixé à 1, cela revient à rechercher les cliques présentes dans le graphe. La recherche des k-cores où k = 2 donne les sous-graphes {abcd} et {fgh} : dans les deux cas, chacun des sommets est relié à au moins deux autres sommets de ces ensembles. Toute clique est donc également un k-core, l’inverse n’étant évidemment pas vrai.

Recherche de  k-core et de k-plex

De nombreuses autres adaptations des cliques ont été proposées au fil des décennies (n-clan, n-clique, LS sets, Lambda sets etc.) mais il est rare qu’elles soient implémentées dans les logiciels d’analyse de réseaux. Ucinet est sans doute le logiciel proposant le plus de variantes sur cet aspect.

Pour aller plus loin : Cliques, communautés et dérivées sur hal-shs.

Billets liés : C comme clique/cluster/communauté

Retour au glossaire

G comme glossaire

Lors de la création du groupe fmr, quatre chantiers ont été lancés en plus de la production des synthèses déposées sur hal-shs. L’un d’eux porte sur la mise au point d’un glossaire bilingue, interactif, interdisciplinaire et aussi exhaustif que possible concernant l’analyse de réseau. Plusieurs tentatives ont abouti à la création d’une liste – nécessairement incomplète – de quelques 170 termes.

Les billets de la catégorie Glossaire ont un objectif plus modeste : définir de façon claire et à l’intention d’un public débutant des termes clés en analyse de réseaux. Si nécessaire, une illustration complétera les définitions données. Les antonymes ne bénéficient d’une entrée propre que dans certains cas et, par exemple, disassortatif est défini avec assortatif tandis que réseau complexe a une entrée propre. Enfin, le format billet nécessite de regrouper certains termes et des termes comme isolé, voisin ou adjacent seront définis dans le billet S comme sommet.

La liste ci-dessous donne l’ensemble des termes pour lesquels une entrée est prévue à ce jour (mais cette liste est appelée à grandir). La mise en ligne sera progressive mais, d’ici Noël 2013*, cette première liste devrait être achevée.

Les références bibliographiques indiquées – de manière non systématique – seront toutes en accès libre.

Liste des billets prévus (ceux en bleu sont en ligne).

A comme accessibilité
A comme arbre
A comme (réseau) assortatif
A comme attributs

B comme (graphe) biparti
B comme blockmodel

C comme centralité(s)
C comme chaîne et chemin
C comme clique/cluster/commmunauté
C comme clustering coefficient
C comme (graphe) complet
C comme (réseau) complexe
C comme connectivité/C comme connexité
C comme cycle

D comme degré
D comme densité
D comme distance
D comme (flux) dominant
D comme données
D comme dyade
D comme dynamique

E comme ego
E comme équivalence
E comme ERGM

F comme (lien) faible
F comme flux

G comme graphe

H comme hiérarchique
H comme homophilie

I comme indice(s)

k comme k-core et k-plex

L comme lien
L comme logiciel(s)

M comme (flux) majeur
M comme matrice
M comme modèle
M comme multigraphe
M comme multi-niveau

P comme partition (matrice)
P comme (réseau) petit-monde
P comme (graphe) planaire
P comme position

R comme représentation
R comme réseau
R comme rôle

S comme (réseau) sans échelle
S comme similarité
S comme (graphe) simple
S comme sommet
S comme symétrique

T comme (réseau) technique
T comme topologie
T comme transposée
T comme triade
T comme trou structural

V comme vecteur
V comme visualisation

*Cette prévision était très optimiste… Les termes barrés sont ceux pour lesquels nous n’avons pas encore été capables de (ou suffisamment motivés-e-s pour)  proposer une définition synthétique et trans-disciplinaire.

C comme clique/cluster/commmunauté

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

Pour analyser un réseau, trois grands types de méthodes existent : étudier les caractéristiques des sommets et, plus rarement, des liens (mesures locales) ; étudier les caractéristiques du graphe dans son ensemble (mesures globales) et enfin chercher des partitions pertinentes permettant de regrouper des sommets. La recherche de cliques appartient à cette dernière catégorie.

La définition de la clique est ancienne (années 50) : il s’agit d’un sous-graphe maximal complet d’au moins trois sommets. En clair, il s’agit du plus grand ensemble possible de sommets au sein d’un graphe entre lesquels tous les liens possibles sont présents. Dans la figure ci-dessous, on distingue trois cliques {abc}, {bcd} et {fgh}. Comme on le voit, un sommet peut appartenir à plusieurs cliques.

Cliques

Cette méthode présente au moins deux inconvénients. Tout d’abord, la définition est très restrictive : si un seul lien manque, il n’y a pas de clique. Dans la figure ci-dessus, le sous-graphe {abcd} n’est pas une clique car il manque un lien entre a et d. Différentes méthodes ont donc été proposées pour assouplir cette définition (voir k comme k-plex et k-core). Ensuite, si la méthode est adaptée à des graphes comprenant quelques dizaines de sommets, elle devient inutilisable pour des graphes plus imposants. Les physiciens et les informaticiens travaillant généralement sur des graphes beaucoup plus volumineux ont donc proposé des méthodes alternatives permettant de déceler ces sous-graphes d’acteurs fortement connectés les uns ou autres : utiliser la centralité d’intermédiarité des liens (voir C comme centralité(s)), mobiliser la modularité pour évaluer la qualité d’une partition.

Si les termes différent selon les communautés scientifiques, cliques, clusters et communautés désignent ces sous-graphes fortement connectés. En fonction de la thématique et des données étudiées, ces ensembles peuvent renvoyer à des concepts différents : liens forts et faibles ou structure centre – périphérie notamment.

Pour aller plus loin : Cliques, communautés et dérivées sur hal-shs.

Billets liés : C comme centralité(s), k comme k-core et k-plex.

Retour au glossaire

A comme attributs

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

L’analyse de réseau repose sur une branche des mathématiques appelée théorie des graphes. Ces derniers sont définis comme un ensemble non vide de sommets et un ensemble éventuellement vide de liens entre ces sommets. L’utilisation de la théorie des graphes dans une autre discipline que les mathématiques suppose un troisième ensemble caractérisant les sommets, ou les sommets et les liens : des attributs. Ces attributs varient en fonction du type de graphe étudié et peuvent être qualitatifs (genre et profession d’un individu dans un réseau social), quantitatifs (âge, revenus…) ou ordinal (rang dans une hiérarchie donnée).

Les attributs des liens permettent de différencier différents types de graphes :

  • l’attribut concernant la nature du lien signale un multigraphe (plusieurs types de relations entre les sommets) ;
  • l’attribut concernant l’intensité du lien signale un graphe valué.

Si le graphe est biparti, chacun des deux ensembles de sommets pourra être porteur d’attributs spécifiques. Par exemple, pour un graphe liant des scientifiques à des colloques, il existera un ensemble d’attributs sur les scientifiques (statut, nationalité, discipline, etc.) et l’un sur les colloques (coordonnées géographiques, nombre d’intervenant-e-s, etc.).

La richesse d’une analyse de réseaux dépend souvent de la richesse des données attributaires récoltées sur les sommets. Ainsi, l’une des questions de recherche classiques en analyse de réseaux concerne l’homophilie des liens, c’est-à-dire la propension des sommets à établir des liens avec des sommets partageant une ou plusieurs de leurs caractéristiques. De très nombreuses études en sociologie ont par exemple montré la forte homophilie de genre à l’école primaire ou de statut social pour les choix conjugaux.

Billets liés : H comme homophilie, L comme lien, R comme réseau, S comme sommet.

Retour au glossaire

D comme densité

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

La densité (density) d’un graphe désigne le rapport entre le nombre de liens présents et le nombre de liens possibles : elle varie entre 0 (graphe vide, sans aucun lien) et 1 (graphe complet).  Si la formule change en fonction du type de graphe (orienté ou non,biparti, multigraphe etc.), elle reste aisée à déterminer et à interpréter.

Cette mesure très utile, disponible dans tous les logiciels d’analyse de réseau, présente deux inconvénients majeurs :

  • elle est sensible  au nombre de sommets : dans un graphe issu d’observations empiriques, plus le nombre de sommets augmente et plus la densité tend à baisser ;
  • une même de densité peut qualifier des graphes de structures très différentes. Ainsi, les trois graphes de la figure ci-dessous ont tous une densité de 0.5 (3 liens présents pour 6 possibles) mais le premier est un graphe étoilé, le second une chaîne et le dernier se compose d’une clique et d’un sommet isolé.

D comme densité

Certains géographes étudiant des réseaux planaires utilisent le terme d’indice gamma (gamma index) pour désigner la densité ; ce dernier terme étant alors le rapport entre la longueur des réseaux et la surface du territoire étudié. Mais la définition de l’indice γ est explicite : nombre de liens présents sur nombre de liens possibles…

Billets liés : I comme indice(s)

Retour au glossaire

S comme (réseau) sans échelle

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 réseau est dit sans échelle (scale-free network) lorsque la distribution des degrés suit une loi de puissance : si on représente la fréquence des degrés sur un graphique où les axes sont en logarithmes (degré en abscisse et effectif en ordonnée), on obtient une ligne droite. Mesurer la pente de cette droite permet de savoir si le réseau est scale-free ou non (même si les bornes proposées peuvent être discutées). Ce type de réseaux comprend donc quelques sommets très fortement connectés et un très grand nombre de sommets très faiblement connectés : le web, où quelques sites attirent des millions de liens (google, facebook, youtube notamment), est l’un des exemples caractéristiques de ces réseaux.

Réseaux sans échelle

Extrait de l’article de Barabási et Albert, 1999, Science

Si le terme de scale-free network est récent (1999), le phénomène décrit est beaucoup plus ancien : dès les années 60, une étude de Derek de Solla Price concernant les citations montrait qu’une poignée d’articles scientifiques étaient massivement cités et que la très grande majorité ne l’était jamais ou presque. Le vocabulaire présent dans un corpus présente également ce type de distribution (mots outils très utilisés et nombreux termes employés une seule fois).

Le mécanisme explicatif proposé – qui a été théorisé dans les années 70 sous un nom différent – est nommé l’attachement préférentiel (preferential attachment) : lorsqu’un acteur intègre un réseau, il tend à se connecter aux acteurs les plus connectés. Là encore, le web fournit un exemple très didactique : lorsqu’on crée un site ou un blog, on a tendance à fournir des liens vers les sites de référence du domaine. Inversement, un site qui vient d’être créé n’a pas ou très peu de liens entrants.

Le terme est devenu très populaire et le nombre d’articles traitant des scale-free networks se compte par milliers. Tout comme les réseaux petits-mondes (small-world networks), l’intérêt principal est de proposer une nouvelle famille de graphes aux caractéristiques différentes des réseaux aléatoires (random graphs).

Pour aller plus loin : http://www.barabasilab.com/

Billets liés : C comme (réseau) complexe, D comme degré, P comme (réseau) petit-monde.

Retour au glossaire

B comme blockmodel

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

Le blockmodeling est une méthode de partitionnement de l’ensemble des sommets d’un graphe basée uniquement sur les propriétés relationnelles des différents sommets. L’objectif de cette méthode est de faire ressortir, au sein d’un graphe, des positions (ensemble de sommets impliqués dans le même type de relations, voir P comme position) et des rôles (systèmes de relations entres les sommets ou entre les positions, voir R comme rôle), sans se baser sur des a priori de classe ou de groupe.

Le principe du blockmodeling consiste à intervertir les lignes et les colonnes de la matrice d’adjacence afin de positionner les uns à côté des autres les sommets qui ont le même type de relations avec le même type de sommets. Le regroupement des sommets peut être effectué selon plusieurs logiques d’équivalence, les plus fréquentes étant l’équivalence structurale et l’équivalence régulière (voir E comme équivalence). La matrice alors obtenue est appelée matrice bloquée (blocked matrix). Les blocs sont ensuite agrégés en fonction du fait qu’ils sont composés de liens (on parlera alors de 1-block) ou d’absence de lien (on parlera alors de 0-block) pour former l’image matrix qui correspond au blockmodel du graphe. Il est aussi possible de représenter l’image matrix sous la forme d’un graphe réduit (reduce graph).

blockmodel1

Dans la majorité des graphes, il est peu fréquent de n’obtenir que des 1-block et des 0-block. Il est alors nécessaire de passer par une matrice de densité (density matrix) qui présente la densité de liens dans chaque bloc. Si le graphe ne comporte pas de boucle, les diagonales ne sont pas prises en compte dans le calcul de la densité. Le choix d’un seuil de densité permet alors de passer de la matrice de densité à à l’image matrix.

blockmodel2

Si la matrice de densité est un moyen de passer de la matrice bloquée à l’image matrix. Cette dernière peut aussi être obtenue en cherchant des motifs au sein des blocs (block types). Cette méthode, appelée generalized blockmodeling, permet de rendre compte plus finement des relations entre les blocs. Le tableau ci-dessous présente les différents types de blocs identifiables dans une matrice (d’après les travaux de Batagelj et al.).

B block 1

Pour aller plus loin :

  • Synthèse du groupe FMR “Blockmodeling et équivalences”, disponible sur Halshs.
  • Drevelle, M. (2012). Structure des navettes domicile-travail et polarités secondaires autour de Montpellier, disponible sur M@ppemonde.mgm.fr (utilisation du blockmodeling pour faire émerger des structures territoriales).

Billets liés : E comme équivalence, P comme position, R comme rôle

Retour au glossaire

Matthieu Drevelle

Doctorant en Géographie-Aménagement à l'Université Paris 1, UMR Géographie-cités, équipe CRIA - Transamo

More Posts

E comme équivalence

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

Dans un graphe, deux sommets sont dits équivalents lorsqu’ils possèdent des propriétés relationnelles communes, c’est-à-dire qu’ils émettent et reçoivent des liens vers le même type de sommets. Trois formes d’équivalence sont classiquement distinguées : l’équivalence structurale (structural equivalence), automorphique (automorphic equivalence) et régulière (regular equivalence). Les mesures d’équivalence sont utilisées dans les méthodes de blockmodeling pour partitionner les graphes en se basant uniquement sur les propriétés relationnelles des différents acteurs (voir B comme blockmodel).

Deux sommets sont dits structurellement équivalents lorsqu’ils ont les mêmes liens avec les mêmes sommets au sein d’un graphe. Il s’agit de la définition la plus stricte de l’équivalence, de fait l’équivalence structurale est relativement rare.

L’équivalence automorphique est plus souple que l’équivalence structurale. Il n’est en effet pas nécessaire, pour que deux sommets soient équivalents, qu’ils partagent les mêmes relations avec les mêmes sommets mais qu’ils aient la même structure de relations. En d’autres termes, deux sommets automorphiquement équivalents peuvent être interchangés sans modifier la structure du graphe, dans la mesure où ils possèdent les mêmes caractéristiques structurelles (degré, centralité, excentricité…). Cette définition plus souple rend possible l’équivalence automorphique de deux sommets appartenant à deux sous-graphes différents.

La définition de l’équivalence régulière est la plus souple. Elle regroupe les sommets qui ont le même type de liens avec le même type de sommets. On compte quatre positions de base des sommets : les isolés (isolate), les émetteurs (source, transmitter), les récepteurs (sink, receiver) et les intermédiaires (carrier).

En regroupant les sommets équivalents, on obtient un graphe réduit (reduced graph) qui résume les sommets à leur position. Ce graphe réduit correspond à la matrice bloquée du graphe (voir B comme blockmodel).

Dans le graphe ci-dessous, les couples de sommets {HI} et {EF} sont les seuls à être structuralement équivalents. On compte trois groupes de sommets concernés par l’équivalence régulière : {AB} ; {CD} ;  {EFGHI}. Si le graphe représentait un organigramme d’entreprise, l’équivalence régulière renverrait à un statut hiérarchique (directeurs, contremaitres, ouvriers) tandis que l’équivalence structurale renverrait à une même position dans l’entreprise (contremaitre sous les ordres de A, ouvriers travaillant sous les ordres de D…).

E equivalence 1

Dans le graphe ci-dessous, les différentes couleurs représentent des sommets automorphiquement équivalents : ils ont la même structure (degré, excentricité, centralité…) sans pour autant partager les mêmes liens avec les mêmes nœuds.

E equivalence 2

Pour aller plus loin : Synthèse du groupe FMR « Blockmodeling et équivalences », disponible sur Halshs.

Billet lié : B comme blockmodel

Retour au glossaire

Matthieu Drevelle

Doctorant en Géographie-Aménagement à l'Université Paris 1, UMR Géographie-cités, équipe CRIA - Transamo

More Posts

P comme (réseau) petit-monde

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 réseau est dit petit-monde (small-world network) quand il présente deux caractéristiques :
– la distance  moyenne entre toute paire de sommets est faible ;
– le niveau de clustering local est élevé, c’est-à-dire que les sommets sont généralement très connectés à leurs voisins immédiats.

Par définition, il est nécessaire que le graphe de départ soit connexe : un chemin doit exister entre toutes les paires de sommets.

La méthode de construction choisie par les mathématiciens Watts et Strogatz en 1998 consiste à partir d’un graphe k-régulier (tous les sommets ont  un même degré k) et à modifier de façon aléatoire un lien. La distance moyenne chute rapidement tandis que le niveau de clustering reste longtemps élevé. Les deux figures ci-dessous, extraites de leur article paru dans Nature en 1998, résument les caractéristiques de ces réseaux. Contrairement aux réseaux sans échelle qui ont été construits d’après des observations empiriques, les graphes petits-mondes sont d’abord une construction théorique.

Smallworld network 1

Réseau small-world

Le nom proposé par les auteurs fait explicitement référence à l’expérience de Stanley Milgran en 1961 et aux « six degrés de séparation » (l’idée qu’il est possible de joindre deux personnes quelconque via une chaîne de connaissances réduite). L’un des inconvénients est que les chaînes les plus courtes entre deux sommets, si elles sont faciles à déterminer quand on considère le graphe dans son ensemble, sont généralement inconnues si l’on se place du point de vue des sommets.

Si la méthode de construction est élégante, si la définition est intuitive, l’un des défauts majeurs de cette famille de graphes est qu’elle est susceptible de comprendre la très grande majorité de tous les réseaux empiriques existants. Comme pour les réseaux sans-échelle, l’intérêt réside peut-être moins dans la caractérisation de tel ou tel graphe que dans la création d’un nouveau modèle de graphe.

Billets liés : C comme (réseau) complexe, S comme (réseau) sans échelle.

Retour au glossaire