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.

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.

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 :

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

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

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.

---

---