A propos 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"

Analyse des forces et des faiblesses d’un réseau avec R : le package NetSwan

Suite à l’école thématique RESEM « Etudier les réseaux sociaux : espaces, mobilités » qui s’est tenue du 21 au 25 septembre sur l’île d’Oléron, je me suis dit qu’il serait pertinent de sensibiliser davantage d’autres disciplines aux extensions que je développe concernant l’analyse des forces et des faiblesses des réseaux. En effet, durant cette école thématique pluridisciplinaire, seuls des géographes m’ont posé des questions concernant le plugin QGIS que je développe périodiquement. Il faut dire que les SIG restent avant tout utilisés par des géographes et que le plugin en question se focalise sur des réseaux spatiaux !

Ainsi, durant la semaine de pause pédagogique de cette fin d’octobre, j’ai entrepris d’écrire quelques fonctions permettant d’analyser les forces et les faiblesses d’un réseau à l’aide du logiciel R. Puis, afin de diffuser ces fonctions, je n’ai trouvé d’autres solutions que de produire un package. Autant le dire de suite, l’aide est très cursive et rédigée dans un anglais très moyen. Néanmoins, ce package est depuis le 31 octobre disponible sur le CRAN. Une des tâches les plus difficiles a finalement été de trouver un nom à ce package : ce sera finalement NetSwan pour « NETwork Strengths and Weaknesses ANalysis ». Ce package repose sur le package Igraph.

Cette version 0.1 est un ballon d’essai visant à étudier si ces développements sont pertinents en dehors du champ des réseaux spatiaux. Ainsi, seulement quatre fonctions sont proposées actuellement. Une fonction « swan_efficiency » qui se focalise sur la comparaison des valeurs d’éloignement entre le réseau normal et le réseau perturbé. Une fonction « swan_closenness » qui se focalise sur la comparaison des valeurs de proximité entre le réseau normal et le réseau perturbé. Une fonction « swan_connectivity » qui mesure le nombre de relations rendues impossibles lorsqu’un nœud est supprimé. Une fonction « swan_combinatory » qui reproduit les algorithmes d’erreurs et d’attaques développés par Albert et al. [1] [2].

Au-delà des exemples proposés dans l’aide, nous pouvons désormais analyser un réseau social aspatial comme le Zachary Karaté Club et tester sa résistance aux algorithmes développés par Albert et al. Pour cela, il convient de taper le code suivant :

library(igraph)
library(NetSwan)
karate<-make_graph("zachary")

res<-swan_combinatory(karate,10)

Le plus long consiste finalement à produire le graphique représentant les résultats de l’analyse :

plot(res[,1], res[,5], type="o", col="yellow", xlab="Fraction of nodes removed", ylab="Connectivity loss")
lines(res[,1],res[,3], type="o", col="red")
lines(res[,1],res[,4], type="o", col="orange")
lines(res[,1],res[,2], type="o", col="blue")
legend("bottomright",c("Random", "Betweenness", "Degree", "Cascading"),
lty=c(1,1,1,1), pch=c(1,1,1,1),

col=c("yellow","blue","red", "orange"))

Le code final est disponible ici. Il apparaît qu’avec 3 nœuds supprimés, il est possible de perturber plus de 60% des relations de ce réseau, quel que soit le type d’attaques. Seules les erreurs aléatoires produisent des perturbations moins importantes.

Si le besoin s’en fait ressentir, les pistes de développement pour ce package sont nombreuses. Premièrement, ce package ne supporte que les graphes définis avec igraph, il serait tout aussi pertinent de permettre l’analyse de graphes construits avec d’autres packages, comme par exemple statnet. Deuxièmement, les fonctions développées dans NetSwan proviennent avant tout de travaux se focalisant sur l’analyse des forces et des faiblesses de réseaux spatiaux. Il conviendrait de développer plus de fonctions qui tiennent compte des particularités des réseaux non spatiaux.

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

ENPC TD1 : Python (NetworkX) et analyse de réseaux

Dans le cadre d’un enseignement sur les risques à l’Ecole Nationale des Ponts et Chaussées, j’ai élaboré une séquence de cours concernant plus spécifiquement les réseaux techniques. Ce billet propose le résumé d’une séance qui est en lien direct avec les préoccupations de ce blog, puisqu’elle traite de l’analyse de réseaux avec une bibliothèque Python nommée NetworkX. Pour reproduire ce billet, il conviendra bien entendu d’installer Python, puis les bibliothèques : Numpy, Scipy et NetworkX 1.7.

