{"word_count": 810, "character_count": 6303}
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&#160;: Numpy, Scipy&#160;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 networkxg=nx.Graph() # création du graphe gg.add_edges_from(arcs) # ajout des arcs de la liste arc au grapheprint(g.nodes()) # consultation des nœuds du graphe gprint(g.edges()) # consultation des arcs du graphe gPlusieurs&#160;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 gbet=nx.betweenness_centrality(g)&#160; # calcul des centralitésaspl=nx.average_shortest_path_length(g)print(aspl) # consultation des éloignements moyensSi 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 operatortri=sorted(bet.items(), reverse=True, key=operator.itemgetter(1))for i in range(len(tri)): # boucle affichant le nom des villes&#160; &#160; print(villes[int(tri[i][0])])# en fonction de l'opération de triPour analyser les forces et les faiblesses d'un réseau, il faut le mettre à l'épreuve. Pour cela, il existe un moyen radical&#160;: 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 gg2.remove_node(20) # suppression du nœud 20aspl2=nx.average_shortest_path_length(g2) # calcul sur le graphe perturbévul20=aspl2-aspl # comparaison des valeurs obtenues pour un même indicateurprint(vul20) # affichage du résultat correspondant à la perturbation engendrée par la suppression du nœud 20Dè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ésultatsfor i in range(len(g.nodes())):&#160;# boucle de la taille du nombre de nœuds&#160; &#160;g2=nx.Graph()&#160;# à chaque itération, création du graphe g2 qui sera perturbé&#160; &#160;g2.add_edges_from(arcs)&#160;# le graphe g2 est au départ identique au graphe g&#160; &#160;g2.remove_node(i)&#160;# à chaque itération, suppression d’un nœud (le numéro i)&#160; &#160;aspl2=nx.average_shortest_path_length(g2)&#160;# calcul sur le graphe perturbé&#160; &#160;dif=aspl2-aspl&#160;# à chaque itération on calcule la perturbation engendrée&#160; &#160;vul=vul+[(i,dif)]&#160;# 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ésultatsfor i in range(len(g.nodes())):&#160;# même code que ci-dessus&#160; &#160;if (i!=8 and i!=53):&#160;# on rajoute juste deux exceptions&#160; &#160; &#160; g2=nx.Graph()&#160; &#160; &#160; g2.add_edges_from(arcs)&#160; &#160; &#160; g2.remove_node(i)&#160; &#160; &#160; aspl2=nx.average_shortest_path_length(g2)&#160; &#160; &#160; dif=aspl2-aspl&#160; &#160; &#160; 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 «&#160;vulnérabilité&#160;» et la «&#160;centralité&#160;» 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 numpyvul2=nx.closeness_vitality(g)&#160;# calcul de vulnérabilité avec networkxmvul2=list(vul2.items())&#160;# transforme la bibliothèque en une listeavul2=numpy.array(mvul2)&#160;# transforme cette liste en une arrayx=avul2[:,1]&#160;# la variable x correspondant à la vulnérabilité des nœudsmbet=list(bet.items())&#160;# transforme la bibliothèque en une listeabet=numpy.array(mbet)&#160;# on transforme cette liste en une arrayy=abet[:,1]&#160;# la variable y correspondant à la centralité des nœudsfrom scipy import statsslope, intercept, r_value, p_value, std_err = stats.linregress(x,y)r2=r_value*r_value # calcul du r2print(r2) # affichage du r2A 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.