Posts from Graphes for 25/06/2014

D comme dyade 24 Jun 2014 03:25 pm | Anonymous 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 dyade (dyad) désigne une paire de sommets et une relation éventuelle entre ces deux sommets. Dans le cas d’un graphe simple non orienté, seules deux possibilités existent : présence ou absence de liens. Pour un graphe simple orienté, on distingue les liens nuls, les liens asymétriques (lien de i vers j mais pas de lien de j vers i) et les liens mutuels (présence du lien ij et du lien ji). Calculer la proportion de liens mutuels par rapport au nombre de liens  total fournit un premier indicateur sur le graphe examiné. Si dans un graphe non valué, l’étude des dyades reste relativement limitée, la situation change lorsque l’on a affaire à des liens valués. La famille des modèles gravitaires développés en analyse spatiale cherche ainsi à expliquer des intensités entre paires d’acteurs par des attributs portant sur les sommets et/ou les liens. Ces modèles reposent sur quelques hypothèses simples impliquant poids, distance et effet de barrière, et un exemple classique (tiré d’un cours de C. Grasland) concerne les échanges entre lieux : 1. les échanges entre lieux sont proportionnels à leurs capacités d’émission et de réception ; 2. l’importance des échanges entre deux lieux diminue lorsque la distance augmente ; 3. deux lieux situés dans deux espaces politiques différents  (i.e. Etat) échangent  moins que deux lieux situés dans le même espace. L’utilisation des modèles gravitaires pour l’analyse des réseaux valués constitue sans aucun doute l’une des pistes les plus prometteuses actuellement pour favoriser le dialogue entre la géographie et les autres disciplines. Billet lié : L comme lien, T comme triade Retour au glossaire Suite ... T comme triade 24 Jun 2014 01:39 pm | Anonymous 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). Une triade est constitué par un ensemble de trois sommets (triplets) et les liens éventuels entre ces sommets. Lorsqu’un lien est présent entre chacun des 3 sommets, on parle de triangle ou de triade fermée – il s’agit également d’une clique de taille 3 (tous les sommets possibles sont présents). Dans le cas d’un graphe orienté simple, le recensement des triades (triad census), proposé en 1975 par Holland et Leinhardt, liste les différentes formes de triades présentes : de la triade vide (aucun lien) à la triade complète (6 liens). Un code numérique à trois chiffres donne dans l’ordre le  nombre de liens mutuels, le nombre  de liens asymétriques (lien de i vers j mais absence de lien de j vers i) et enfin le nombre de liens nuls. On parle du code MAN (mutuel, asymétrique, nul). Dans la figure ci-dessous, on voit par exemple que la triade vide est notée 003, la triade complète 300. La lettre parfois présente permet de différencier les directions des liens : haut (Up), bas (Down), cyclique (Cyclical) et T (Transitive). 120D signifie donc 1 lien mutuel en bas, 2 liens asymétriques et aucun lien nul. Source : http://www.paulmichaelcohen.com/what-can-monkeys-tell-us-about-facebook/ (consulté le 17 juin 2014) Pour  la plupart des auteur-e-s, la triade est l’élément de base de l’analyse de réseau. Si la dyade permet de distinguer lien mutuel et lien asymétrique, la triade permet de mettre en évidence des phénomènes beaucoup plus riches, notamment au niveau sociologique, tels que la transitivité (si ij et ik sont présents, ik sera sans doute présent) ou la présence de trous structuraux (absence d’un lien au sein d’une triade). Billets liés : C comme clustering coefficient, T comme trou structural Retour au glossaire Suite ... Les indices Kansky avec R : premières fonctions 24 Jun 2014 01:31 pm | Anonymous K. Kansky est un géographe américain qui, dans sa thèse imprimée en 1963, proposa un certain nombre d’indicateurs permettant de caractériser des réseaux, indicateurs directement issus de la théorie des graphes. Si l’ouvrage est quasiment introuvable, le chapitre 2 Measures of network structure en 1989 paru dans la revue Flux est lui accessible sur Persée (http://www.persee.fr/web/revues/home/prescript/article/flux_1154-2721_1989_hos_5_1_913). Ces indices ont connu un succès foudroyant en géographie des transports et restent encore largement utilisés aujourd’hui. Bizarrement, aucun package R ne permet – à ma connaissance – de calculer ces indices. Le présent billet rappelle très brièvement la définition de ces indices, leur interprétation et fournit les fonctions R – basées sur le package igraph – permettant de les calculer. Petite précision : il s’agit de ma toute première tentative d’écriture de fonction, merci  donc d’être indulgent-e, ma marge de progression dans ce domaine étant immense… Merci à Serge L’homme qui m’a donné la formule pour le diamètre kilométrique et corrigé mon indice de Shimbel, merci enfin à Timothée Giraud qui est toujours disponible pour répondre à mes nombreuses (et souvent naïves) questions. J’en profite pour signaler leurs sites respectifs : site pédagogique de Serge Lhomme (http://serge.lhomme.pagesperso-orange.fr/) ; blog R géomatique de Timothée Giraud (http://rgeomatic.hypotheses.org/). Les indices de Kansky Soit e le nombre de liens, v le nombre de sommets et p le nombre de composantes connexes d’un graphe g, Kansky propose notamment les indices suivants : nombre cyclomatique mu = e – v + p. Plus il est élevé, plus le réseau est dense ; alpha : ratio entre le nombre de circuits présents et le nombre de circuits possibles : il varie entre 0 (arbre) et 1 (graphe complet) ; beta : e/v. Une valeur inférieure à 1 signale un arbre, beta ne peut dépasser 3 pour un graphe planaire ; gamma : ratio entre le nombre de liens présents et le nombre de liens possibles. Une formule est proposée pour les graphes planaires et une autre pour les graphes non planaires. Le terme densité employé dans les autres disciplines est synonyme ; degré de connectivité : v*(v-1) * 1/2(e). Ratio entre le nombre de sommets et le nombre de liens (son interprétation m’échappe – mais je suis loin d’être un spécialiste des graphes planaires et des infrastructures de transport…) ; indice de Shimbel : somme des toutes les distances entre les sommets. Peut être mesuré de façon topologique (distance mesurée en nombre de liens) ou pondéré (par une distance, un flux, une intensité etc.) eta : distance moyenne des liens, exprimé généralement en kilomètres ; pi : flux total divisé par le long des plus courts chemins kilométriques ; theta : flux total divisé par le nombre de liens (intensité moyenne) iota : distance totale divisée par le flux total Trois fonctions R Les données doivent avoir la forme suivante : un data.frame (tableau de données) ayant au minimum 3 colonnes : origine, destination et distance. Des colonnes peuvent être ajoutées pour porter des poids divers (flux de marchandises, débit horaire etc.). Cette liste de liens doit être transformée en objet igraph : le package igraph doit donc être appelé avant leur exécution (library(igraph)). La fonction kansky_un mesure les indicateurs ne prenant pas en compte les poids et les distances : diamètre (topologique), nombre cyclomatique, indice alpha (planaire et non planaire), beta, gamma (planaire et non planaire), le degré de connectivité et l’indice de Shimbel (topologique). La fonction kansky_di mesure les indicateurs prenant en compte une distance entre les sommets : diamètre (kilométrique), eta, pi et indice de Shimbel (pondéré). Le tableau en entrée doit impérativement avoir trois colonnes (origine, destination, distance). La fonction kansky_df mesure les indicateurs prenant en compte une distance et une intensité entre les sommets : indices theta et iota. Si le tableau de départ ne comprend pas 4 colonnes minimum, un message  d’erreur apparaît. Exemple reprenant une des figures utilisées par Kansky pour détailler le nombre cyclomatique (mu) library(igraph) d <- rbind(c(1,2), c(2,3), c(2,5), c(2,7), c(3,4),              c(4,5), c(5,6),  c(6,7)) g <- graph.data.frame(d, directed = FALSE) kansky_un(g) Fonctions téléchargeables ici. Suite ... Articles récents : Croissance et décroissance des réseaux – Paris, 25-09-14 – programme provisoire Label Propagation Clustering C comme clustering coefficient tnet : package R pour l'analyse de réseaux valués Girvan Newman Clustering Développé par RG, grâce à MailChimp et YahooPipes