Flament Claude (1965), Théorie des graphes et structure sociale, Paris, La Haye, Mouton-Gauthier-Villars
[lire ou télécharger cette fiche au format Word 2000]
L'ouvrage de Claude Flament se divise en trois parties, une « introduction à la théorie des graphes » qui en présente les principaux résultats mathématiques, « les réseaux de communication » qui applique ces résultats au problème particulier du transfert d'information dans un réseau, et enfin les « processus d'équilibration», qui porte sur les problèmes du type « les amis de mes amis sont mes amis ».
Plusieurs points doivent être précisés ici:
- Claude Flament est psycho-sociologue, mais le livre est avant tout un livre de mathématiques, particulièrement pauvre en données empiriques. Elles se réduisent en fait à quelques résultats d'études expérimentales en laboratoire sur les réseaux de communication. Des outils et des principes sont présentés, mais leurs usages restent limités. Tout cela se situe en grande partie dans la tradition de Harary et Cartwright, deux mathématiciens.
- Les mathématiques utilisées dans le livre sont datées. Parce que la théorie des graphes a progressé, mais surtout parce qu'une grande partie des résultats consistent en l'exposé d'algorithmes permettant de résoudre des problèmes dans les graphes (recherche du plus court chemin, de l'arbre couvrant minimum, etc.). C'est le développement de l'informatique depuis 40 ans qui rend un certain nombre de ces algorithmes caduques. Je me suis donc permis de rajouter un paragraphe, très incomplet, sur la notion de complexité, absente du livre.
- S'agissant d'un livre de mathématique, il est difficile d'en fournir un résumé. On peut en retenir principalement les principaux théorèmes, sans leurs démonstration, ainsi que certaines idées générales sur l'usage des graphes en sciences sociales. L'impossibilité de présenter des schémas complique la compréhension.
La théorie des graphes est fondée sur la théorie des ensembles. Pour schématiser, un relation dans un ensemble S peut être considéré comme un sous-ensemble R de S carré, le produit cartésien de S par lui-même. une relation peut avoir plusieurs propriétés, la réflexivité ((a,a) appartient à R), la transitivité (si (a,b) et (b,c) appartiennent à R alors (a,c) appartient à R), la symétrie (si (a,b) appartient à R, alors (b,a) appartient à R), la propreté (si (a,b) et (b,a) appartiennent à R, alors a=b). par exemple, la relation d'ordre «inférieur ou égal» sur les entiers naturels est réflexive, transitive, propre, mais elle n'est pas symétrique.
Quelques définitions: Un graphe peut donc être défini comme une relation, c'est-à-dire un sous ensemble G de l'ensemble des couples d'élément d'un ensemble S, S étant dans le cas d'un réseau social l'ensemble des individus. On peut également représenter un graphe par une matrice: chaque «case» représente un couple d'élément de S, et les cases marquée d'un 1 sont celles des couples qui appartiennent à R. On peut définir des sous-graphes (on enlève certains points et les arcs qui vont vers ou partent de ces points), des graphes partiels (on ôte certains arcs) ou des sous-graphes partiels de n'importe quel graphe. Un chemin dans un graphe, par exemple entre s et s' est un sous-ensemble complètement ordonné de R tel que le premier couple commence par s et le dernier finisse par s': c'est une suite d'arc qui relie s à s'. Un circuit est un chemin d'un point vers lui-même. Dans le cas d'un graphe non-orienté, ou symétrique (donc si R est symétrique), on peut parler d'arête à la place d'arc, de chaîne à la place de chemin, et de cycle à la place de circuit. Une arborescence est un graphe tel que tout point soit le point d'arrivée d'un et un seul arc, sauf un point qui n'est à l'arrivée d'aucun arc et qui est nommé la racine. Un arbre est une arborescence non-orientée: tout point peut être racine. Ni les arbres ni les arborescences ne peuvent contenir de circuit ou de cycle. un graphe est fortement connexe si de tout point il existe un chemin vers tout autre point. Un graphe est faiblement connexe ou simplement connexe si entre tout couple de point il existe un chaîne. C'est la version «non-orientée» du graphe fortement connexe. Attention, un graphe connexe ou fortement connexe n'est pas nécessairement un graphe de densité 1, ou une clique. Un graphe symétrique connexe est toujours fortement connexe. Dans un graphe qui n'est pas connexe ou fortement connexe, on peut définir des sous-graphes connexes ou fortement connexes, appelés composantes (fortement) connexes maximales: tout ajout d'un point quelconque à une composante (fortement) connexe maximale fait qu'elle n'est plus (fortement) connexe. On peut mesurer un degré de connexité par le nombre d'arcs ou d'arêtes qu'il faut enlever pour rendre le graphe non connexe. On peut également définir des points d'articulation: le sous-graphe privé de ce point n'est plus connexe. Cette notion reste peu développée ici par rapport à ce qui sera fait ensuite sur les liens faibles ou les trous structuraux.
Une notion intéressante par contre est l'usage qui est fait de la notion mathématique de treillis: il s'agit de classer différents graphes définis sur un même ensemble S de points. Sur l'ensemble de tous les graphes possibles avec les points de S, on défini une relation d'ordre partielle: G est inférieur à G' si et seulement si il suffit de rajouter un arc (respectivement une arête) à G pour obtenir G'. Le graphe maximum est donc la clique sur S, le graphe complet, et le graphe minimum est le graphe «vide», sans aucun arc. Le treillis est lui-même un graphe, un graphe de graphe. On peut donc définir une distance entre deux graphes définis sur un même ensemble S de points, qui correspond exactement au plus court chemin reliant ces deux graphes dans le treillis, c'est-à-dire au nombre d'arcs (respectivement d'arêtes) qu'il faut enlever puis ajouter pour passer d'un graphe à l'autre.
Enfin, parlons des graphes valués: on ajoute une application v au graphe telle qu'à chaque arc de R on associe une valeur réelle. En fait, les graphes non-valués , symétriques ou non, peuvent être considérés comme des cas particuliers des graphes valués, où tous les arcs (respectivement arêtes) ont une valeur de 1. L'application v est la valuation du graphe. La longueur d'un chemin n'est plus le nombre d'arc parcourus, mais la somme des valeurs de ces arcs. Un multigraphe est un graphe dans le quel se combinent plusieurs types différents de relations, c'est en fait plusieurs graphes définis sur le même ensemble S de points. Le multi-graphe le plus commun est celui qui mêle les relations affectives «positives» et «négatives», et peut également être interprété comme un graphe valué dont les valeurs sont soit 1 soit -1.
Je passe sur tous les algorithmes et leurs démonstrations, par exemple pour chercher la distance de tout couple de point (égale à l'infini si aucun chemin ne les relie): de tels algorithmes relèvent aujourd'hui de l'informatique et ne se font plus «à la main».
Cette partie est la moins intéressante du livre: elle
relève plus ou moins de la théorie des organisations, et cherche
à optimiser le parcours de l'information au sein d'un réseau déjà
constitué. L'idée de base est la suivante: si un groupe organisé
doit accomplir une tâche, alors on peut assimiler cette tache à
un transfert d'informations dans le groupe. On suppose qu'il existe un ensemble
d'informations, chacune détenue par un ensemble particulier d'individus,
et la tâche est définie par les points d'arrivée de ces
informations. Concrètement, pour faire les comptes d'une entreprise,
il faut organiser le voyage et la synthèse des informations de chaque
département vers le service de comptabilité.
L'originalité de Claude Flament (par rapport à Bavelas ou Leavitt)
est cependant l'introduction de cette notion de tâche: peu de conclusions
peuvent se tirer simplement en voyant la structure d'un réseau de communication:
il faut savoir à quoi il doit servir, c'est-à-dire qui détient
les informations et où elles doivent arriver. Un problème dans
ce modèle est donc défini par: un graphe G (orienté et
valué) représentant le réseau de communication; un ensemble
d'informations a, b, c, etc.; pour chaque information, l'ensemble des individus
qui les possèdent au départ; la tâche: pour chaque information,
les individus qui doivent la posséder à l'arriver. Le but est
de savoir si la tâche est réalisable dans le réseau (facile),
puis d'optimiser tous ces parcours.
On peut compliquer en introduisant des informations secondaires: elles sont obtenues à partir de la synthèse de deux ou plus informations primaires, synthèse qui se fait dès que ces deux informations parviennent au même individu. On voit que la simple recherche du plus court chemin ne suffit plus trouver l'optimum: supposons deux informations a et b détenues respectivement par Sa et Sb, qui doivent être synthétisée en ab puis parvenir à leurs destinataires Sx et Sy. Si l'on se contente de trouver les chemins les plus courts respectivement entre Sa et Sx, Sa et Sy, Sb et Sx, puis entre Sb et Sy, on risque de ne pas trouver l'optimum, puisque en faisant la synthèse le plus tôt possible on réalise des économies en ne faisant plus circuler qu'une seule information, ab pendant tout le reste du chemin, même s'il est un peu plus long.
Les résultats sont une série d'algorithmes qui vont des cas les plus simples (chaque information est détenue par un individu seulement et doit parvenir à un individu seulement) aux plus compliqués (informations secondaires). Lorsque une information est détenue par plusieurs individus au départ, il suffit de choisir le plus «proche» du destinataire, en comparant la longueur des plus court chemins. La véritable difficulté vient quand les informations ont plusieurs destinataires. En effet, grossièrement, il faut alors faire des «économies» en faisant circuler le plus longtemps possible l'information sur un chemin commun avant de la diviser entre différents chemins allant vers les différents destinataires. Le problèmes est facile lorsqu'on a deux destinataires. À partir de trois, la difficulté devient exponentielle: supposons que S1, S2 et S3 doivent avoir une même information: faut-il d'abord trouver un embranchement qui sépare les chemins entre S1 et S2 d'un côté, S3 de l’autre, ou bien entre S1 d'un côté et S2 et S3 de l'autre, ou encore entre S1 et S3 d'un côté, et S2 de l'autre. Pour chacune de ces possibilités on peut ensuite appliquer deux fois l'algorithme qui permet de trouver le plus court chemin lorsqu'on a deux destinataires. Supposons en effet que le plus efficace soit de diviser les chemins d'abord en un point x d'un côté vers S1 et S2 et de l'autre vers S3, avant de trouver un nouvel embranchement z pour aller vers S1 d'un côté et vers S2 de l'autre. On peut alors commencer par chercher le parcours optimal seulement pour S1 et S2, puis le parcours optimal pour S3 et z, grâce à l'algorithme qui fonctionne pour deux destinataires. Il faut ensuite recommencer en faisant des suppositions différentes. On voit que pour 4, puis 5, etc. destinataires, le nombre de recours à cette algorithme devient très élevé. Citons Flament: «il faut dire qu'il n'existe pas actuellement de méthode général satisfaisante».
De plus, de nombreuses hypothèses peuvent venir compliquer le modèle: on peut supposer que la duplication des message ait un coût (prix des photocopies), les coûts de communication, donc la valuation du graphe, peuvent être différents pour chaque information, on peut vouloir modéliser des phénomènes de saturation, tels qu'un arc est limité dans le nombre d'informations qu'il peut transmettre, ou vouloir introduire les question de temporalité, par exemple en supposant qu'une synthèse pour fournir une information secondaire ne peut être faite qu'une fois les informations primaires arrivée. Enfin, on peut introduire les risques d'erreur de transmission, de manière mathématiquement rigoureuse à partir de la théorie de l'information de Shannon. Dans ce cas, il faut donner une valeur à la réalisation correcte de la tâche pour pouvoir arbitrer entre redondance de l'information (et donc coût supplémentaire de communication) et risque d'erreur. La recherche de l'optimum est considérablement compliquée.
Mais surtout, le manque de liens avec une quelconque réalité empirique se fait cruellement sentir. Flament considère par exemple le réseau comme une donnée, l'optimisation ne jouant qu'ensuite dans le choix du parcours des informations. Mais on peut penser que les réseaux de communications sont mis en place selon des critères d'efficacité, et peuvent être modifiés. Le réseau est donc dynamique. La complexité même de la recherche de l'optimum laisse penser que les organisations réelles relèvent d'une rationalité limitée, qui recherche un parcours de l'information simplement satisfaisant et non pas optimum, d'autant que les coûts de communication ne sont pas toujours les postes les plus importants.
Les applications de ces modèles présentées par Flament relèvent presque exclusivement de la psychologie expérimentale:
Dans les problèmes concrets que nous allons maintenant présenter, il semblera qu'il y a disproportion entre les problèmes concrets et l'élaboration mathématique, et cela en deux sens: trop, ou pas assez de mathématique.
Dans l'étude expérimentale des groupes de travail, nous utiliserons les notions de réseau, modèle, organisation optimum; les cas seront tellement simples qu'il n'y aucun besoin d'élaboration mathématique.
Par contre, dans l'étude des groupes de discussion, les mathématiques que nous avons considérées sont nettement insuffisantes, tellement les problèmes sont alors plus complexes.
Nous pensons que la formulation mathématique est cependant un lien entre les différentes études; que l'étude expérimentale des groupes de travail en fonction des réseaux de communication est née et s'est développée sous l'impulsion des recherches mathématiques; que dans l'étude des cas plus complexes, nos élaborations soit s'intègreront dans un modèle mathématique plus vaste, soit constituent une assez bonne approximation d'aspects essentiels du problème - en bref, nous considérons que notre travail n'est pas tout à fait inutile, son utilité principale étant, peut-être, d'appeler d'autres chercheurs à reprendre ces analyses pour en fournir de meilleures.
Les études expérimentales rassemblent 4 à 6 participants qui ne peuvent communiquer que selon un réseau pré construit par l'expérimentateur (en général symétrique et non valué). L'expérimentateur prépare des réseaux plus ou moins centralisés (toujours connexes cependant, sinon l'intérêt est limité...) et mesure, au bout d'un certain nombre d'essai des participant, les parcours de communication, la partie du réseau qu'ils utilisent effectivement pour accomplir une tâche. Cette tâche consiste généralement en une sorte de Cluedo: chacun dispose d'un série de symboles, il faut trouver celui que tous les participants ont, ou celui qu'aucun n'a. Les formules de Flament permettent de calculer les organisations optimum et de comparer avec les organisations effectives. Pour synthétiser les résultats: au bout de cinq à six essais, les participants ont une organisation très proche de l'optimum. Ils arrivent d'autant plus rapidement à l'optimum qu'ils choisissent une organisation correspondant logiquement au réseau dont ils disposent (centralisée dan sun réseau centralisée, homogène dans un réseau homogène). L'étude des groupes de discussion consiste à faire écouter aux participants individuellement une série de signaux sonores rapprochés, à leur demander individuellement combien de signaux ils ont entendus, puis à leur demander de se mettre d'accord sur le nombre de signaux qu'ils on entendu. Le résultat final de l'accord est très dépendant de la structure du réseau, celle-ci permettant ou non l'alliance de participants qui ont des estimations proches.
Dans cette troisième partie, Flament aborde un usage complètement différent des graphes, qui sont maintenant complets et valués seulement par 1 et -1. Le problème est le suivant: on suppose que dans un graphe les relations peuvent être soit positives, soit négatives, toujours symétriques (on ne peut pas aimer quelqu'un qui nous déteste), et que le graphe est complet (c'est une clique, si l'on veut). On suppose que dans l'idéal, les relations positives sont transitives (les amis de mes amis sont mes amis), mais pas les relations négatives (les ennemis de mes ennemis sont mes amis). Par définition, un tel graphe est dit déséquilibré lorsqu'il existe un cycle tel que le produit des valeurs des arêtes soit égal à -1 (donc s'il y a un nombre impair d'arêtes négatives). Cela signifie que si l'on suit une série d'arêtes, jusqu'à revenir à l'individu de départ, on obtient quelque chose du genre «l'ami de l'ami de l'ennemi de l'ami ... de mon ennemi est mon ami» qui est contradictoire. Exemple: L'ami de l'ami de mon ami est mon ennemi. Contradictoire.
On comprend facilement cette règle si l'on se ramène aux relations triangulaires. Cette définition est en partie arbitraire et contestable: par exemple, pourquoi supposer que le graphe est complet? Pourquoi supposer que «les ennemis des mes ennemis sont mes amis»? Ne peut-on pas penser que les relations ne sont pas simplement positives ou négatives, mais même approximativement plus ou moins positives ou négatives (donc prendre un graphe valué sur tous les réels). Toutes ces critiques sont raisonnables, mais compliquent démesurément le modèle, sans proposer de modèle alternatif (par exemple, si A aime B pour 4, et B déteste C pour 20, quelle doit être la relation entre A et C pour équilibrer le graphe ?).
Dans les conditions précises de ce modèle et de cette définition de l'équilibre, on peut démontrer deux principaux théorèmes: un graphe est équilibré si tous ses triangles sont équilibrés. Un graphe est équilibré si il peut être partitionné en deux sous-ensemble (l'un étant éventuellement vide) tels que toutes les relations internes aux deux ensembles soit positives et toutes les relations d'un ensemble à l'autre soient négatives. On en déduit d'autres théorèmes: quelque soit un point a quelconque choisit dans un graphe, si tous les triangles comprenant a sont équilibré, alors le graphe est équilibré. On peut donc ne se soucier que des triangles comprenant un point précis, ce que Flament appelle une base d'équilibre de pivot a (pour le point a).
À partir de cette base d'équilibre, Flament démontre des algorithmes qui permettent notamment de calculer le degré de déséquilibre d'un graphe, défini au sens de distance du graphe au graphe équilibré le plus proche dans le treillis. À la réserve que ce processus d'équilibration ne suppose pas la possibilité de simplement supprimer des relations, on a là une méthode suggestive: plus un graphe est déséquilibré, plus nombreuses sont les arêtes dont il faut changer le signe pour revenir à l'équilibre, et réciproquement. Mais un même graphe déséquilibré peut se transformer en différents graphes équilibrés qui sont à égale distance. Flament introduit alors plusieurs hypothèses: Dans un graphe déséquilibré, les tensions ont tendance à faire basculer la valeur des arêtes. Toutes les arêtes ont la même chance d'être transformées, à la condition que le graphe ainsi obtenu soit moins déséquilibré que le graphe de départ. Puis le processus recommence tant que le graphe n'est pas équilibré. Pour donner une idée du raisonnement, supposons que l'arête (a,b) passe de négatif à positif, puis que l'arête (b,c) passe de négatif à positif. Cela revient au même que si ces transformations avaient eu lieu dans l'ordre inverse. Mais il est possible que si l'arête (b,c) change la première, alors (a,b) ne peux plus changer sans augmenter ou maintenir stable le degré de déséquilibre, et donc ne change pas. La probabilité d'aller vers un graphe où les deux arêtes ont changé de signe dépend donc de l'ordre dans lequel ces changements ont lieu. Parmi tous les graphes équilibrés à égale distance (dans le treillis) d'un graphe déséquilibré donné, certains sont donc plus probablement atteints que d'autres. Flament peut ainsi indiquer la manière la plus probable dont le graphe va se rééquilibrer: par exemple, l'exclusion de tel membre peut être plus probable que l'exclusion de tel autre... Il semble assez facile de raffiner ce modèle en supposant des solidités différentes des liens, et donc des probabilités différentes de changer de signe.
Là encore, les applications empiriques sont absentes. Un rapprochement est proposé avec certaines remarques de Lévi-Strauss (dans Anthropologie Structurale) sur la relation dans le carré fils/père/mère/oncle maternel. Les formes constatées par Lévi-Strauss correspondent à presque tous les graphes possibles dans lesquels la relation mère/fils est positive et dans lesquels il existe au moins une relation négative. Les plus fréquentes sont les formes correspondant à des graphes équilibrés (exclusion du père ou exclusion de l'oncle), moins fréquentes et plus floues sont les formes déséquilibrées dans lesquelles le seul moyen de revenir à l'équilibre en ne changeant qu'une seule relation est de changer pour le négatif la relation mère/fils. Enfin les formes déséquilibrées qui peuvent se rééquilibrer par le changement d'une seule relation, autre que celle mère/fils, sont très rares. «Il semble que l'accord entre le modèle et la réalité soit assez satisfaisante».
Les algorithmes proposés dans ce livres concernent tous des calculs faits à la main. L'utilisation d'ordinateurs permet de faire des calculs sur des graphes de taille beaucoup plus grande, et cela change principalement deux choses: cela permet des études expérimentales sur des groupes plus nombreux, ou sur des résultats empiriques plus complexes. Cela demande de distinguer les algorithmes en fonction de leur complexité. La durée de calcul d'un algorithme dépend en général de la taille du graphe sur lequel on l'applique selon un rapport plus ou moins élevé. Pour les petits graphes, la différence peut être négligeable. Pour les graphes très grands, elle peut être fondamentale, d'où l'intérêt de la notion mathématique de complexité.
Un graphe est généralement représenté dans un ordinateur par une matrice. Pour un graphe avec N individus, le graphe est donc d'une taille proportionnelle à N au carré. La complexité d'un problème est le rapport entre la taille de la donnée (ici N au carré en général) et le nombre d'opérations élémentaires que demande la résolution du problème (dans le pire des cas, avec le meilleur algorithme connu). On divise les problèmes en classe de complexité: la classe P correspond aux problèmes pour lesquels les meilleurs algorithmes connus sont «en temps polynomial», par exemple en temps linéaire ou en N puissance 4. La classe NP correspond aux problèmes pour lesquels les meilleurs algorithmes connus sont «en temps exponentiel», beaucoup plus longs donc que ceux de la classe P. Un certain nombre de problèmes, en particulier sur les graphes, sont dits «NP-complets»: on peut prouver que si on trouvait un algorithme qui résout le problème en un temps polynomial, alors tous les problèmes de classe NP seraient résolus en temps polynomial. La question n'est pas tranché, mais les mathématiciens pensent que les problèmes de classe NP ne seront jamais résolus en temps polynomial.
La conséquence pratique est claire: un certain nombre
de calculs que l'on souhaiterait pouvoir faire sur les graphes, et qui sont
théoriquement possibles, sont en pratique impossibles sur les graphes
trop grands (plus d'une dizaine d'individus par exemple) parce que les ressources
informatiques qu'ils demandent sont exponentielles par rapport à la taille
du graphe. Aujourd'hui, une analyse mathématique des réseaux sociaux
ne peut donc plus faire l'économie d'une mesure de la complexité
des algorithme qu'elle propose. Les algorithmes de recherche du plus court chemin
sont simple, en temps polynomial. Dans le cas des algorithmes de Claude Flament,
il est très probable que les algorithmes d'optimisation des réseaux
de communication qu'il propose sont NP-complets (mais ce n'est qu'une conjecture
personnelle), et donc inutilisables en pratique. On peut d'ailleurs se demander
non seulement dans quelle mesure un algorithme est utilisable pour la recherche,
mais aussi dans quelle mesure les individus dans un réseau peuvent avoir
conscience du réseau et avoir à son endroit des représentations
exactes, si de telles représentations demandent des calculs dépassant
de loin les capacités cognitives humaines.