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

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.

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.

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.

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