Pour ce billet, nous disposons d’un fichier Python définissant trois listes (ici). Ces listes correspondent à une modélisation simplifiée d’un graphe du réseau autoroutier français. Il convient tout d’abord d’ouvrir ce fichier dans l’IDLE Python, puis d’exécuter ce code. Il est alors possible de construire le graphe du réseau à étudier.

import networkx as nx # import de la bibliothèque networkx
g=nx.Graph() # création du graphe g
g.add_edges_from(arcs) # ajout des arcs de la liste arc au graphe
print(g.nodes()) # consultation des nœuds du graphe g

print(g.edges()) # consultation des arcs du graphe g

Plusieurs indicateurs pouvant nous servir par la suite peuvent être calculés. Pour chaque nœud, on peut ainsi calculer le degré, la centralité intermédiaire ou l’intermédiarité (betweenness), l’éloignement moyen.

deg=nx.degree(g) # calcul des degrés des nœuds du graphe g
bet=nx.betweenness_centrality(g)  # calcul des centralités
aspl=nx.average_shortest_path_length(g)

print(aspl) # consultation des éloignements moyens

Si l’on souhaite afficher le nom des villes suivant leur niveau de centralité intermédiaire, il est possible d’utiliser la bibliothèque Operator :

import operator # import de la bibliothèque operator
tri=sorted(bet.items(), reverse=True, key=operator.itemgetter(1))
for i in range(len(tri)): # boucle affichant le nom des villes

    print(villes[int(tri[i][0])])# en fonction de l’opération de tri

Pour analyser les forces et les faiblesses d’un réseau, il faut le mettre à l’épreuve. Pour cela, il existe un moyen radical : supprimer des éléments du réseau et recalculer des indicateurs calculés au préalable afin de comparer les résultats obtenus. Pour un réseau transport, l’éloignement moyen peut être considéré comme un indicateur pertinent. Afin de conserver un graphe « intact », il peut être pertinent de travailler sur un deuxième graphe créé pour être perturbé.

g2=nx.Graph() # création du graphe g2 créé pour être perturbé
g2.add_edges_from(arcs) # le graphe g2 est au départ identique au graphe g
g2.remove_node(20) # suppression du nœud 20
aspl2=nx.average_shortest_path_length(g2) # calcul sur le graphe perturbé
vul20=aspl2-aspl # comparaison des valeurs obtenues pour un même indicateur

print(vul20) # affichage du résultat correspondant à la perturbation engendrée par la suppression du nœud 20

Dès lors, il est possible de généraliser ce calcul pour l’ensemble des nœuds du réseau étudié :

vul=[] # création du tableau qui contiendra les résultats
for i in range(len(g.nodes())): # boucle de la taille du nombre de nœuds
   g2=nx.Graph() # à chaque itération, création du graphe g2 qui sera perturbé
   g2.add_edges_from(arcs) # le graphe g2 est au départ identique au graphe g
   g2.remove_node(i) # à chaque itération, suppression d’un nœud (le numéro i)
   aspl2=nx.average_shortest_path_length(g2) # calcul sur le graphe perturbé
   dif=aspl2-aspl # à chaque itération on calcule la perturbation engendrée

   vul=vul+[(i,dif)] # ajout dans le tableau de la valeur obtenue pour un nœud supprimé

Néanmoins, à partir du 8ème élément (print(vul)), une erreur se produit. En effet, retirer un ou plusieurs éléments à un réseau n’est pas une opération neutre. En l’occurrence, certains éléments, s’ils sont retirés, peuvent notamment engendrer des ruptures de connexité (des pertes de connectivité). Ici, les ruptures de connexité engendrent l’impossibilité de calculer l’éloignement moyen puisque certaines distances deviennent incalculables (ces distances tendent en fait vers l’infini). Il faut alors créer des exceptions.

vul=[] # création du tableau qui contiendra les résultats
for i in range(len(g.nodes())): # même code que ci-dessus
   if (i!=8 and i!=53): # on rajoute juste deux exceptions
      g2=nx.Graph()
      g2.add_edges_from(arcs)
      g2.remove_node(i)
      aspl2=nx.average_shortest_path_length(g2)
      dif=aspl2-aspl

      vul=vul+[(i,dif)]

Comme précédemment, il est possible de trier les résultats obtenus afin d’identifier les éléments les plus problématiques. Il apparaît alors que ces éléments sont presque identiques à ceux apparaissant comme les plus centraux.

