Les indices Kansky avec R : premières fonctions

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.

tnet : package R pour l’analyse de réseaux valués

La plupart des packages disponibles dans R permettent l’analyse de réseaux booléens (1 s’il existe une relation entre deux sommets i et j, 0 sinon) mais, si l’on souhaite étudier des réseaux valués (l’intensité des liens est variable entre les sommets), le choix est plus restreint. tnet est un package R maintenu par Tore Opsahl permettant l’analyse de réseaux valués simples et celle de réseaux bipartis et longitudinaux non valués. Le package est bien documenté, le site de Tore Opsahl est riche (http://toreopsahl.com/tnet/), cela méritait donc un billet un peu détaillé. Précision liminaire : tnet permet l’analyse mais non la visualisation des graphes, en effet, les objets manipulés par tnet sont de simples data.frame.

Je suppose pour la suite que R et le package tnet sont installés sur vos machines (voir les billets consacrés à R sur ce blog ou la foultitude de documentation disponible en français et en ligne sur le sujet).

Format des données et importation

Plusieurs jeux de données, classiques (le fameux Davis’ Southern Women Club) ou plus récents, sont disponibles dans tnet (voir la description détaillée sur la page http://toreopsahl.com/datasets/). Qu’on souhaite s’entraîner avec ou pas, il est intéressant d’y jeter un œil pour comprendre la structure des données. Elle est on ne peut plus simple : 3 colonnes origine – destination – intensité. Les attributs des sommets seront importés dans un fichier séparé. Si le réseau one-mode est non orienté, les liens devront être entrés deux fois (i-j et j-i). Les codes des sommets doivent être numériques et commencer par 1. La fonction as.tnet(jeu-de-données) permet de contrôler que la structure des données est correcte. Enfin, pour éviter la prise en compte des sommets isolés, la fonction compress_ids les supprime avant calcul.

Les fonctions se terminant par _w permettent l’analyse des réseaux valués (weighted), celles se terminant par _tm l’analyse des graphes bipartis (two-mode) et celles terminées par _l l’étude des réseaux longitudinaux.

Analyse des graphes valués one-mode

Le principe des mesures disponibles est simple : on fait varier un paramètre entre 0 – pas de prise en compte de l’intensité des liens – et 1 – prise en compte complète de l’intensité des liens. Il n’y a pas de recette miracle pour choisir le bon seuil et tout dépend de l’étendue des intensités : plus celle-ci  est grande, plus le paramètre devra être proche de zéro. Le petit graphe ci-dessous servira d’exemple pour cette partie :

tnet1

Pour le créer directement dans R :

rm(list=ls())
 library(tnet)
g <- rbind(c(1,2,3), c(2,1,3),
           c(1,3,4), c(3,1,4),
           c(2,3,1), c(3,2,1),
           c(3,4,2), c(4,3,2),
           c(4,5,1), c(5,4,1))

En pratique, mieux vaut évidemment importer ses données…

Les principales fonctions disponibles sont les suivantes :

degree_w(g) fournit un tableau à 3 colonnes : identifiant du sommet, degré et sommes des intensités des liens adjacents. Si je contrôle sur la figure, je vois par exemple que le sommet 3 a trois liens adjacents (degré) et que la somme des valeurs de ces trois liens est bien égale à 7 (4 + 2 + 1).

node degree output
 [1,] 1    2    7
 [2,] 2    2    4
 [3,] 3    3    7
 [4,] 4    2    3
 [5,] 5    1    1

closeness_w fournit un tableau de 3 colonnes : identifiant du sommet, centralité de proximité et centralité de proximité normalisée. La centralité mesurée ne repose pas sur le nombre de liens comme c’est le cas habituellement en analyse de réseau mais sur la somme des valeurs des liens parcourus. En d’autres termes, chaque intensité est assimilée à un coût et l’objectif est de trouver les chemins entre sommets minimisant ces coûts.

clustering_local_w et clustering_w fournissent les clustering coefficients locaux et globaux. Plusieurs prises en compte des intensités sont possibles avec l’argument measure = » ». Les principales options sont « am » (moyenne arithmétique, valeur par défaut de l’argument), « gm » (moyenne géométrique), « mi » et « ma » (respectivement minimum et maximum) et enfin « bi » (binaire). Dans ce dernier cas, l’intensité des liens n’est pas  utilisée.

D’autres fonctions et mesures sont disponibles (rich club coefficient global et local) mais il est fortement conseillé de relire attentivement les billets et articles de Tore Opsahl pour les utiliser à bon escient.

Analyse des graphes bipartis…

La structure des données est la même : origine – destination – intensité et, là encore, les deux ensembles de sommets doivent être numérotés de 1 à n. Attention donc à ne pas s’emmêler les pinceaux lors de la mise en forme… L’option type de la fonction as.tnet as.tnet(jeu-de-données, type= »weighted two-mode tnet ») – permet de contrôler la structure des données.

Les principales mesures disponibles sont la mesure de la distance (distance_tm()), le clustering coefficient global (clustering_tm()) et le clustering coefficient local (clustering_local-tm()). Là encore, mieux vaut relire d’abord ses articles et billets : ces mesures sont des propositions a priori pertinentes, ce ne sont pas (pas encore ?) des mesures communément utilisées.

… et analyse des réseaux longitudinaux

 Le package propose en tout en pour tout deux fonctions dont l’une (growth_l) qui prétend identifier les mécanismes responsables de l’apparition de liens entre  les sommets. Ayant à ce jour une connaissance fort limitée de l’analyse des réseaux longitudinaux,  je préfère ne pas m’avancer plus avant…

Dernier point : je déconseille en temps normal l’utilisation de packages développés et maintenus par une seule personne, le risque est en effet grand qu’il cesse brusquement d’être mis à jour avant de disparaître… Si je fais une exception pour celui-ci, c’est en grande partie due à la très grande qualité du site de Tore Opshal. Mais ce jeune homme (cf sa photo ici) travaillant dans le secteur privé, ne vous attachez quand même pas trop à son package….

 

 

Analyse de graphe et QGIS 2.0

Vous l’aurez sans doute déjà noté, la version 2.0 de QGIS est sortie en septembre 2013. Cette nouvelle version a suscité une certaine effervescence dans la sphère du SIG Open Source. Pour les développeurs du dimanche, cette évolution induisait quelques soirées de programmation afin d’apporter les modifications nécessaires au fonctionnement d’extensions développées dans des versions antérieures. Ainsi, je me suis attelé à mettre à jour les extensions présentées dans ce blog (billet 1, billet 2, billet 3). Il était selon moi dommage de laisser tomber en désuétude des extensions conçues il y a seulement un an. J’avais de surcroît plein de projets d’amélioration pour ces extensions, mais je me suis finalement laissé distraire (création d’un plugin d’analyse spatiale et d’un plugin permettant de calculer des modèles de localisation-allocation). Comble du ridicule, je n’ai pas pris le temps de publier cette mise à jour. QGIS est aujourd’hui à la version 2.2.

Je ne vais pas détailler dans ce billet les changements induits par cette nouvelle version en matière de programmation (vous pouvez trouver certains détails ici). Quoi qu’il en soit, je mets à votre disposition une nouvelle extension compatible avec QGIS 2.x (cliquez ici pour la télécharger). Une seule nouveauté est à noter : cette extension regroupe les trois extensions développées précédemment. De plus, cette extension incorpore directement NetworkX (bibliothèque sur laquelle ce plugin repose en partie). L’installation de cette extension est donc très simple.

qgisv2

Ce nouveau plugin regroupe le plugin d’analyse de réseau, celui d’analyse de vulnérabilité et permet de définir des communautés.

Pour installer cette extension, il faut tout d’abord dézipper le dossier téléchargé. Ensuite, il faut copier le dossier « network_analysis » dans « C:\Program Files\QGIS xxxx\apps\qgis\python\plugins\ ». Lancez QGIS et le tour est joué !

Une seule chose est à vérifier (car on apprend des commentaires passés). Lorsque vous dézippez un dossier sous Windows, il vous est proposé de l’envoyer vers un dossier du même nom. Ainsi, votre dossier « network_analysis » est lui-même dans un dossier « network_analysis ». Il faut éviter cette redondance. Ainsi, après avoir copié le dossier, vérifiez bien que votre arborescence est la suivante «C:\Program Files\QGIS xxxx\apps\qgis\python\plugins\network_analysis» et pas «C:\Program Files\QGIS xxxx\apps\qgis\python\plugins\network_analysis\network_analysis».

Arborescence correcte.

Arborescence correcte.

Pour effectuer les calculs, il est nécessaire de disposer de deux couches d’information géographique : une première couche contenant les nœuds et une deuxième couche contenant les arcs. La couche des nœuds doit impérativement contenir les identifiants des nœuds. Il est conseillé de choisir comme identifiant des valeurs numériques allant de 1 à n (vous pouvez télécharger un exemple ici). De même, la couche des arcs doit posséder un champ « identifiant ». De surcroît, cette couche doit impérativement comporter deux champs qui renvoient aux identifiants des nœuds formant les extrémités des arcs (vous pouvez télécharger un exemple ici).

A bientôt pour de nouvelles extensions…

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

Visualiser autrement son temps de transport en métro. (parisien)

L’application développée par Jérôme Cuvier est de celles qui sortent (vraiment) de l’ordinaire, et mérite donc qu’on y stationne quelques minutes.

Pour rejoindre une station de métro depuis une autre, il faut normalement scruter une version du plan (papier, numérique), repérer les différentes lignes à prendre, les éventuelles correspondances. Sur le site de la Ratp, la chose est facilitée puisqu’une version interactive est proposée ici. La possibilité est aussi offerte de calculer son itinéraire, d’estimer son temps de parcours en fonction du moment de la journée, d’afficher sa feuille de route etc.

Estimer son temps de déplacement en métro parisien relève d’un art qui tient beaucoup, beaucoup de l’expérience. Une petite astuce, bien connue, consiste à compter environ 2 minutes par station, ajoutées à celles-là, les temps de correspondance, la présence d’escaliers roulants ou pas, de tapis roulants lentement ou rapidement. Bref.

Avec l’application de Jérôme Cuvier, tout cela n’est pas terminé mais l’exercice peut devenir ludique.

Il faut d’abord sélectionner sa station d’origine : ici Châtillon-Montrouge. L’outil déstructure ensuite la topologie classique du réseau de métro, en reprojettant l’ensemble des stations sur un fond de plan centré sur la station de départ. L’utilisation d’un diagramme circulaire permet de visualiser le temps de déplacement depuis la station de départ vers l’ensemble des autres stations de métro, par tranche de 5 minutes. Le temps de trajet moyen depuis Châtillon-Montrouge vers n’importe quelle autre station est estimé ici à 33 minutes et 19 secondes.

plan de metro vu de Chatillon-Montrouge

Ensuite, après un survol (pas un clic) de la station de destination (Château-de-Vincennes, par exemple), l’application propose le sous-réseau de ligne(s) de métro qu’il faut emprunter, ainsi que le temps de parcours global. Plutôt saisissante cette manière d’afficher un cheminement « subjectif » (!), on dirait un chevelu.

sous-réseau de métro entre chatillon et vincennes

47 minutes de  temps de déplacement estimé, soit une de moins qu’avec le site de la ratp (je précise avoir mentionné des horaires de semaine et en journée). Mais si j’utilise l’astuce des 2 minutes par station, j’estime mon temps de parcours à 54 minutes (27 stations et une correspondance).

temps de transport chatillon-vincennes estime par le site de la ratp

Quelques bémols tout de même. On regrette l’absence d’éléments de repérage : les noms et numéros des lignes auraient été bienvenus. Aussi de ne pas pouvoir imprimer le résultat.

PS : il est bien sûr possible de conserver la position habituelle des stations du métro parisien.

Pour en savoir plus : Plan du métro interactif (Jerôme Cukier) 

Françoise Bahoken

Géographe et cartographe, je suis accueillie en détachement depuis décembre 2010 à l'IFSTTAR ; je suis par ailleurs membre-associée de l'UMR 8504 Géographie-Cités.

More Posts

MoMA: Inventing Abstraction > visualiser le réseau de la création artistique (1910-1925)

Le site du Museum of Modern Art de New-York (MoMA) propose une très belle rétrospective en ligne de l’exposition Inventing Abstraction (1910-1925) parue en 2013 .

Si le MoMA n’est pas à présenter, on souhaite noter la possibilité d’observer le réseau de relations de ces artistes du début du vingtième siècle. Plusieurs approches de l’exposition sont disponibles.

Tout d’abord, on peut aller faire un tour sur le MoMA Multimedia de l’exposition, en passant ici. Pour ma part, j’ai commencé par Behind the Scene: Inventing Abstraction.

Ensuite, on peut s’émerveiller devant l’ensemble du réseau des acteurs de la période moderne, qui correspond à la capture suivante :

 

On peut poursuivre l’exploration en sélectionnant un artiste d’intérêt, avec tout l’embarras qui va avec. La liste n’est pas courte – ni très longue d’ailleurs – et une soirée n’y suffirait pas : de A comme Josef Albers à W comme Max Weber ou encore Mary Wigman, en passant bien sûr par Piet Mondrian, Fernand Léger, Pablo Picasso, Man Ray et tant d’autres. Il y en a (presque) pour tous les gouts.

J’ai choisi d’observer ce que l’on nous propose pour Vaslav Nijinski (1889-1950), car c’est un grand chorégraphe, ancien danseur étoile (donc classique) des ballets russes  ; une partie de sa bio est disponible sur Wikipédia ici.

En traçant le réseau de relations de Vaslav Nijinski, on obtient sa position et les liens qu’il entretient avec les autres artistes proposés (ici).

L’application étant vraiment bien faite, outre son aspect ludique, agréable à manipuler et à regarder, une trop courte biographie de l’auteur est proposée. On a aussi accès à quelques reproductions. Dans le cas de Vaslav Nijinski, on peut admirer trois dessins, dont celui-ci :

 

Vaslav Nijinski : Untilted (Arc and segments : Lines), 1918-1919

On y apprend que ce dessin est réalisé à main levée, au crayon de couleur sur papier. On y voit une mise en scène de lignes courbes, qui traduisent un effet de convergence vers des points, comme le plan d’une chorégraphie de ballet… les trajectoires d’un réseau de danseurs ?. Y aurait-il là un lien avec le Sacre du Printemps, repris notamment par Maurice Béjart (voir ici) ? Le texte qui accompagne le dessin ne le dit pas. Mais on sait que Vaslav Nijinski a été surnommé « Le clown de Dieu », par Béjart lui-même. En tous les cas, on note que lorsqu’il réalise ce dessin, vers 1818-1919, l’auteur vit ses dernières belles années : il sera peu de temps après interné en hôpital psychiatrique, pour schizophrénie, pendant une bonne trentaine d’années. Il ne finira pas très bien … mais il est toujours possible de télécharger le graphe des relations généré en ligne.

L’onglet Conversations du même site permet aussi d’accéder à des interviews de ceux qui ont participé au making off de l’exposition, à la constitution des fichiers qui ont servi à générer le réseau de relations. On y trouve aussi un entretien sur les Networks and Creativity qui décrit ce réseau….

Au final, une très belle visite entre visualisation des réseaux et art moderne.

Pour en savoir plus :  http://www.moma.org

Françoise Bahoken

Géographe et cartographe, je suis accueillie en détachement depuis décembre 2010 à l'IFSTTAR ; je suis par ailleurs membre-associée de l'UMR 8504 Géographie-Cités.

More Posts

Un tutoriel pour faire des cartes de flux avec Qgis

Notre collègue cartographe et géomaticien Laurent Jégou vient de mettre en ligne un tutoriel bien pratique pour réaliser des cartes de flux avec le logiciel SIG libre Qgis: http://portailsig.org/content/qgis-concevoir-une-jolie-carte-de-flux

Le secret c’est d’utiliser la fonction « Hub Lines » du plugin Mmqgis (http://michaelminn.com/linux/mmqgis/) à partir d’une couche (shp) de points origines et une couche de points destinations.

Laurent Jégou complète son explication par une astuce pour rendre les lignes courbes. Un exemple de résultat obtenu avec les données Géoscience (UMR LISST, Université de Toulouse 2), la carte des collaborations internationales de Toulouse en 2008:

toulouse_collab

 

 

 

Votre ego-network… vu par google

Alors que l’affaire « Prism » (programme de surveillance de la NSA) a mis en évidence la délicate question de la protection de la vie privée sur internet, une équipe du MIT, dans le cadre d’un programme de recherche baptisé « Immersion », a mis en ligne une application permettant de visualiser notre ego-network à partir des métadonnées issues des mails envoyés et reçus sur la plateforme gmail. D’après la page internet du projet, « Immersion » se veut un outil d’introspection, d’aide à l’exploration de sa vie privée, de stratégie (pour mieux planifier ses relations professionnelles), mais il se présente aussi comme une démarche artistique. On note surtout sur cette page une absence de lien vers une documentation scientifique du projet.

Nouvelle image

L’application trace le réseau social de l’internaute à partir des champs « De »,  « A », « Cc »… et de la date d’envoi du mail. La taille des nœuds est proportionnelle au volume de mails échangé entre l’internaute (ego) et les membres de son ego-network. La taille des liens est proportionnelle au nombre de coprésence dans un même mail des différents acteurs. A noter que l’ego-network présenté n’en est pas totalement un puisque le nœuds de l’ego et les liens les reliant aux autres acteurs ne sont pas représentés (sans doute pour des raisons de clarté de la visualisation). Enfin, la couleur des nœuds, bien qu’aucune légende ne renseigne sur sa nature, renvoie probablement aux classes de modularité.

Le graphe présenté est dynamique et interactif, on peut ainsi sélectionner une période de temps et voir évoluer la structure de son réseau. Il est aussi possible de sélectionner un nœud en particulier pour avoir d’avantage d’information sur l’acteur.

ego_net

Pour ceux qui n’ont pas gmail (ou qui n’ont pas envie de transmettre leur login/mot de passe), il est aussi possible de visualiser un réseau de démonstration (composé de données réelles anonymisées).

Pour le site, c’est ici : https://immersion.media.mit.edu

Pour la démonstration, c’est là : https://immersion.media.mit.edu/demo#

Matthieu Drevelle

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

More Posts

L’analyse de réseaux avec R – un état des lieux (journée Semin-R du 24 mai 2013)

La courte présentation Beamer ci-dessous a été présentée à la journée Semin-R du 24 mai 2013 à Paris. Comme toujours, les commentaires – absents ici – permettent de nuancer ou de préciser le contenu des différentes diapositives. Il va de soi que cette présentation ne vise ni l’exhaustivité – je n’ai pas testé les 46 packages annoncés – ni l’objectivité. Elle  me semble pouvoir néanmoins servir d’introduction correcte au vaste champ de l’analyse de réseaux avec R.

Cliquer sur Crtl + L pour visualiser le diaporama (je n’ai pas encore trouvé l’astuce pour permettre l’affichage en plein écran…).

L’analyse de réseaux avec R, les premiers pas (deuxième partie)

Un premier billet publié début avril a présenté l’installation de R et de RStudio, le fonctionnement général du logiciel et a montré comment effectuer des mesures basiques sur un graphe à l’aide des packages statnet et igraph. L’objectif de ce billet est d’expliquer le plus simplement possible comment importer et transformer ses propres données et comment les visualiser. L’objectif de l’exercice est le suivant : importer un jeu de données comportant des attributs sur les liens et sur les sommets, puis de représenter le graphe en faisant dépendre la taille et la couleur des sommets de deux attributs et l’épaisseur des liens d’un troisième attribut.

Importer ses données

Les données proposées en exemple représentent un graphe fictif de relations entre enfants. Elles comportent deux fichiers : un fichier de type origine – destination – intensité concernant les liens non orientés existants, un fichier de type individus – variables qui précise les attributs de chacun des sommets (genre et âge). Pour télécharger le jeu de données et le script commenté dans ce billet, cliquer ici (les fichiers sont encodés en utf-8). En  règle générale, avec R, il est préférable pour limiter les risques d’erreurs d’importer des fichiers de format texte (.txt ou .csv).

La démarche à suivre est la même avec les deux packages : mettre en forme ses données, les importer dans R puis les transformer en un objet que statnet et igraph sont capables d’analyser. Détail important : ces deux packages ne permettent pas d’analyser des graphes valués (i.e. l’intensité des liens n’est pas prise en compte pour le calcul des indicateurs) mais, dans la représentation graphique, il est possible de faire varier l’épaisseur des liens en fonction de leur intensité.

Une fois vos fichiers placés dans un dossier, créez dans ce même dossier un fichier script.txt et changez l’extension pour obtenir script.R. Ouvrez-le ensuite avec RStudio.

Le début du script est le suivant :

rm(list=ls())
l <- read.table(« liens.txt », sep= »; », header=TRUE)
s <- read.table(« sommets.txt », sep= »; », header=TRUE, stringsAsFactors=FALSE)

La première ligne supprime tout les objets précédemment créés dans R, les deux lignes suivantes permettent l’importation des fichiers. Il convient de préciser leur nom, le caractère utilisé pour séparer les colonnes (sep= » »), éventuellement le caractère utilisé pour les décimales (dec= » ») et header=TRUE informe R que la première ligne contient les étiquettes de colonnes. L’option stringsAsFactors permet d’éviter que R ne transforme les caractères de la variable qualitative GENRE en facteur. Une fois les fichiers importés, vous pouvez les visualiser en cliquant sur eux dans la fenêtre Workspace. Il est toujours prudent, surtout lorsque l’on débute avec R, mais la règle reste valable ensuite, de vérifier avant toute opération que l’importation s’est bien déroulée.

Avec igraph

La transformation des données est relativement simple  avec igraph : la fonction graph.data.frame prend comme premier argument une liste de liens dont les deux premières colonnes doivent être les origines et les destinations. Les éventuelles colonnes supplémentaires seront considérées comme des attributs des liens. Les arguments suivants concernent la nature du graphe (orienté ou non notamment). Enfin, un argument vertices = permet d’importer les attributs des sommets. La ligne de code suivante permet donc de transformer nos deux fichiers en un objet igraph.

g <- graph.data.frame(l, directed=FALSE, vertices = s)

Pour la représentation, il faut d’abord définir les différents paramètres nécessaires et préciser les couleurs à utiliser, à quelle variable les attribuer, à quoi correspond la taille des sommets, l’épaisseur des liens etc. etc. Le code ci-dessous devrait vous donner la figure suivante – l’orientation des sommets pouvant être différente.

vertexCol <- get.vertex.attribute(g, »GENRE »)
colors = c(« Pink », »Blue »)
vertexCol[vertexCol == « F »] = colors[1]
vertexCol[vertexCol == « M »] = colors[2]

vertexSiz <- get.vertex.attribute(g, « AGE »)

edgeW <- get.edge.attribute(g, « INT »)

plot(g, vertex.color= vertexCol, vertex.size = vertexSiz,
      edge.width = edgeW)

Visualisation avec igraph

Avec statnet

La transformation en objet network analysable par statnet se fait à l’aide des commande as.matrix et as.network. Les noms sont explicites : as.matrix transforme une liste de liens en matrice ; as.network transforme la matrice en objet network. Donc, si vos données de départ sont au format matriciel, vous n’aurez pas besoin d’utiliser as.matrix… Dans la mesure où mes liens ne sont pas orientés, je le précise lors de la transformation avec l’option directed=FALSE. Je ne dois par contre prendre que les deux premières colonnes d’où les crochets et les parenthèses.

library(statnet)
ls <- as.network(as.matrix(l[,c(1:2)], directed=FALSE)
ls
gplot(ls)

La dernière étape consiste à transformer la dernière colonne du fichier l (intensité de la relation) et le fichier s (sommets) en données attributaires pour l’objet network ls créé à l’étape précédente. Cela se fait avec l’assignation %v% pour les sommets (v comme vertex) et %e% pour les liens (e comme edge).

ls %v% « GENRE » <- s$GENRE  
ls %v% « AGE » <- s$AGE
ls %e% « int » <- l$INT

Pour la  représentation graphique, il faut d’abord définir les couleurs à utiliser puis visualiser avec la fonction gplot. Cette fonction propose un très grand nombre d’options, le plus simple est de taper ?gplot puis de tester les différents scripts d’exemple. Bizarrement, il faut faire appel aux tableaux de départ et non à l’objet network pour personnaliser la visualisation. Les options utilisées ici sont les suivantes : gmode = « graph » signale que le graphe est non orienté ( = « digraph » dans le cas contraire) ; displaylabels permet d’afficher ou non les labels des sommets, vertex.col et vertex.cex permettent de choisir couleur et taille des sommets et enfin edge.lwd permet de moduler l’épaisseur des liens.

nodeColors <- ifelse(s$GENRE== »F », »Pink », »Blue »)

gplot(ls, gmode= »graph », displaylabels=TRUE, vertex.col=nodeColors,
      vertex.cex= s$AGE/4, edge.lwd = l$INT)

Le résultat obtenu ressemble – à l’orientation générale de la figure près – à ceci :

 Visualisation avec statnet

En guise de conclusion

Le premier billet vous a – théoriquement – permis d’installer R, RStudio et de tester différente mesures de graphe à l’aide des packages statnet et igraph. Vous savez maintenant importer vos données (liens et attributs) et visualiser vos graphes en fonction des attributs importés, vous êtes donc quasi autonomes. Un dernier conseil pour finir : prenez toujours le temps de bien parcourir les rubriques d’aide des fonctions.

EgoNet et Vennmaker : logiciels d’analyse de réseaux personnels

Un billet sur les réseaux personnels ou ego-network pour changer un peu. Qu’on se le dise, l’analyse de réseau n’est pas réservée aux fouilleurs de big data. Elle se prête très bien à une démarche de recherche plus qualitative. Les logiciels EgoNet et VennMaker, respectivement développés par des sociologues et des historiens, en témoignent.

Ces logiciels présentent la particularité d’associer un module permettant de générer un questionnaire ou guide d’entretien à un module de représentation et d’analyse de graphe. Bien que la partie analyse de graphe reste limitée, rien n’empêche l’utilisateur d’exporter le graphe de sortie et d’approfondir l’analyse avec des logiciels plus spécialisés (évoqués dans les autres billets du groupe fmr).

Les deux logiciels ne sont pas équivalents. L’utilisation d’EgoNet exige plus de rigueur que celle de VennMaker. Les deux logiciels permettent de construire un questionnaire dont les étapes sont bien balisées: le générateur de nom (« Citez-moi les personnes de votre entourage qui répondent à tel ou tel critère ») ; la qualification des relations entre un ego et ses alters (« Quelle est la nature de la relation que vous entretenez avec chacune de ces personnes ? ») ; la qualification des relations entre alters (« Quelle est la nature de la relation que ces personnes entretiennent entre elles ? »).

Ci-dessous, une capture d’écran de la partie entretien du logiciel Egonet :

Capture d'écran Egonet

Une fois le questionnaire généré, il est prévu que vous le complétiez, en direct, pendant l’entretien. Avec les réponses enregistrées, les logiciels génèrent le graphe du réseau personnel de la personne interrogée. Vous pouvez alors, le lui montrer, faire quelques traitements (calculs des indices de centralité basiques sur EgoNet) et en discuter avec elle.

Si c’est cette démarche qui vous intéresse, nous vous conseillons d’avoir plutôt recours à EgoNet car c’est l’interface qui s’y prête le mieux. En effet, la particularité de VennMaker est de permettre à son utilisateur d’intervenir directement sur le graphe sans qu’il y ait besoin du questionnaire. Contrairement à EgoNet, VennMaker permet de dessiner, littéralement, le réseau tout en réalisant l’entretien.

La souplesse de VennMaker est intéressante, à notre sens, s’il s’agit moins de réaliser un questionnaire qu’un entretien semi-directif. Les options de dessins sont originales pour, par exemple, rendre compte d’attributs multiples : on peut faire varier la forme et la couleur des nœuds et il est possible de les placer sur un cadran (en toile de fond) ce qui permet, éventuellement, d’indiquer leur localisation géographique.

Ci-dessous, une capture d’écran de l’interface graphique de VennMaker :

Capture d'écran VennMaker

Avec EgoNet, ce sont uniquement les réponses obtenues par le biais du questionnaire qui définissent le graphe. Cela permet d’éviter les erreurs d’interprétation du résultat a posteriori. En effet, le gros défaut de VennMaker est de permettre à l’utilisateur de modifier la configuration du graphe obtenu par le biais de l’entretien, après que celui-ci ait été réalisé. Le risque est alors important de ne plus pouvoir s’y retrouver. Un autre point positif en faveur d’Egonet : il est gratuit et libre ce qui n’est pas le cas de VennMaker (pour autant, une version d’essai gratuite est disponible en ligne). Les deux logiciels évoluent régulièrement pour pallier aux défauts rencontrés par les utilisateurs.

En conclusion, voici deux logiciels originaux pour les tenants d’une approche aux frontières du qualitatif et du quantitatif. Je remercie Ainhoa de Federico d’avoir organisé les deux ateliers méthodologiques qui m’ont permis de découvrir ces logiciels. Ces ateliers ont été organisés dans le cadre du Labex SMS (Structuration des Mondes Sociaux) à l’Université de Toulouse – Le Mirail. Le prochain atelier méthodologique aura lieu le 12 juin 2012 de 16 à 19h à la Maison de la Recherche (UTM).  Cette fois-ci, Juergen Lerner de l’Université de Konstanz viendra présenter le logiciel Visone (logiciel déjà évoqué sur ce blog).

Site du logiciel Egonet : http://sourceforge.net/projects/egonet/
Site du logiciel VennMaker : http://www.vennmaker.com/en/

Communautés, QGIS, R (igraph) et Python…

Toujours dans la continuité des billets précédents (billet 1) (billet 2) qui présentent des plugins d’analyse de réseaux spatiaux, ce billet présente un plugin permettant d’identifier des communautés au sein de ces réseaux. En effet, ce billet permet d’aborder d’une part un sujet important de l’analyse de réseaux, l’identification de communautés, et d’autre part les relations possibles entre R et QGIS via Python, puisque la bibliothèque choisie pour ces analyses est igraph.

igraph, qui est un package réputé sous R pour l’analyse de réseaux, dispose d’une extension Python. Dans un premier temps, il s’agit d’utiliser cette extension qui permet de travailler sous QGIS avec igraph et ce indépendamment de R. Pour utiliser igraph avec Python et par conséquent QGIS, c’est néanmoins un peu plus compliqué qu’avec NetworkX, car il faut cette fois-ci compiler la bibliothèque en question. Le plus simple consiste à télécharger l’installateur Windows pour Python 2.7 (http://igraph.sourceforge.net/download.html). Une fois l’installateur lancé, il suffit de bien préciser l’emplacement de Python dans QGIS « C:/Program Files/Quantum GIS Lisboa/apps/Python27 ». Normalement, dès le premier lancement de QGIS, tout fonctionne. Il est alors possible d’importer igraph via la console Python de QGIS.

Exemple de test du fonctionnement de IGraph sous QGIS via la console Python.

Exemple de test du fonctionnement de IGraph sous QGIS via la console Python.

Il convient ensuite de télécharger le nouveau plugin (cliquer ici pour l’obtenir). Il faut le dézipper, puis placer le dossier dans le répertoire suivant : « C:\Program Files\Quantum GIS Lisboa\apps\qgis\python\plugins ». Il suffit alors de lancer QGIS pour que le plugin apparaisse dans « Extension -> Analyse de Graphe… -> Detection de communautes ». S’il n’apparaît pas, il faut aller dans « Extension -> Gestionnaire d’extensions » et cocher l’extension « Detection de communautes (version 0.1) ». Après avoir lancé le plugin, une boîte de dialogue s’ouvre. Elle permet de sélectionner les nœuds et les arcs du graphe à étudier. Après avoir validé cette première boîte de dialogue, une deuxième boîte de dialogue apparaît. Elle permet de sélectionner les champs des extrémités des arcs, de préciser si le graphe est orienté ou non, de préciser si le graphe est pondéré ou non (et si oui, quel est le champ de cette pondération : distance, flux, importance…). Enfin, différents algorithmes sont proposés afin d’identifier les communautés au sein du réseau étudié.

Présentation de la deuxième boite de dialogue.

Présentation de la deuxième boite de dialogue.

Les différents algorithmes proposés par le plugin utilisant igraph sont les suivants :

  • Walktrap, algorithme développé par Latapy et Pons et fondé sur des marches aléatoires ;
  • Betweenness, algorithme fondé sur la centralité des arcs. Les arcs les plus centraux sont retirés progressivement, chaque nouvelle composante connexe définissant alors une nouvelle communauté ;
  • Multilevel, algorithme fonctionnant par agrégation de nœuds à une communauté afin d’améliorer la modularité ;
  • Eigenvector, algorithme séparant progressivement les communautés à partir des valeurs propres du graphe ;
  • Infomap, deuxième algorithme fondé sur des marches aléatoires.

Pour chaque algorithme, seule la solution optimale est retenue (c’est-à-dire celle offrant la modularité la plus forte). C’est pourquoi le nombre de communautés n’est pas demandé avant le calcul. La valeur finale de la modularité est indiquée afin de comparer les résultats obtenus par les différents algorithmes. Une fois le calcul terminé, les valeurs stockées correspondent aux communautés auxquelles appartiennent les nœuds. Il est alors possible d’afficher ces communautés :

Communautés issues de l’algorithme fondé sur la centralité des arcs.

Communautés issues de l’algorithme fondé sur la centralité des arcs.

Le fait d’utiliser l’extension Python de igraph interrogera sans doute quelques utilisateurs invétérés de R. Faut-il recoder en Python tous ses codes R et trouver une extension Python pour éventuellement les utiliser sous QGIS ? La réponse est non, puisqu’il est possible de faire interagir QGIS et R à l’aide notamment de la bibliothèque RPy. En effet, RPy est une interface Python pour R. Ainsi, cette interface permet en utilisant le langage Python d’interagir avec R et de bénéficier de l’ensemble des développements réalisés sous R. L’inverse est aussi possible. Pour cela, il faut repartir pour une opération de téléchargement (http://sourceforge.net/projects/rpy/files/OldFiles/) et de compilation. En partant du principe que le package igraph est bien installé sous R (il faut notamment vérifier sa présence dans « C:\Program Files\R\R-(x.xx.x)\library\ »), il est très simple d’exécuter des codes R sous QGIS et par conséquent de les exploiter. Par exemple, on va exécuter à partir de QGIS le code R suivant :

test <- function () {
library(igraph)
g <- barabasi.game(100,m=2)
eb <- edge.betweenness.community(g)
return(eb$bridges)
}

Ce code peut être sauvegardé comme étant le fichier test.r. Pour appeler ce fichier sous QGIS, il est possible d’utiliser la console Python de QGIS. Plus précisément, il suffit de taper les lignes de code suivantes :

>>> from rpy import * # Import de la bibliothèque Rpy
>>> r.source('C:/Users/serge.lhomme/Documents/R/test.r') # Chargement du fichier test.r
{'visible': False, 'value': <Robj object at 0x0CBBDA00>}
>>> resultat=r.test() # Exécution de la fonction test
Message d'avis :
package 'igraph' was built under R version 2.12.2
>>> resultat # Affichage du résultat
[198.0, 196.0, 194.0, 192.0, 190.0, 188.0, 186.0, 184.0, 182.0, 180.0, 178.0, 176.0, 174.0, 
172.0, 170.0, 169.0, 168.0, 167.0, 166.0, 165.0, 164.0, 163.0, 162.0, 161.0, 160.0, 159.0, 
158.0, 157.0, 156.0, 155.0, 154.0, 153.0, 151.0, 150.0, 149.0, 148.0, 147.0, 145.0, 144.0, 
143.0, 140.0, 138.0, 137.0, 136.0, 135.0, 134.0, 133.0, 132.0, 131.0, 130.0, 128.0, 126.0, 
124.0, 122.0, 121.0, 119.0, 118.0, 117.0, 115.0, 114.0, 112.0, 111.0, 110.0, 109.0, 108.0, 
106.0, 105.0, 104.0, 102.0, 101.0, 100.0, 98.0, 96.0, 94.0, 92.0, 90.0, 89.0, 87.0, 85.0, 
83.0, 81.0, 79.0, 77.0, 75.0, 73.0, 71.0, 69.0, 67.0, 65.0, 64.0, 62.0, 61.0, 59.0, 57.0, 
56.0, 52.0, 51.0, 47.0, 45.0]

A partir de ces simples commandes, il est possible d’appliquer ses codes R sous QGIS. Ce qui sera sans doute utile pour certains et ce qui augmente encore les possibilités offertes par QGIS.

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

Visualiser les graphes autrement avec yEd

yEd est un logiciel gratuit (mais non libre) utilisable sur tous les systèmes d’exploitation (Windows – XP, Vista, 7 et 8 -, Mac – OS X 10.4 à 10.8 – et Linux) et qui propose des visualisations originales et d’excellente qualité. S’il propose une poignée de mesures basiques (nombre de liens et de sommets, centralité), ce n’est pas là que réside l’intérêt de cet outil.

Le lancement du logiciel fait apparaître l’interface suivante – il est possible qu’elle soit légèrement différente en fonction de votre système d’exploitation.

Interface de yEd

Soit une liste de menus déroulants en haut, une série d’icônes et plusieurs fenêtres : en haut, une fenêtre donnant des renseignements sur le graphe, sur la gauche en haut, la fenêtre Overview donne une vue d’ensemble, Folder Contents liste les éléments disponibles et Structure View permet de faire des recherches sur les graphes utilisés.

Fenêtre PaletteIl est utile de faire apparaître la fenêtre Palette (menu Windows > Palette) qui permet de modifier l’aspect des sommets et des liens. La modification n’est pas prise en compte de façon instantané mais prend effet à l’ouverture du graphe suivante.

yEd sait notamment lire les formats de graphe suivants : .gml, .graphml, .grapmlz, .xgml. Il permet aussi d’importer des listes de liens ou des matrices depuis un fichier .xls. Dans ce cas, une boîte de dialogue permet d »indiquer quelle est la feuille à ouvrir, où se trouvent les origines et les destinations etc. J’ai testé des listes de liens et des matrices, l’importation se déroule sans aucun problème. L’ouverture se fait à l’aide du menu File > Open.

Une fois le graphe ouvert, le menu le plus intéressant est le menu Layout qui propose les choix suivants. Le choix d’un algorithme déclenche l’ouverture d’une boîte de dialogue qui permet de paramétrer l’espacement entre les sommets, le sens de lecture etc. Si le choix n’est pas réalisable (choisir une visualisation type Tree pour un graphe qui n’est pas un arbre par exemple), un message explicatif apparaît.

Menu Layout (yEd)

 Les exemples de visualisation ci-dessous utilisent les graphes des relations au sein des Misérables et celui des collaborations scientifiques collectées par Newman, ils sont téléchargeables en format .gml à l’adresse suivante : http://wiki.gephi.org/index.php/Datasets. Je reproduis deux détails, le premier obtenu avec l’algorithme Flowchart, le second avec l’algorithme Hierarchical (option compact). Évidemment, avec un gros graphe, la visualisation n’apparaît pas de façon instantanée et il convient d’attendre quelques secondes. Mais, une fois l’image obtenue, la navigation à l’intérieur est très fluide.

Algorithme Flowchart

Algorithme Hierarchical

La navigation à l’intérieur du graphe se fait en combinant la fenêtre Overview et les différentes loupes disponibles en icône. Celle de droite produit un grossissement localisé de bonne qualité. Il est possible également de zoomer et de dé-zoomer à l’aide de la mollette de la souris. On peut également sélectionner un sommet précis en utilisant la fonction Search de la fenêtre Structure View.

Zoom local (yEd)

Toutes les visualisations produites peuvent évidemment être exportées en format image ou vectoriel (Menu File > Export). Tous les principaux formats sont proposés (eps, jpg, bmp, svg, pdf etc.).

La prise en main est facile, les différents paramètres aisés à modifier et les résultats sont visuellement intéressants, un logiciel de visualisation – et non d’analyse, je me répète – recommandable donc.

Téléchargement, documentation et galerie : http://www.yworks.com/en/products_yed_about.html

La version testée est la version 3.10.2 sous environnement Windows 7.

Un plugin QGIS pour analyser la vulnérabilité structurelle de graphes spatiaux

Dans la continuité d’un précédent billet, qui présentait de manière succincte l’utilisation de Python afin de programmer un plugin QGIS d’analyse de réseaux spatiaux, ce billet présente un plugin permettant plus précisément d’analyser leur vulnérabilité structurelle. De plus, ce plugin permet d’introduire des recherches récentes en matière d’analyse de réseaux.

L’analyse de la vulnérabilité structurelle des réseaux connait un intérêt croissant. Les raisons de cet intérêt sont multiples. Ainsi, alors que le risque s’est imposé comme une problématique majeure au sein de nombreuses sociétés contemporaines, l’analyse structurelle constitue un moyen pertinent d’appréhender les problématiques de vulnérabilité. L’analyse structurelle se focalise sur l’étude de la forme, de la configuration des réseaux. La dynamique des flux au sein de ces réseaux n’est donc pas modélisée à l’aide d’équations physiques et les aspects purement matériels (fragilité intrinsèque des nœuds et des arcs) sont laissés de côté. L’approche structurelle permet alors une approche plus réflexive. De plus, elle peut constituer une alternative aux approches physiques modélisant les flux, ces approches physiques étant bien souvent trop complexes à mettre en œuvre sur de grands réseaux. Pour une bonne introduction, il est possible de consulter l’article de Jean-François Gleyze et Magali Reghezza (cliquer ici) ou cette synthèse du groupe fmr (cliquer ici).

Pour les personnes n’étant pas particulièrement intéressées par les problématiques de risques, il est important de préciser que l’utilisation des indicateurs et des algorithmes conçus à cet effet peut se révéler intéressante pour des analyses de réseaux plus classiques, afin notamment de mettre en évidence l’importance de certains composants (nœuds ou arcs).

Pour installer ce plugin, il convient tout d’abord de suivre les recommandations du précédent billet. Ainsi, la bibliothèque NetworkX (cliquer ici pour l’obtenir) doit être installée dans le répertoire des extensions Python de QGIS (par exemple : « C:\Program Files\Quantum GIS Lisboa\apps\Python27\Lib\site-packages »). En effet, pour assurer une certaine continuité avec le précédent plugin, j’ai choisi d’utiliser la même bibliothèque. Ainsi, si cette bibliothèque a déjà été installée pas besoin de recommencer cette installation. Ensuite, il convient de télécharger le nouveau plugin (cliquer ici). Il faut le dézipper, puis placer le dossier dans le répertoire suivant : « C:\Program Files\Quantum GIS Lisboa\apps\qgis\python\plugins ».

Il suffit de lancer QGIS pour que le plugin apparaisse dans « Extension -> Analyse de vulnérabilité ». S’il n’apparaît pas, il faut aller dans « Extension -> Gestionnaire d’extensions » et cocher l’extension « Analyse de la vulnérabilité d’un graphe (version 0.1) ». Après avoir lancé le plugin, une boîte de dialogue s’ouvre. Elle permet de sélectionner les nœuds et les arcs du graphe à étudier. Après avoir validé cette première boîte de dialogue, une deuxième boîte de dialogue apparaît. Elle permet de sélectionner les champs des extrémités des arcs, de préciser si le graphe est orienté ou non, de préciser si le graphe est pondéré ou non (et si oui, quel est le champ de cette pondération : distance, flux, importance…). Enfin, différents indicateurs sont proposés pour analyser la vulnérabilité structurelle du réseau étudié.

Boîte de dialogue et indicateurs

Concernant les indicateurs, l’allongement moyen calcule la moyenne des détours engendrés par la suppression d’un sommet. L’algorithme calcule alors cet indicateur pour tous les sommets. Ainsi, plus l’allongement moyen est important, plus le nœud doit théoriquement faire l’objet d’une attention particulière puisque sa défaillance engendre une reconfiguration importante du réseau. A noter que cet indicateur est corrélé avec l’indicateur de centralité intermédiaire (Gleyze, 2005 ; Lhomme, 2012). Cet indicateur présente le défaut de ne pas prendre en considération les éventuelles pertes de connexité liées à la suppression d’un nœud. En effet, certains détours seraient d’une valeur infinie. Pour pallier ce défaut, il convient alors d’analyser l’inverse de l’éloignement moyen (nommé par certains efficiency). Pour cet indicateur, le terme de centralité d’information a pu être utilisé (Crucitti et al., 2006). A partir de ces deux indicateurs, des cartes thématiques peuvent être réalisées.

Analyse de la centralité d'information

L’indicateur de vulnérabilité dynamique tente d’appréhender les problématiques liées à la reconfiguration du réseau après la défaillance d’un sommet. En effet, la reconfiguration imposée par la suppression d’un sommet peut engendrer une utilisation anormale (notamment une utilisation très supérieure par rapport à la normale) de certains sommets pouvant alors engendrer la défaillance de ceux-ci. Ainsi, l’objectif de cet indicateur est d’étudier les défaillances en chaîne pouvant être induites par la suppression initiale d’un sommet. Pour cela, il existe plusieurs solutions (Wang et Rong, 2011). Ici, l’indicateur calcule la tolérance minimale requise afin d’éviter que la moitié des composants du réseau soient perturbés par la suppression initiale d’un nœud.

Un dernier algorithme permet d’évaluer les conséquences induites par la suppression de plusieurs nœuds. Pour cela, des scénarios types sont étudiés : l’attaque de nœuds choisis aléatoirement, l’attaque des nœuds les plus centraux, l’attaque des nœuds de degrés les plus élevés, l’attaque des nœuds les plus centraux dynamiquement. L’ensemble de ces scénarios est présenté dans (Albert et al., 2004). En fonction du nombre de sommets perturbés, il convient alors d’évaluer les pertes de connectivité correspondantes. Comparativement aux autres indicateurs, une boîte de dialogue supplémentaire permet à l’utilisateur de préciser : le nombre d‘itérations à effectuer pour calculer le scénario aléatoire, le taux maximum de nœuds impliqués dans les scénarios (0 à 1), le répertoire où sera enregistrée l’image, le nom du fichier image, le type de format de l’image (.png ou .svg), la largeur et la hauteur de l’image, l’épaisseur des lignes et la taille des points.

Boîte de dialogue particulière à l'analyse de la vulnérabilité combinatoire

Ensuite, une boîte de dialogue affiche la progression du calcul. En effet, ce calcul, comme ceux des indicateurs d’allongement moyen et de vulnérabilité dynamique, peut être assez long. Enfin, le graphique final s’affiche.

Analyse de la vulnérabilité combinatoire

Pour finir, il est important de préciser que pour les deux plugins désormais implémentés, les nœuds des graphes doivent impérativement être numérotés en partant de 1, puis ne sauter aucune valeur.

Voici un jeu de données test (cliquer ici pour l’obtenir).

Références

Albert R., Albert I., Nakarado G., 2004, « Structural vulnerability of the North American power grid », Physical Review E, 69(2), pp. 1-4. http://arxiv.org/pdf/cond-mat/0401084v1.pdf

Crucitti P., Latora V., Porta S., 2006, « Centrality measures in spatial networks of urban streets », Physical Review E, 73(3), pp. 1-5. http://arxiv.org/pdf/physics/0504163.pdf

Gleyze J. F., 2005, La vulnérabilité structurelle des réseaux de transports dans un contexte de risque, Thèse de doctorat, Université Paris VII, Laboratoire COGIT-IGN, 826 p. http://tel.archives-ouvertes.fr/tel-00138991/

Lhomme S., 2012, Les réseaux techniques comme vecteur de propagation des risques en milieu urbain. Une contribution théorique et pratique à l’analyse de la résilience urbaine, Laganier R. & Serre D. (sous la dir.), Thèse de doctorat, Université Paris Diderot, 365 p. http://tel.archives-ouvertes.fr/docs/00/77/22/04/PDF/these_serge_lhomme.pdf

Wang J. W., Rong L. L., 2011, « Robustness of the western United States power grid under edge attack strategies due to cascading failures », Safety Science, 49(6), Elsevier, pp. 807-812. http://www.sciencedirect.com/science/article/pii/S0925753510002547

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

L’analyse de réseaux avec R, les premiers pas

R est un logiciel libre, multiplateforme et qui permet de réaliser à peu près tous les traitements de données possibles dont, bien entendu, l’analyse de réseaux. Seul inconvénient, il fonctionne à l’aide de scripts et nécessite donc l’apprentissage d’un langage particulier. Pourquoi alors l’utiliser ? Parce qu’il s’agit d’un logiciel très puissant, qu’il permet de tout faire, et surtout parce que, une fois le langage maîtrisé, il permet de gagner un temps fou. Une fois le script écrit, obtenir toute une série de mesures sur un graphe prend quelques secondes alors que la même opération avec un logiciel presse boutons nécessite quelques dizaines de clics… Ce billet s’adresse aux personnes tentées par R mais qui n’osent pas encore franchir le pas.

La première partie explique comment installer R, l’interface RStudio (et son utilité), comment charger les modules (packages) d’analyse de réseaux et le fonctionnement de l’aide. La deuxième partie montre quelques manipulations basiques sur les graphes fournis en exemple avec les modules. Un second billet détaillera les procédures d’importation de ses propres données (sommets, liens et attributs) et les possibilités graphiques du logiciel (mise en ligne prévue pour fin avril).

Installer R et RStudio

Première étape : se rendre sur le site http://cran.r-project.org/ et télécharger la version de R compatible avec votre système d’exploitation. Puis se rendre sur le site http://www.rstudio.com/ et télécharger la dernière version de RStudio. RStudio est une interface graphique qui facilite l’utilisation de R en rendant un certain nombre de fonctions (rubriques d’aide, actualisation des modules etc.) beaucoup plus simples à utiliser. Elle n’est pas indispensable mais elle est fortement recommandée quand on débute avec R.

Une fois les deux logiciels téléchargés, installez-les (sous Windows, clic droit et exécuter en temps qu’administrateur). Les choix proposés par défaut sont généralement pertinents, vous pouvez donc les laisser. Lancer ensuite RStudio et vous obtenez une fenêtre de ce type (la capture a été effectuée sous environnement Windows 7, RStudio version 0.97.336). Quatre fenêtres sont ouvertes : celle en haut à gauche accueille les scripts, c’est-à-dire la suite d’instructions que vous allez exécuter ; les résultats apparaîtront dans la fenêtre en bas à gauche appelée la console. La fenêtre en haut à droite liste les jeux de données utilisés et l’historique des manipulations effectuées. Enfin, la fenêtre en bas à droite héberge les rubriques d’aide, les sorties graphiques et la liste des packages installés.

Interface de RStudio

Charger un package

R est un logiciel modulaire. Certains modules sont inclus par défaut lors de l’installation du logiciel, d’autres plus spécifiques doivent être installés. Pour débuter en analyse de réseaux, deux modules sont indispensables : le package statnet (qui est en réalité un ensemble de packages dépendants les uns des autres) et le package igraph. D’autres packages existent et plusieurs billets de ce blog en présentent certains (voir les billets sur le module intergraph, le module bipartite, le module QuACN ou le module qgraph).

statnet et igraph sont des packages inclus dans la version de base de R mais ils ne sont pas actifs au démarrage. Il convient donc de les charger à l’aide des fonctions library(statnet) et library(igraph). Attention, mais j’y reviendrai pas la suite, ces deux packages ne peuvent pas fonctionner ensemble. Pour exécuter une fonction, deux possibilités existent : la taper directement dans la console puis taper Entrée ; la taper dans un script et taper Ctrl + Entrée pour l’exécuter. Le résultat est exactement le même. Mais tout l’intérêt de R est de créer des scripts (des suites de commandes) qui peuvent être sauvegardés (ce sont de simples fichiers texte ayant l’extension .R) et réutilisés ensuite. Une bonne habitude est donc, à l’ouverture de RStudio, de créer un nouveau script à l’aide des menus déroulants File > Create new R script. Le menu File permet de créer les scripts, de les sauvegarder à l’endroit de son choix, de les ouvrir etc.

Créer un script avec RStudio

Au fait, pourquoi deux packages ? statnet est développé par des sociologues férus de modèles statistiques (ERGM) ; igraph est développé par des physiciens et des informaticiens. On trouve dans les deux les mesures les plus communes en analyse de réseaux mais certaines ne sont proposées que dans l’un de ces deux packages. Par ailleurs, la simplicité des commandes et la clarté des résultats varie d’un package à l’autre. A titre personnel, l’importation des données attributaires me semble beaucoup plus simple avec igraph mais je préfère les visualisations proposées par statnet. Mais ceci est affaire de goût… Autre avantage d’utiliser deux packages, ce qu’on ne parvient pas à faire avec l’un,  on réussit généralement à le faire avec l’autre.

Les rubriques d’aide

Dans RStudio, lorsque que vous chargez un package à l’aide de la commande library(nom_du_package), l’aide s’affiche dans un onglet de la fenêtre Help. Si vous avez besoin de savoir comment fonctionne une instruction, il suffit de la taper dans la console, de taper Ctrl + Entrée et la rubrique s’affiche alors dans la fenêtre Help. Quand les créateurs et/ou créatrices du package ont fait du bon boulot, vous trouvez une définition de la fonction, sa structure (éléments indispensables et optionnels), les éléments pris en entrée et ceux fournis en sortie et enfin un exemple d’utilisation. La rédaction de la documentation étant en grande partie normée, ces rubriques sont généralement de bonne qualité (mais en anglais évidemment…).

Aide d'igraph dans RStudio

Les rubriques d’aide sont  – avec les forums et listes de diffusion consacrés à R – sont vos meilleurs alliés pour progresser rapidement. Lorsque que vous utilisez un package pour la première fois, prendre le temps de regarder les différentes fonctions, d’examiner les jeux de données disponibles, de tester les scripts d’exemple proposés vous fera gagner un temps précieux.

Mais il est temps d’entrer dans le vif du sujet… La suite du billet suppose que vous avez installé R et RStudio… et c’est tout.

Pour les deux packages, les manipulations proposées sont les suivantes : chargement d’un jeu de données, calcul de la densité du graphe, du nombre et de la taille des composantes connexes, et enfin calcul de deux mesures de centralités des sommets (degré et intermédiarité, soit en bon anglais degree et betweenness). Comme indiqué plus haut, les aspects liés à la visualisation et à l’importation de ses propres billets seront abordés dans un second billet.

Manipulations basiques avec statnet

Le petit texte qui suit est un script, c’est-à-dire une liste d’instructions. Les étapes sont toujours les mêmes : nettoyer l’espace de travail (rm = remove), charger le package, charger un jeu de données puis effectuer les opérations souhaitées sur ce jeu de données. Quand on débute (et même après), il est vivement conseillé de commenter ses scripts : il suffit de placer un croisillon (AltGr + 3 sur Windows, Maj + @ sur Mac). Et c’est bien un croisillon et non un dièse1…) et ce qui est tapé ensuite n’est pas pris en compte par le logiciel.

Plusieurs jeux de données sont fournis avec statnet et l’exemple proposé ici utilise le jeu de données nommé faux.magnolia.high. Ce graphe simule les liens d’amitiés sur un campus américain (pour obtenir plus d’informations, taper ?faux.magnolia.high dans la console, Entrée et les détails s’affichent dans la fenêtre Help).

rm(list=ls()) #supprimer tous les objets importés ou créés auparavant
library(statnet) #chargement du package  statnet
data(« faux.magnolia.high ») #chargement du jeu de données
g <- faux.magnolia.high #attribution d’un nom court (facilite la saisie)
g  #informations de base sur le graphe

Taper le nom de l’objet g permet d’obtenir les informations suivantes : nombre de sommets (vertices = 1461), caractéristiques du graphe (ici on apprend qu’il est non-orienté, non multiple, ne comprend pas de boucles et qu’il ne s’agit pas d’un hypergraphe : directed = FALSE hyper = FALSE loops = FALSE multiple = FALSE bipartite = FALSE). On apprend enfin qu’il comprend 974 liens et qu’il n’y a pas de données manquantes (total edges= 974 missing edges= 0 non-missing edges= 974). Dernier point, mais qui ne sera pas utilisé dans ce billet, l’existence d’attributs (sur les sommets et/ou les liens) est indiqué : chaque sommet comprend un nom et des indications portant sur le niveau scolaire, le genre et l’ethnie (Vertex attribute names: Grade Race Sex vertex.names).

gden(g) #calcul de la densité
component.dist(g) #nombre et compositions des composantes connexes

Cette dernière fonction crée trois objets différents : un objet membership qui précise pour chaque sommet la composante connexe à laquelle il appartient ; un objet csize (component size) qui donne la taille de chacune des composantes connexes ; un objet cdist qui décrit la distribution des tailles des composantes connexes. Si je souhaite utiliser ces résultats ensuite – et la remarque s’applique aux opérations suivantes – j’ai tout intérêt à créer un objet qui va stocker ces résultats et me permettre de les réutiliser ensuite. La procédure est simple, je fais précéder l’instruction d’un nom (prendre un nom explicite est recommandé) et du petit symbole <-, ce qui donne la ligne de commande suivante. Les résultats ne s’affichent pas dans la console mais sont stockés – et réutilisables – dans l’objet comp.connexe.

comp.connexe <- component.dist(g)
deg <- degree(g) #calcul des degrés
summary(deg) #informations sur les degrés (min, Q1, médiane, moyenne, Q3 et max)
bet <- betweenness(g) #calcul de la centralité d’intermédiarité
summary(bet) #informations sur la centralité d’intermédiarité
tab <- as.data.frame(cbind(g$vertex.names, deg, bet)) #création d’un tableau

Cette dernière ligne appelle un petit commentaire : je crée un tableau de données (as.data.frame) qui consiste à coller côte à côte 3 colonnes (cbind), ces 3 colonnes étant le nom des sommets (g$vertex.names), leur degré (deg) et leur centralité d’intermédiarité (bet). Cette étape n’est pas obligatoire mais on peut préférer stocker tous les résultats concernant les sommets dans un même tableau plutôt que de multiplier les objets à manipuler.

Manipulations basiques avec igraph

Le mini-script qui suit réplique la même suite d’opérations mais avec le package igraph (et avec un jeu de données différent, le fameux Zachary karate club dataset). Comme vous le verrez, les noms des fonctions se ressemblent parfois fortement. Mais, statnet et igraph ne pouvant être utilisés de façon simultanée, il convient tout d’abord de détacher le package statnet puis de charger le package igraph.

rm(list=ls()) #nettoyer l’espace de travail
detach(package:statnet) #détacher le package statnet
library(igraph) #charger le package igraph
library(igraphdata)#charger les jeux de données du package igraph
data(karate) #charger le jeu de données du Zachary karate club
g <- karate #lui donner un nom plus court
g #principales propriétés

Taper g donne le résultat suivant : IGRAPH U-W- 34 78 — Zachary’s karate club network + attr: name (g/c), Citation (g/c), Author (g/c), Faction (v/n), weight (e/n). Ce qui en termes compréhensibles se traduit de la manière suivante : le graphe est non-orienté (U undirected) et valué (W weighted), il comprend 34 sommets et 78 liens, son nom est Zachary’s karate club network et il comprend un certain nombre d’attributs : sur le graphe (g : nom, auteur et citation), sur les sommets (v comme vertex ) et sur les lien (e comme edge).

graph.density(g) #densité du graphe
comp.connexe <- clusters(g) # composantes connexes

La fonction clusters crée trois objets : un objet membership qui indique à quelle composante appartient chaque sommet ; un objet csize indiquant la taille des composantes connexes et enfin un objet no donnant le nombre de composantes connexes. Le graphe étant ici connexe, les résultats de cette commande sont d’un intérêt relatif.

deg <- degree(g) #degré des sommets
bet <- betweenness(g) #centralité d’intermédiarité
tab <- as.data.frame(cbind(deg, bet)) #création d’un tableau
head(tab,10) #examen des 10 premières lignes du tableau

Et c’est tout pour aujourd’hui… Dernier conseil pour finir : avec R, il est important de prendre son temps et d’examiner les problèmes de manière séquentielle. Si vous abordez R pour la première fois, vous ne pouvez pas en deux heures apprendre à importer vos données, à lancer et interpréter un modèle ERGM puis à produire une superbe visualisation. Mais, avec des recours réguliers aux rubriques d’aide, de petits scripts (abondamment commentés) que vous enrichissez au fur et à mesure (j’ai créé un tableau avec 2 indicateurs, il est facile d’en ajouter…), votre progression sera rapide et efficace.

Ressources en ligne

Ayant déjà souvent écrit sur l’analyse de réseaux avec R – et je ne compte pas m’arrêter là -, je me permets de renvoyer à ce billet publié il y a quelques mois.

1 Robin Cura est la personne  qui m’a permis de comprendre l’étendue de mon ignorance sur cet aspect crucial. Et il a évidemment raison : ♯ est un dièse, # est un croisillon….

L comme logiciel(s), ou comment choisir un logiciel pour l’analyse de réseaux

Il existe aujourd’hui plus de 90 logiciels dédiés à l’analyse de réseaux selon la page Wikipedia Social network analysis software (consultée le 31 mars 2013). Trois constats décourageants pour commencer :

  • il est impossible de connaître tous les logiciels  ;
  • il est impossible de suivre leur actualité ;
  • maîtriser un logiciel est un processus (plus ou moins) chronophage.

A ces trois constats s’ajoutent deux contraintes : l’une linguistique, l’anglais est obligatoire, que ce soit pour lire la documentation ou utiliser les menus ; l’autre disciplinaire, il est recommandé d’être bilingue Social network analysis (école Wasserman – Faust) / Physique et informatique (école Watts, Newman et al.). Mais il y a une excellente nouvelle : l’offre est abondante, diversifiée et les logiciels sont de plus en plus performants et faciles à prendre en main.

Les quelques éléments présentés dans ce billet visent à faciliter le choix d’un logiciel. Quatre séries de critères peuvent être utilisées (cette classification étant arbitraire et sans doute incomplète) :

  • les critères liés à l’utilisateur ou à l’utilisatrice ;
  • les critères liés aux données ;
  • les critères liés aux traitements souhaités ;
  • les critères liés au logiciel lui-même.

En ce qui concerne l’utilisateur ou l’utilisatrice, tout dépend de vos objectifs et de votre fréquence d’utilisation. Si vous projetez une utilisation régulière et plurielle de l’analyse de réseaux (mesures, modèles, visualisation), peut-être est-il utile d’attaquer R. Si vous avez besoin de temps à autre de produire une belle image (pour illustrer un billet, un exposé, un cours etc.), un logiciel presse boutons avec une interface simple est recommandé. Le choix d’un logiciel payant, gratuit ou libre est lui affaire de conviction personnelle. Attention, un grand nombre de logiciels non libres sont disponibles exclusivement sous Windows.

Un critère utile est également votre réseau personnel : si vous avez dans votre entourage des personnes qui maîtrisent tel ou tel logiciel, autant mobiliser leurs compétences ! Enfin, et ceci afin de contre-balancer les trois constats décourageants qui ouvrent ce billet, l’apprentissage est cumulatif : une fois que vous maîtrisez un logiciel, apprendre à en utiliser un second est plus facile et plus rapide. Et c’est heureux car, si votre pratique est régulière, vous vous sentirez rapidement limité avec un seul logiciel. Il n’est pas rare d’utiliser un logiciel pour la visualisation, un pour l’analyse et un troisième pour une fonction bien spécifique.

Concernant les données, tous les logiciels ne permettent pas d’analyser tous les types de graphes. Si votre graphe est simple, vous n’avez que l’embarras du choix. S’il est valué, biparti, multiplexe, constitué de réseaux personnels ou autre, le choix est plus restreint. Sans du tout prétendre à l’exhaustivité, voici une petite liste de logiciels spécialisés :

La taille du réseau importe. Si votre réseau est de taille réduite (moins de deux cents sommets), tous les logiciels ou presque sont utilisables. Si votre réseau comprend plusieurs milliers ou centaines de milliers de sommets et de liens, seule une poignée de logiciels est adaptée (R, Cytoscape, Gephi ou Tulip sont des candidats sérieux – il y en a évidemment d’autres). Mais attention, plus le graphe est gros, plus les traitements sont longs et plus les logiciels ont tendance à planter… y compris sur des machines performantes.

En ce qui concerne les traitements souhaités, tous les logiciels ne permettent pas de réaliser tous les traitements existants. Le logiciel rapide, ergonomique, multiplateformes, permettant à la fois le clic-bouton et les lignes de commande, les analyses multiples et les visualisations d’excellente qualité, ce logiciel n’existe pas (même si certains ne sont plus très loin). Et si votre objectif premier est de produire une belle image – ce qui n’a ici rien de péjoratif – vérifiez également que les visualisations peuvent être exportées en format vectoriel (.eps, .svg, .ai etc.) pour pouvoir être retravaillées ensuite. Passer quelques dizaines de minutes pour obtenir un résultat magnifique mais où on ne peut ensuite pas ajouter l’auteur, les sources ou retravailler la police est une expérience frustrante…

Dernière série de critères à examiner, le logiciel lui-même. Est-il payant, gratuit ou libre ? Multiplateformes ? Est-il facile à prendre en main (certains logiciels sont connus pour être particulièrement mal fichus) ? Est-il porté par une équipe, soutenue par des institutions ou s’agit-il d’un outil développé par une personne dans son coin ? Y a-t-il fréquemment des mises à jour ? Existe-t-il une liste de diffusion (mailing list) ? Quelle est la qualité de la documentation proposée ? Existe-t-il des tutoriels en français ?

L’aspect documentation est particulièrement important : si pour maîtriser un logiciel gratuit, il est nécessaire d’acheter un manuel à 30 ou 40 euros (voir Pajek ou NodeXL), peut-être le jeu n’en vaut-il pas la chandelle… Le format des données et leur compatibilité avec d’autres logiciels est un autre aspect essentiel : si je dois passer des heures pour mettre en forme des données et que le format est tellement spécifique qu’aucun autre logiciel ne sait les lire, est-ce bien utile de perdre autant de temps ? Car bien entendu, il n’existe pas (pas encore ?) de format standard… Une petite règle simple : un logiciel proposé sans jeux de données n’a pas grand intérêt car il est souvent nécessaire d’examiner la façon dont ils sont structurés pour pouvoir importer ensuite ses propres données.

Dernier conseil : pour apprendre à utiliser un logiciel, n’hésitez pas à écrire des fiches méthodologiques (j’importe mes données, j’exporte mes résultats, je personnalise mes visualisations etc.) voire des tutoriels puis à les partager. Parce que, de temps en temps, même en étant bilingue français – anglais et SNA – physique, c’est agréable de trouver des tutoriels corrects en français…

Retour au glossaire