Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

agrégation de sciences économiques et sociales préparations ENS 2003-2004 Les r

agrégation de sciences économiques et sociales préparations ENS 2003-2004 Les réseaux sociaux Théorie des graphes et structure sociale (Flament, 1965) Fiche de lecture réalisée par Damien Babet (ENS Ulm) Flament Claude (1965), Théorie des graphes et structure sociale, Paris, La Haye, Mouton-Gauthier-Villars 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. I. introduction à la théorie des graphes 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». II. Les réseaux de communication 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 uploads/Management/ reseaux-fiches-flament-1965.pdf