On peut alors chercher à mesurer le degré d’intensité de la relation existant entre la « vulnérabilité » et la « centralité » d’un nœud. Pour cela, il convient de trouver un indicateur de vulnérabilité pouvant se calculer pour tous les nœuds. NetworkX propose un indicateur qui fonctionne comme nous avons procédé, mais en utilisant un indicateur de proximité (closeness) et non d’éloignement, ce qui permet de palier au problème de rupture de connexité (en effet, en s’appuyant sur les inverses des distances, les valeurs tendant vers l’infini tendent vers zéro).

import numpy
vul2=nx.closeness_vitality(g) # calcul de vulnérabilité avec networkx
mvul2=list(vul2.items()) # transforme la bibliothèque en une liste
avul2=numpy.array(mvul2) # transforme cette liste en une array
x=avul2[:,1] # la variable x correspondant à la vulnérabilité des nœuds
mbet=list(bet.items()) # transforme la bibliothèque en une liste
abet=numpy.array(mbet) # on transforme cette liste en une array
y=abet[:,1] # la variable y correspondant à la centralité des nœuds
from scipy import stats
slope, intercept, r_value, p_value, std_err = stats.linregress(x,y)
r2=r_value*r_value # calcul du r2

print(r2) # affichage du r2

A la fin, on obtient un code propre que vous pouvez télécharger ici. S’il existe un lien entre vulnérabilité et centralité, celui-ci est imparfait. On essaiera de le montrer dans un prochain billet relatif à ces enseignements.

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

Analyse de réseau avec QGIS 2.x

Voici un cinquième billet concernant l’analyse de réseau et QGIS (billet 1, billet 2, billet 3, billet 4), car une certaine demande semble apparemment exister. En effet, lorsque que l’on consulte les statistiques du site, les pages relatives à QGIS et à la programmation Python apparaissent parmi les pages les plus visitées (pas autant que les pages relatives à R, mais quand même…). Les plugins présentés dans ces billets sont donc régulièrement téléchargés. En outre, comme quelques mises à jour ont été effectuées (les trois premiers plugins ont notamment été regroupés et complétés), il semble nécessaire de vous proposer un nouveau lien pour le télécharger (cliquez ici pour la télécharger).

Si vous voulez disposer à tout moment de la version la plus récente du plugin, je vous conseille de télécharger la version disponible sur mon site personnel (http://serge.lhomme.pagesperso-orange.fr/dev.html). Pour installer cette extension, il vous faudra tout d’abord dézipper le dossier téléchargé, puis 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. 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».

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

Le fonctionnement de cette extension est très simple. Premièrement, elle repose sur une décomposition en trois familles d’algorithmes : les algorithmes de base (Degree ; Closeness ; Betweenness ; Eloignement ; Clustering ; Eigenvector ; Square_clustering ; Eccentricity ; Page rank ; Average neighbor degree ; Hub_dependence) ; les algorithmes de vulnérabilité (Allongement moyen ; Closeness vitality ; Dynamique ; Combinatoire) ; un algorithme de détection de communautés (Méthode de Louvain). Vous avez accès à ces familles d’algorithmes via le menu QGIS dans « Extension → Analyse de graphe… ».

qgisv2

Après avoir choisi votre famille d’algorithmes, une boite de dialogue s’ouvre vous demandant de sélectionner votre couche contenant les nœuds et votre couche contenant les arcs. Puis, après avoir appuyé sur OK, une deuxième boite de dialogue s’ouvre permettant de renseigner les principales propriétés de votre graphe. Il est alors possible de sélectionner le champ correspondant aux nœuds de départ, le champ correspondant aux nœuds d’arrivée, d’indiquer si le graphe est orienté ou non et si le réseau est valué ou non. Si le réseau est valué, il vous faudra indiquer le champ correspondant à cette valuation. Enfin, il faut choisir l’algorithme que vous souhaitez appeler et si les résultats doivent être normalisés ou non.

boite

A l’heure actuelle tous les calculs se font sur les nœuds. A l’avenir, les calculs sur les liens seront proposés. Ainsi, une fois que vos choix ont été validés, puis les calculs exécutés, les résultats sont stockés dans la table comportant les nœuds. Grâce à QGIS, vous pouvez alors effectuer des discrétisations ou des caractérisations à partir du champ créé.

A noter que seul le calcul de vulnérabilité combinatoire diffère de ce fonctionnement général avec une boite de dialogue supplémentaire à compléter et des résultats stockés sous la forme d’une image.

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

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

P comme (graphe) planaire

Ces billets visent à définir le plus clairement et le plus précisément possible des termes clés en analyse de réseau. Ils s’adressent à un public débutant et évitent autant que possible toute formalisation mathématique (pour cette dernière, voir les synthèses fmr sur Hal-Shs).

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

planaire1

Analyse visuelle

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

planaire2

Analyse mathématique

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

planaire3

Analyse algorithmique

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

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

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

Retour au glossaire

Serge Lhomme

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

More Posts - Website

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

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

QGIS et l’analyse de graphe

Dans un précédent billet, il a été signalé qu’il existe peu d’outils intégrés au sein des SIG permettant d’analyser les réseaux. Néanmoins, les SIG libres peuvent être combinés à d’autres logiciels, programmes ou bibliothèques accroissant ainsi leur potentialité initiale. De plus, Grass (SIG libre qui, il est vrai, n’est pas des plus commodes à appréhender) permet d’effectuer différentes mesures sur des réseaux spatiaux.
Ce billet va présenter d’une part, comment réaliser un programme sur QGIS permettant d’analyser des réseaux spatiaux en ayant recours à des bibliothèques existantes d’analyse de réseaux (en l’occurrence, des bibliothèques développées en Python). D’autre part, ce billet va présenter un plugin réalisé à cet effet.

Utiliser une bibliothèque Python avec QGIS

Le SIG libre QGIS propose une console Python permettant d’interagir avec l’ensemble des outils de QGIS et par conséquent de développer de petits programmes automatisant plusieurs tâches. Dans les faits, il est plus souvent intéressant d’utiliser les nombreuses bibliothèques Python existantes afin d’étendre les capacités de QGIS. Par exemple, il existe de nombreuses bibliothèques permettant de réaliser de l’analyse de graphe (igraph, NetworkX…). Dans ce billet, nous allons utiliser NetworkX, bibliothèque développée originalement par Aric Hagberg, Dan Schult, et Pieter Swart (http://networkx.github.com/).

Pour utiliser une bibliothèque Python dans QGIS, il faut la télécharger (voici le lien pour la télécharger [1]), puis la dézipper et enfin la placer dans le répertoire des bibliothèques Python de QGIS. Ainsi, pour la version 1.8 (Lisboa) de QGIS, le répertoire se situe dans : « C:\Program Files\Quantum GIS Lisboa\apps\Python27\Lib\site-packages » (attention cette version de QGIS n’a pas été choisie par hasard, en effet elle implémente Python 2.7 qui est nécessaire pour la dernière version de NetworkX). Toutes les bibliothèques Python déjà présentes dans QGIS se trouvent dans ce répertoire (MapPlotLib, PyQt4…). La bonne complémentarité entre QGIS et Python est ici illustrée, car il n’y a plus rien à faire. Tout est installé et il est alors possible de réaliser de l’analyse de graphe avec QGIS, alors même qu’initialement ce n’était pas le cas.

Pour vérifier, il suffit d’ouvrir QGIS, d’aller dans « Extension -> Console Python », puis de taper les lignes de code suivantes :

>>> import networkx as nx  # Import de la bibliothèque NetworkX
>>> G=nx.Graph()  # Création d’un graphe G
>>> G.add_edges_from([(1,2),(1,3)])  # Création des arcs du graph G
>>> nx.clustering(G)  # Calcul les clustering coefficient des noeuds
{1: 0.0, 2: 0.0, 3: 0.0}
>>> nx.degree(G)  # Calcul les degrés des noeuds
{1: 2, 2: 1, 3: 1}

Analyser des graphes spatiaux dans QGIS avec Python

Cette étape est un peu plus complexe que la précédente. En effet, sans même avoir une grande connaissance de Python et de QGIS, il est possible d’utiliser la bibliothèque NetworkX dans QGIS en étudiant les tutoriels (voici le lien vers les tutoriels [2]). Faire interagir Python et QGIS ajoute un niveau de difficulté supplémentaire. Ainsi, partons du fait que deux couches ont été chargées dans QGIS. La première couche est composée de nœuds caractérisés par leur identifiant (vous pouvez télécharger un exemple ici). La deuxième couche est composée d’arcs caractérisés par leur identifiant, les deux identifiants des nœuds situés aux extrémités de l’arc et leur longueur (vous pouvez télécharger un exemple ici).

L’enjeu est alors de créer le graphe « NetworkX » à partir de ces deux couches. Pour cela, il faut récupérer les attributs des couches à l’aide de Python :

>>> canvas=qgis.utils.iface.mapCanvas() # Interaction avec la carte et les couches
>>> allLayers = canvas.layers() # Récupère les deux couches chargées dans QGIS
>>> couche_noeud = allLayers[0] # Récupère la couche supérieure
>>> couche_arc = allLayers[1]  # Récupère la couche inférieure
>>> provider = couche_arc.dataProvider() # Interaction avec la couche arc
>>> field=provider.fields() # Récupère les champs de la couche arc
>>> startind=provider.fieldNameIndex(‘depart’) # Index du champ « départ »
>>> endind=provider.fieldNameIndex(‘arrivee’)   # Index du champ « arrivée »
>>> distind=provider.fieldNameIndex(‘distance_K’) # Index du champ « distance_K »
>>> feat = QgsFeature()   # Permet de manipuler les entités des couches
>>> allAttrs = provider.attributeIndexes()   # Récupère les index des entités
>>> provider.select(allAttrs)   # Sélectionne toutes les entités 
>>> table=[]  # Création d’une table qui va récupérer les informations
>>> while provider.nextFeature(feat):  # Boucle parcourant l’ensemble des entités
…     attrs = feat.attributeMap()   # Récupère tous les attributs des entités
…     attrsstart=attrs.values()[startind].toInt()[0]  # Attribut nœud de départ
…     attrsend=attrs.values()[endind].toInt()[0]  # Attribut nœud d’arrivée
…     attrsdist=attrs.values()[distind].toInt()[0] # Attribut distance
…     table=table+[(attrsstart,attrsend,attrsdist)] # Ajoute les attributs récupérés à la table

Une fois les attributs des couches permettant de créer le graphe récupérés et après les avoir collectés dans un tableau, il est possible d’analyser ce graphe à l’aide la bibliothèque NetworkX :

>>> import networkx as nx  # Import de la bibliothèque NetworkX
>>> G=nx.Graph() # Création d’un graphe G
>>> G.add_weighted_edges_from(table) # Ajout des entités de la table au graphe G
>>> b=nx.betweenness_centrality(G,weight=’weight’) # Calcul de la centralité des noeuds du graphe G

Enfin, il est possible de récupérer les résultats obtenus pour les implémenter dans la couche nœuds :

>>> provider2 = couche_noeud.dataProvider() # interaction avec les données
>>> nbcol=int(provider2.fieldCount()) # Récupère le nombre de champs de la couche
>>> from PyQt4.QtCore import *   # Import de la bibliothèque PyQt4
>>> from PyQt4.QtGui import *   # Import de la bibliothèque PyQt4
>>> provider2.addAttributes([QgsField(« centralite », QVariant.Double)])
>>> taille=len(b)  # Récupère le nombre de nœuds
>>> couche_noeud.startEditing()  # Permet l’édition de la couche nœuds
>>> for k in range(taille):  # Boucle qui parcoure l’ensemble des nœuds
…      couche_noeud.changeAttributeValue(k,nbcol,b[k+1]) # Attribution des valeurs
>>> couche_noeud.commitChanges() # Enregistrement des changements

Toutes ces lignes de commande peuvent être récupérées et réorganisées pour créer un petit programme permettant de calculer les centralités des nœuds d’un graphe spatial (lien vers un fichier zip contenant un exemple ici) :

>>> execfile(« C:/Users/XXXXX/Desktop/centralite.py »)       # Appelle le programme à exécuter

Utiliser un plugin QGIS pour analyser des graphes spatiaux

Pour développer un plugin en Python dans QGIS, des connaissances supplémentaires en programmation sont nécessaires. Elles ne seront pas développées dans ce billet. Elles peuvent être trouvées sur ce site internet. Je vais plutôt introduire un petit plugin que j’ai développé. Il n’est pas très exhaustif, mais a pour objectif de montrer ce que l’on peut obtenir en combinant QGIS et une bibliothèque Python d’analyse de graphe.

Le dossier zip à télécharger se trouve ici. Une fois le dossier téléchargé et dézippé, il faut le placer dans le répertoire des plugins Python de QGIS. Pour la version Lisboa, le répertoire est le suivant : « C:\Program Files\Quantum GIS Lisboa\apps\qgis\python\plugins ». Le plugin est alors installé. Ensuite, il suffit de lancer QGIS pour que le plugin apparaisse dans « Extension -> Analyse de graphe ». S’il n’apparait pas, il faut aller dans « Extension -> Gestionnaire d’extensions » et cocher l’extension « Analyse de graphe version 0.1 ». Après avoir lancé le plugin, une boite 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 boite de dialogue, une deuxième boite de dialogue apparait. 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 (ceux-ci peuvent être normalisés ou non).

Le tour est joué. Ainsi, un champ a été créé dans la couche des nœuds afin de stocker les résultats de la requête. Il est alors possible de réaliser une carte thématique finale.

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