Du réseau au récit… Une analyse diachronique des rues de Beauvais (Picardie)

Ces dernières années, le nombre d’outils permettant d’analyser des réseaux spatiaux au moyen de SIG a augmenté. Ceci a notamment engendré la multiplication de travaux ayant pour objet l’analyse des réseaux de rues, et leur comparaison tant spatiale que temporelle. En général, les comparaisons temporelles visent soit à mettre en lien usage du sol et configuration du réseau (Psarra, Kickert, et Pluviano 2013; Vaughan, Dhanani, et Griffiths 2013), soit à mettre en lien ces configurations avec des phénomènes connus tels la densification (Barthelemy et al. 2013), l’étalement urbain (Gudmundsson et Mohajeri 2013), ou encore la croissance et le renforcement de structures préexistantes (Strano et al. 2012).

Le travail présenté ici s’inscrit dans cette lignée, puisqu’il vise à mettre en lien la configuration du réseau de rues (sa forme) avec l’ensemble des processus de formation/ transformation d’une ville. Pour ce faire, la forme du réseau est étudiée, puis comparée de manière diachronique sur le temps long. On recherche ensuite des changements dans ces formes, changements qui sont enfin mis en relation avec des facteurs explicatifs, soit en introduisant les processus urbains en cours, soit en faisant appel au contexte (socio-économique, politique, …) du moment.

Cette méthodologie a été appliquée à la ville de Beauvais (en Picardie), sur trois dates : 1849, 1888 et 1960. Ici, un indicateur assez simple a été choisi : la largeur des rues. Une fois cette variable calculée pour les trois dates, nous avons établi des classes de largeur, puis cumulé les longueurs des rues comprises dans chaque classe de largeur. La distribution (longueur ; largeur) obtenue a ensuite été comparée à une loi de puissance inverse (cf. graphiques), qui correspond à un modèle très hiérarchisé, avec un très grand nombre de ruelles étroites, un nombre moyen de rue moyennement larges, et un très petit nombre de rues larges. L’objectif ici était d’obtenir pour chaque date un indicateur d’écart à cette loi, ce qui permettait de comparer plus facilement les trois distributions, et d’observer des changements.

Histogramme représentant, pour chaque catégorie de largeur, le linéaire des rues de 1849 (en bleu) et la distribution suggérée par une loi de puissance inverse (en rouge) Indicateur d’écart : 0,22. (Hachi, 2014).

Histogramme représentant, pour chaque catégorie de largeur, le linéaire des rues de 1849 (en bleu) et la distribution suggérée par une loi de puissance inverse (en rouge) Indicateur d’écart : 0,22. (Hachi, 2014).

Plan de la ville de Beauvais en 1871

Les résultats ont permis de révéler la proximité entre la distribution de 1849 et la loi de puissance inverse (graphique ci-dessus), chose qui indique que les largeurs de rues étaient très hiérarchisées durant cette période, avec un très grand nombre de rues étroites (de 1 à 7 m) et peu de rues larges.

capture-decran-2016-11-29-a-23-07-10histogramme_1888

Histogramme représentant, pour chaque catégorie de largeur, le linéaire des rues de 1960 (en bleu) et la distribution suggérée par une loi de puissance inverse (en rouge) Indicateur d’écart : 9,69. (Hachi, 2014).

Histogramme représentant, pour chaque catégorie de largeur, le linéaire des rues de 1960 (en bleu) et la distribution suggérée par une loi de puissance inverse (en rouge) Indicateur d’écart : 9,69. (Hachi, 2014).

Photographie de Beauvais après la reconstruction (alain.tairnaite.free.fr)

Photographie de Beauvais vers 1960 (alain.tairnaite.free.fr)

En 1888, la distribution s’éloigne d’une loi de puissance inverse, mais l’indicateur d’écart reste faible. En 1960, la distribution s’éloigne encore plus de la loi de puissance, ce qui confirme l’émergence d’un nouveau modèle. Cette comparaison semble révéler deux types de changements, un premier relativement faible entre 1849 et 1888, puis un changement plus important en 1960.

Beauvais, vue aérienne prise par M. Lecointre, M. Serre pilote

Beauvais, vue aérienne prise par M. Lecointre, M. Serre pilote, 1948.

Le contexte historique de Beauvais fournit des hypothèses d’explication à ces phénomènes. La tardive industrialisation de la ville à la fin du XIXe siècle n’a engendré que de faibles changements dans son tissu urbain, resté très marqué par son centre médiéval. Mais en 1945, ce dernier est presque entièrement détruit lors d’un incendie, et la reconstruction opérée jusqu’en 1960 est alors l’occasion de « moderniser » le tissu, et d’élargir les rues pour permettre le passage des automobiles.

Cet exemple illustre l’apport que peut constituer l’étude des caractéristiques spatiales des réseaux de rues dans l’identification de différents types de changements, plus ou moins impactants, qui affectent les tissus urbains. Une étude plus complète, sur un temps plus long et avec divers indicateurs (topologiques en particulier) devrait nous permettre de révéler des régularités dans la manière dont interagissent ces réseaux spatiaux avec les processus de formation/ transformation de la ville.

 

Références :

  • Barthelemy, Marc, Patricia Bordin, Henri Berestycki, et Maurizio Gribaudi. 2013. « Self-organization versus top-down planning in the evolution of a city ». Scientific reports http://www.nature.com/srep/2013/130708/srep02153/full/srep02153.html?WT.ec_id=SREP-639-20130801.
  • Gudmundsson, Agust, et Nahid Mohajeri. 2013. « Entropy and order in urban street networks ». Scientific Reports 3 (novembre). doi:10.1038/srep03324.
  • Psarra, Sophia, Conrad Kickert, et Amanda Pluviano. 2013. « Paradigm lost: Industrial and post-industrial Detroit–An analysis of the street network and its social and economic dimensions from 1796 to the present ». Urban Design International 18 (4): 257–281.
  • Strano, Emanuele, Vincenzo Nicosia, Vito Latora, Sergio Porta, et Marc Barthélemy. 2012. « Elementary processes governing the evolution of road networks ». Scientific Reports 2 (mars). doi:10.1038/srep00296.
  • Vaughan, L. S., Ashley Dhanani, et Sam Griffiths. 2013. « Beyond the suburban high street cliché-A study of adaptation to change in London’s street network: 1880-2013 ». Journal of Space Syntax 4 (2): 221–241.

 

 

Ryma Hachi

Ryma Hachi est doctorante à l’UMR Géographie-cités depuis Octobre 2014, sous la direction de Lena Sanders. Architecte et historienne de formation, sa thèse porte sur l’apport de l’analyse morphologique diachronique en histoire urbaine. Elle vise plus particulièrement à révéler, grâce à des outils tels que la théorie des graphes, les processus de formation et de transformation des formes urbaines.

More Posts

Groupe fmr – séance du 22 novembre 2016

Le mardi 22 novembre prochain, Natalia Zdanowska, doctorante à Géographie-cités, présentera ses travaux. Voici un court texte de présentation.

Systèmes de villes et intégration des pays de l’Europe centrale dans l’économie-monde: une analyse par les réseaux d’entreprises et les flux aériens transnationaux

Les villes centre-est européennes organisent un territoire culturellement hétérogène, rempli de conflits ethniques, religieux et géographiques datant de plusieurs siècles (Castles, 1995). La situation de cet espace se résume bien par la notion d’Europe de l’entre deux (Brunet, Rey, 1996). Malgré un tel contexte, du fait de leurs trajectoires communes au sein d’Empires et du bloc soviétique, les villes en Europe centrale et orientale* ont pu tisser des liens très spécifiques entre elles. Leur réorganisation après la chute du mur de Berlin constitue un aspect intéressant à étudier.

La question principale est de savoir comment s’est opérée l’insertion des villes d’Europe centrale et orientale dans l’économie-monde et dans la division internationale du travail après 1989. A-t-elle permis de renforcer les liens établis entre elles dans le passé ou a plutôt privilégié les relations avec les villes de l’Europe de l’Ouest voire d’autres villes du monde dans une logique de l’économie libérale ? Nous questionnons également l’état des relations avec les villes de l’ex-URSS.

Pour répondre à ces interrogations une analyse de la position des villes centre-est européennes est menée au sein des réseaux internationaux d’entreprises en 2013 et aériens entre 1989 et 2013. L’objectif est d’identifier les interdépendances spatiales entre villes centre-est européennes et de les comparer avec des connections établies avec d’autres villes afin de débattre sur l’existence d’un ou des systèmes de villes en Europe centrale et orientale aujourd’hui. L’outil principal pour aborder ces problèmes est la théorie des graphes.

Brunet, R., Rey, V. (1996) Géographie universelle : Europes orientales, Russie, Asie centrale, Paris, collection « Géographie Universelle », Belin.
Castles, S., (1995) « How nation states respond to Immigration and ethnic diversity », New Community, 21(3), 293-308.

* Considérée pour le travail comme les huit pays postsocialistes ayant rejoint l’Union européenne après 2004 (Bulgarie, Croatie, Hongrie, Pologne, Roumanie, Slovaquie, Slovénie, Tchéquie)

Prochaines séances
13 décembre : Initiation à Tulip par Natalia Zdanowska et César Ducruet
10 janvier : QGis pour l’analyse de graphes planaires – prise en main par Serge Lhomme
24 janvier : QGis pour l’analyse et la représentation de matrice de flux par Françoise Bahoken

Les séances sont ouvertes à toute personne intéressée mais il peut être prudent de signaler sa venue (groupe_fmr@yahoo.fr), la bibliothèque de la rue du four étant vite remplie.

Les séances ont lieu les mardis matin de 10 heures à midi au 13 rue du four, 5e étage, bibliothèque, Paris. Et nous commençons à l’heure.

Groupe fmr – séance du 8 novembre 2016

Le mardi 08 novembre prochain, Ryma Hachi, doctorante à Géographie-cités, présentera ses travaux. Voici un court texte de présentation.

Pour Edgar Morin, « toute interrelation dotée de quelque stabilité ou régularité prend caractère organisationnel et produit un système » (Morin, 1990 : 104). De ce point de vue, de nombreux réseaux, qui sont par nature des ensembles interconnectés, peuvent être considérés comme des systèmes, dès lors qu’on observe une certaine régularité dans les interrelations dont ils se composent.
L’objectif de cette intervention sera de révéler ces régularités, sur un réseau caractéristique de la forme urbaine : le réseau de rues. Dans ce réseau, les interrelations sont essentiellement d’ordre topologique, et peuvent être décrites grâce à des indicateurs issus de la théorie des graphes. Mon travail vise donc à démontrer que la comparaison des propriétés topologiques des réseaux de rues, de manière diachronique sur du temps long, peut être révélatrice de moments de stabilité, mais aussi de transition. Ces phénomènes seront ensuite mis en relation avec leur « contexte d’apparition » (politique, socio-économique, etc.), ce qui permettra de révéler l’impact de divers événements sur l’organisation du réseau de rues.
Après un état de l’art sur l’analyse diachronique des réseaux de rues, je présenterai ma méthodologie, quelques résultats préliminaires, et des hypothèses d’explication des phénomènes observés. Je prendrai pour cela appui sur deux cas d’étude, la ville de Beauvais, en Picardie, et celle de Raleigh, en Caroline du Nord.

Référence :
E. Morin – Introduction à la pensée complexe. Paris, ESF Éditeur, 1990, 158 p. Communication et complexité

Prochaines séances
22 novembre : Présentation et discussion des travaux de Natalia Zdanowska, doctorante à Géographie-cités
13 décembre : Initiation à Tulip par Natalia Zdanowska et César Ducruet
10 janvier : QGis pour l’analyse de graphes planaires – prise en main par Serge Lhomme
24 janvier : QGis pour l’analyse et la représentation de matrice de flux par Françoise Bahoken

Les séances sont ouvertes à toute personne intéressée mais il peut être prudent de signaler sa venue (groupe_fmr@yahoo.fr), la bibliothèque de la rue du four étant vite remplie.

Les séances ont lieu les mardis matin de 10 heures à midi au 13 rue du four, 5e étage, bibliothèque, Paris. Et nous commençons à l’heure.

Le groupe fmr est de retour – automne hiver 2016

Bonne nouvelle, la réunion de rentrée organisée la semaine dernière a été utile et le groupe fmr reprend donc du service avec deux axes de travail : des séminaires sur les travaux doctoraux en cours mobilisant l’analyse de réseaux et des séances de formation. Cinq séances sont prévues, un bilan sera fait de cette nouvelle formule puis nous aviserons.

Les séances sont ouvertes à toute personne intéressée mais il peut être prudent de signaler sa venue (groupe_fmr@yahoo.fr), la bibliothèque de la rue du four étant vite remplie.

Les séances ont lieu les mardis matin de 10 heures à midi au 13 rue du four, 5e étage, bibliothèque, Paris. Et nous commençons à l’heure.

Dates précises et titres provisoires
O8 novembre : présentation et discussion des travaux de Ryma Hachi, doctorante à Géographie-cités
22 novembre : présentation et discussion des travaux de Natalia Zdanowska, doctorante à Géographie-cités
13 décembre : initiation à Tulip par Natalia Zdanowska et César Ducruet
10 janvier : QGis pour l’analyse de graphes planaires – prise en main par Serge Lhomme
24 janvier : QGis pour l’analyse et la représentation de matrice de flux par Françoise Bahoken

Appel de rentrée – 7 octobre 2016

Le groupe fmr (flux, matrices, réseaux), groupe de géographes intéressé.e.s par les méthodes et outils de l’analyse de réseau(x), a été actif de 2010 à 2015.

A l’heure ou quatre des textes de la Journée d’étude de 2014 sont publiés dans un dossier spécial formant le prochain n°105 de la revue Flux – Cahiers scientifiques internationaux Réseaux et Territoires, le groupe fmr souhaite fêter l’évènement en organisant une réunion ouverte à tous, sans frontière disciplinaire :

le vendredi 7 octobre 2016 de 13h30 à 15h30,
dans les locaux de l’UMR Géographie-Cités
13, rue du Four 75006 Paris (5ième étage).

L’objectif de cette réunion est de se renouveler et de définir collectivement de nouveaux thèmes d’investigation. Le groupe souhaite, en effet, élargir ses motivations initiales tout en conservant son ancrage en géographie : alors que le texte fondateur, publié dans la revue Netcom https://netcom.revues.org/431, envisageait une meilleure intégration de l’analyse de réseau en géographie, le groupe fmr souhaite aujourd’hui élargir sa focale en renforçant, notamment, la prise en compte du rôle joué par l’espace (au sens large) dans l’analyse de réseaux en sciences humaines et sociales.

Cette réunion s’adresse donc à toutes les personnes intéressées par les activités du groupe et, surtout, désireuses de s’investir a minima, plus particulièrement aux doctorant.e.s intéressé.e.s par l’analyse de réseaux au sens large.

Merci de nous indiquer votre intérêt pour ce projet de renouvellement en envoyant un email à l’adresse : groupe_fmr <at> yahoo.fr. Des modalités plus précises vous seront ensuite communiquées.


Entre 2010 et 2015 ont notamment été organisés dans le cadre des activités du groupe fmr : Lire la suite

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

ENSAI 2016 – Analyse de réseaux sociaux, spatiaux et complexes

Comme l’année précédente, j’interviens 27 heures (18h cours + 9h TD) à l’ENSAI de Rennes sur l’analyse des réseaux sociaux, spatiaux et complexes. Le contenu des cours sera modifié et actualisé mais les billets mis en ligne (cf les billets taggués Cours) fournissent une base correcte. Les TD ont eux été totalement remaniés, seul le logiciel R étant désormais utilisé.

Calendrier et contenu

11 janvier, 14h-17h : Vocabulaire de base et survol historiographique multi-disciplinaire
22 janvier, 9h45-12h45 : L’analyse des réseaux sociaux
22 janvier, 14h-17h : TD Analyse et visualisation de réseaux avec le package igraph
26 janvier, 9h45-12h45 : Analyse de réseaux spatiaux et analyse de flux
26 janvier, 14h-17h : TD Analyse et visualisation de réseaux spatiaux avec les packages cartography et flows
2 février, 9h45-12h45 : Visualisation des données relationnelles : enjeux, principes et perspectives
2 février, 14h-17h : TD Accompagnement pour le projet personnel
12 février, 9h45-12h45 : Analyse des réseaux de grande taille
12 février, 14h-17h : Exposés, modélisations statistiques, bilan du cours

Modalités d’évaluation

Travail en binôme obligatoire.

Produire un fichier Markdown mobilisant l’analyse de réseaux pour étudier les relations diplomatiques mondiales (http://www.correlatesofwar.org/COW2\%20Data/Diplomatic/Diplomatic.html) ou les flux commerciaux mondiaux (http://correlatesofwar.org/data-sets/bilateral-trade). Le choix des traitements effectués, les limites des méthodes et des résultats obtenus seront précisés dans une annexe méthodologique (2 pages maximum).

Un exposé oral (10 minutes pour présenter les données, les hypothèses, les traitements et les résultats, 5 minutes pour présenter les limites et les pistes possibles, 10 minutes de questions) sera effectué le 12 février.

Un nouveau collectif en vue : le GDR Analyse de réseaux en SHS

Le groupe fmr (flux, matrices, réseaux), créé en 2010, rassemble des géographes intéressé-e-s par les méthodes d’analyse de réseaux, qu’elles aient été développées en géographie, en sociologie, en physique ou dans d’autres disciplines. Le dialogue avec d’autres disciplines a été mis en œuvre notamment dans les trois journées d’étude organisées à ce jour. Mais le noyau dur du groupe était et reste exclusivement composé de géographes. Autre point à souligner, le groupe fmr est un groupe de travail sans existence institutionnelle. Nous avons évidemment bénéficié du soutien financier (pour les journées d’étude) et logistique (prêt de salle pour nos réunions) de nos laboratoires d’appartenance mais le groupe fmr est et reste un groupe informel.

Il est apparu nécessaire de poursuivre le dialogue interdisciplinaire dans un cadre plus large – sortir de la communauté géographique et de la seule agglomération parisienne – et institutionnellement plus solide. Deux membres du groupe fmr (Serge Lhomme et moi-même), après avoir échangé avec de nombreux collègues (géographes et non-géographes) ont donc proposé au CNRS la création d’un groupement de recherche consacré à l’Analyse de réseaux en SHS. Ce groupement associe des chercheur-e-s et ingénieur-e-s de dix disciplines (sociologie, histoire, géographie, archéologie, droit, économie, informatique etc.) et d’une vingtaine d’institutions dans toute la France.

Prévu pour durer de 2016 à 2019, éventuellement renouvelable pour 4 ans, ce groupement de recherche s’est fixé les objectifs suivants :

1. créer une revue pluri-disciplinaire à comité de lecture en accès libre (articles en français ou en anglais : publications au fil de l’eau avec possibilité de dossiers thématiques);
2. développer une réflexion conceptuelle et méthodologique transdisciplinaire autour de nos pratiques par le biais de workshops annuels;
3. organiser des formations (initiation ou perfectionnement) sur des méthodes ou des outils;
4. constituer et mettre à disposition de la communauté scientifique internationale des bases de données et des programmes issus de nos travaux.

Un site propre au groupement de recherche sera mis en ligne dans les mois à venir.

 

 

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

Cartographie de flux avec le package cartography

Depuis hier, le package cartography développé par nos collègues Timothée Giraud (http://rgeomatic.hypotheses.org/) et Nicolas Lambert (http://neocarto.hypotheses.org), tous deux ingénieurs à l’UMS RIATE, est en ligne sur le CRAN. Il permet de faire beaucoup de cartes différentes dont des cartes de flux. Le script et les données utilisés dans ce billet sont téléchargeables ici (j’arrête provisoirement github, j’y fais un peu n’importe quoi…) – le script est encodé en utf-8 (pour règler l’encodage dans RStudio : Tools > Global Options > Default text encoding).

La documentation sur les fonctions est lisible et homogène et les exemples fonctionnent mais, bien entendu, ce qui est intéressant est de pouvoir importer et cartographier ses propres données. Deux fichiers sont attendus en entrée : une liste de liens (origine, destination, intensité de la relation) et un fond de carte au format .shp. Les deux donneront dans R un data.frame et un  SpatialPolygonsDataFrame (noté SPDF dans la suite du  billet). Il est bien entendu nécessaire que le code des unités spatiales soit le même dans les deux fichiers…

La première étape consiste à attribuer des coordonnées à la liste de liens à l’aide de la fonction getLinkLayer. La fonction prend comme argument : le nom du SPDF et les colonnes origine-destination du data.frame. Si l’identifiant commun n’est pas la première colonne du SPDF, il est nécessaire de préciser la colonne adéquate avec l’argument spdfid = « Nom_de_la_colonne ». Dans l’exemple téléchargeable, l’argument est utilisé.

La fonction plot(SPDF) permet ensuite de visualiser le fond de carte.

Deux fonctions permettent de cartographier les flux : propLinkLayer (épaisseur proportionnelle à l’intensité) et gradLinkLayer (flux discrétisés). Le script téléchargeable devrait vous permettre de comprendre la logique d’utilisation et les principales options. Dans les deux cas, l’orientation des flux n’apparaît malheureusement pas.

Signalons enfin la fonction legendPropLines qui permet de personnaliser la légende de la carte réalisée (fonction non encore testée à ce jour).

La réalisation de cartes est plutôt aisée mais, comme toujours pour la cartographie des flux, cela ne garantit pas nécessairement un résultat d’une grande lisibilité…

 

 

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

Sélection de flux avec R : le package flows

L’analyse et la représentation des flux supposent le plus souvent une sélection de ces derniers. La méthode classique en analyse spatiale des flux dominants (voir ce billet) et les méthodes des flux majeurs (garder x premiers flux par lieu, les x flux les plus install.packages(« flows », dependencies = TRUE)importants en volume, les flux représentant plus de x % d’un volume donné etc.) forment les deux grandes familles de sélection couramment employées.

Le package flows, développé en juin-juillet au sein de l’UMS RIATE avec mes collègues Timothée Giraud (voir le blog rgeomatic) et Marianne Guérois permet de choisir ses critères de sélection, de calculer des indicateurs statistiques et, pour les flux dominants, de visualiser la sélection effectuée. Il est disponible sur le CRAN donc s’installe normalement avec un install.packages(« flows », dependencies = TRUE).

Les fonctions de sélection et d’analyse prennent en entrée une matrice carrée origine – destination. Si les données de départ sont de type origine – destination – intensité, la fonction prepflows permet de passer en format carré.

La fonction statmat fournit pour une matrice origine destination un certain nombre d’éléments utiles pour connaître les données de départ mais également justifier statistiquement la méthode ou le seuil retenu. On obtient notamment le volume total de flux et les indicateurs statistiques de base sur ces flux (quartiles, moyenne, etc.), la densité, le nombre, la taille et la composition des composantes connexes, le degré pondéré et non pondéré des sommets. Des sorties graphiques permettent d’étudier la distribution des degrés (pondérés et non pondérés) et des liens (boîte à moustache et courbe de Lorenz sur l’intensité des flux).

En ce qui concerne la sélection, trois familles de méthode sont implémentées :

  • flux dominants classiques ;
  • critères locaux (pour chaque sommet, garder les flux obéissant à tel critère) ;
  • critères globaux (considérant l’ensemble des flux, garder ceux obéissant à tel critère).

La fonction compmat permet de comparer deux matrices origine-destination de même dimension, notamment pour connaître la perte d’information consécutive à une sélection.

Enfin, la représentation graphique est limitée aux résultats issus de la méthode des flux dominants dans la mesure où d’autres packages existent pour visualiser des graphes valués ou réaliser des cartes de flux (un package de cartographie développé par le déjà cité Timothée Giraud et son collègue Nicolas Lambert devrait être disponible très prochainement). Elle permet d’obtenir des figures de ce type :

exemplemap

Exceptionnellement, je ne fournis pas de script : je me permets de renvoyer à la vignette qui accompagne le package et qui explique tant les méthodes que l’utilisation des fonctions.

Dernier point : n’hésitez pas à envoyer vos remarques (par mail ou en commentaire), demandes et critiques, pour que nous puissions améliorer ce package.

Combinaisons de graphes avec igraph

Ayant eu récemment à me pencher sur la question délicate des jointures entre réseaux ayant des liens en communs, j’en profite pour faire un point rapide sur les fonctions du package igraph permettant ces combinaisons. Si vous ne connaissez pas ce package, voyez les billets taggés R sur ce blog. Le script utilisé est téléchargeable sur github ici-même. et, pour les personnes qui n’ont pas envie et/ou besoin de s’inscrire sur ce git, il est reproduit à la fin de ce billet.

Soit les deux graphes suivants :

g1g2

g1 et g2 sont deux graphes non orientés et ont trois sommets (ACD) et deux liens en commun (pléonasme…). Toutes les fonctions commentées ici prennent des graphes de même type en entrée (orientés ou non), certaines autorisent les combinaisons de graphes différents (un orienté et un non orienté).

La première étape du script consiste à créer des attributs pour g1 et g2 : attributs du réseau, des sommets et des liens. L’objectif est de contrôler la perte éventuelle d’attributs lors des opérations effectuées. Pour mémoire, pour un graphe nommé g, la syntaxe de igraph est la suivante :

g$densite <- graph.density(g) #attribut du graphe
V(g)$degre <- degree(g) #attribut des sommets (V comme vertex)
E(g)$betw <- edge.betweenness(g) #attributs des liens (E comme edges)

La fonction graph.complementer prend un graphe en attribut et crée son complémentaire : les liens absents dans le graphe de départ sont créés, les liens présents dans le graphe de départ sont supprimés. Un paramètre booléen loops permet de décider si on souhaite ou non générer des boucles (par défaut, loops = FALSE). Les attributs du réseau et des sommets sont conservés, les attributs des liens sont perdus (ce qui semble cohérent, ces liens étant supprimés).

La fonction graph.difference prend deux graphes en entrée : seuls les liens présents dans le premier réseau et non dans le deuxième sont conservés, tous les attributs du premier réseau sont gardés. On peut également utiliser l’opérateur %m% (comme minus) : écrire graph.difference(g1,g2) ou g1%m%g2 est donc équivalent. La figure ci-dessous permet de comparer les résultats obtenus : le lien AD présent dans g1 et g2 donc les opérations g1-g2 et g2-g1 entraînent sa disparition.

graph_difference

La fonction (non utilisée dans le script) graph.disjoint.union permet de joindre deux graphes dont les sommets sont distincts.

La fonction graph.intersection (ou %s%) prend deux graphes en entrée et un paramètre keep.all.vertices (TRUE par défaut) permet de choisir entre garder l’ensemble des sommets et les seuls sommets connectés dans le graphe produit. Les attributs sont tous conservés. Enfin, la fonction graph.union prend deux graphes en entrée : tout lien présent dans un moins un graphe
sera dans le graphe produit – sans création de liens multiples – et tous les attributs seront conservés.

Script complet

library(igraph)

#création des deux graphes
d1 <- rbind(c(« A », »B »),c(« A », »C »), c(« B », »C »), c(« A », »D »), c(« D », »E »))
d2 <- rbind(c(« A », »F »), c(« A », »D »), c(« A », »C »), c(« C », »I »))

g1 <- graph.data.frame(d1, directed = FALSE)
g2 <- graph.data.frame(d2, directed = FALSE)

#visualisation
par(mfrow = c(1,2))
plot(g1, main = « g1 »)
plot(g2, main = « g2 »)
dev.off()

#3 points communs (ACD) et deux liens communs (AD et AC)

#ajout d’attributs : degré des sommets
V(g1)$degree <-  degree(g1)
V(g2)$degree <- degree(g2)

#ajout d’attributs aux liens (intermédiarité)
E(g1)$between <- edge.betweenness(g1)
E(g2)$between <- edge.betweenness(g2)

#ajout d’attributs au réseau : densité
g1$densite <- graph.density(g1)
g2$densite <- graph.density(g2)

#fonction graph.complementer
#crée un graphe avec les liens absents du graphe de départ
#les liens présents au départ sont eux supprimés
compg1 <- graph.complementer(g1, loops = FALSE)
plot(compg1)
#les attributs des sommets et du graphe sont conservés
#attributs des liens sont perdus
V(compg1)$degree
compg1

#fonction graph.difference premier réseau – deuxième réseau (opérateur %m%)
#seuls les liens présents dans le premier réseau et non dans le deuxième sont conservés
#tous les attributs du premier réseau sont gardés
diffg1 <- graph.difference(g1, g2)
diffg1

diffg2 <- graph.difference(g2, g1)

#coordonnées (quasi) identiques pour faciliter la comparaison
lay <- layout.fruchterman.reingold(g1)

#lien A-D présent dans g1 et g2 donc g1-g2 et g2-g1 entrainent sa disparition
par(mfrow = c(2,2))
plot(g1, main = « g1 », layout = lay, vertex.color = « red », vertex.size = 20, vertex.label.dist =3)
plot(g2, main = « g2 », layout = lay, vertex.color = « red », vertex.size = 20, vertex.label.dist =3)
plot(diffg1, main = « graph.difference(g1, g2) », layout = lay, vertex.color = « red », vertex.size = 20, vertex.label.dist =3)
plot(diffg2, main = « graph.difference(g2, g1) », layout = lay, vertex.color = « red », vertex.size = 20, vertex.label.dist =3)
dev.off()

#calculer degré actualisé
V(diffg1)$degree2 <- degree(diffg1)
V(diffg1)$degree
V(diffg1)$degree2

#graph.disjoint.union pour joindre des graphes dont les sommets différents (opérateur %du%)

#liens communs à deux graphes : conserve les attributs
#tous les sommets sont conservés (opérateur %s%)
interg1 <- graph.intersection(g1,g2, keep.all.vertices = TRUE)

#seuls sommets adjacents aux liens communs sont gardés (ici ACD)
interg2 <- graph.intersection(g1,g2, keep.all.vertices = FALSE)

par(mfrow = c(1,2))
plot(interg1, sub = « graph.intersection(g1,g2,\nkeep.all.vertices = TRUE) »)
plot(interg2, sub = « graph.intersection(g1,g2,\nkeep.all.vertices = FALSE) »)
dev.off()

#union de graphes : tout lien présent dans un moins un graphe
#est dans le graphe produit – tous les attributs sont conservés
#ne crée pas de liens multiples

uniong <- graph.union(g1,g2) #opérateur %u%

Analyse (et visualisation) de réseaux avec NetworkX – 1

NetworkX est un module python dédié à l’analyse de réseaux. Déconseillé comme outil d’apprentissage, il pourrait s’avérer utile pour des personnes plus expertes, notamment pour l’analyse des réseaux bipartis où le choix reste limité (y compris dans R, le package bipartite n’intégrant guère de mesures récentes). Avant de découvrir NetworkX, il est indispensable de savoir utiliser Python (écriture et exécution d’un script .py). Il exige des centaines de ressources en ligne sur le sujet et je n’ai pas les compétences permettant d’en recommander une en particulier. Mais j’insiste : soit vous cherchez des mesures non existantes ailleurs (ex. plus courts chemins dans des graphes bipartis), vous avez des notions en programmation et l’investissement peut être rentable ; soit vous vous en sortez très bien avec vos logiciels préférés et, à moins d’animer un blog sur l’analyse de réseaux, l’investissement n’est peut-être pas tout à fait nécessaire… Je précise pour finir que je suis encore très loin de maîtriser l’outil (je n’arrive par exemple pas encore à importer des attributs pour les sommets) et que ce billet est très perfectible. Les phrases suivies d’un * sont à considérer comme de possibles erreurs de ma part…

Comment ça marche ?

Le principe est simple : écrire un script python utilisant les commandes du module NetworkX et l’exécuter. Le graphe analysé peut être créé à l’intérieur même du script ou généré à partir d’une liste de liens, et l’importation de fichiers d’autres formats sont également possibles (GEXF, GraphML, Pajek, JSON etc. voir la liste complète ici). Les résultats et les sorties graphiques peuvent être exportés pour être utilisés dans un environnement logiciel autre (format image ou vectoriel).

Comme souvent, il est possible de générer directement son réseau (sommets, liens et attributs éventuels pour les deux) dans NetworkX. Et comme presque toujours, cette option (longuement développé dans tous les tutoriels disponibles) n’a à peu près aucun intérêt dans la mesure où nos données sont déjà existantes dans un format quelconque… Je vais prendre ici le cas le plus simple – ou en tout cas, l’un des plus répandus – dans la mesure où les données sont sous la forme d’une liste de liens possédant un attribut (intensité). Représenter un sommet isolé oblige à créer une boucle.  NetworkX permet également de lire des fichiers structurés sous la forme :

a b c

b d e  etc. où le premier sommet est l’origine du lien et les sommets suivants ses voisins (fonction networkx.read_adjlist).

J’ai utilisé un format .txt et des espaces comme séparateurs pour créer un fichier liens.txt. Les attributs doivent être indiqués entre accolades. S’il n’y a pas d’attribut pour les liens, n’importe quel séparateur semble utilisable (j’ai testé avec des virgules et des points-virgules) ; par contre, s’il y a un attribut, l’espace semble être le séparateur à utiliser*. Le nom des attributs est entre apostrophes, suivi de :, puis de la valeur. S’il y a plusieurs attributs, les séparer par une virgule comme dans l’exemple ci-dessous.

a b {'weight':2, 'color':'green'}
a c {'weight':3, 'color':'green'}

Par défaut, NetworkX considère que le graphe est non orienté. Le script suivant permet d’importer le fichier, de le visualiser, d’effectuer des mesures standards, de le rendre non-orienté puis d’effectuer une nouvelle série de mesures. Le script et le fichier des liens sont téléchargeables sur github à l’adresse https://github.com/beauguitte/NetworkX_1. Je le reproduis in extenso pour les personnes ne souhaitant pas s’inscrire sur le git en question…

Exemple type

# coding: utf8
import networkx as nx
import matplotlib.pyplot as plt #pour la visualisation

#lecture d'une liste de liens
G=nx.read_edgelist("liens.txt", create_using=nx.DiGraph())

#visualisation
pos=nx.spring_layout(G)               #choix de l'algorithme
nx.draw(G, pos, with_labels=True)
plt.show()
#plt.savefig("edge_colormap.png")     #export dans un format donné

Ce qui donne à peu près ça.

plot_ networkx

#analyse
print "number of nodes : %s" % G.number_of_nodes()
print "number of edges : %s" % G.number_of_edges()
print G.in_degree()
print G.out_degree()

#passage en graphe non orienté
G=G.to_undirected()

print "degree of node a : %s" % G.degree("a") #sommet spécifique
print "degree (undirected) %s" % G.degree()   #ensemble des sommets
print "betweenness centrality %s" % nx.betweenness_centrality(G)
print "degree (normalized) %s" % nx.degree_centrality(G)

#transformer les mesures en attributs
deg = G.degree()
nx.set_node_attributes(G, 'degree', deg)

#visualisation
pos=nx.spring_layout(G)
nx.draw(G, pos, with_labels=True)
plt.show()

#recherche des cliques
cl = list(nx.find_cliques(G))
print "cliques %s" % cl

#plus courts chemins
pathlengths=[]

print("source vertex {target:length, }")
for v in G.nodes():
   spl=nx.single_source_shortest_path_length(G,v)
    print('%s %s' % (v,spl))
    for p in spl.values():
        pathlengths.append(p)
print('')
print("moyenne des plus court chemins %s" % (sum(pathlengths)/len(pathlengths)))

#distribution des plus courts chemins
dist={}
for p in pathlengths:
    if p in dist:
        dist[p]+=1
    else:
        dist[p]=1

print('')
print("length #paths")

print("densité : %s" % nx.density(G))
print("diamètre: %d" % nx.diameter(G))
print("eccentricity: %s" % nx.eccentricity(G))
print("centre : %s" % nx.center(G))
print("péripherie : %s" % nx.periphery(G))

En attendant la suite…

Sur le papier, NetworkX est plutôt séduisant pour l’analyse des graphes bipartites et/ou valués. En pratique, le coût d’entrée pour un programmateur peu avancé est assez élevé. Je compte m’acharner dessus dans les semaines à venir et proposer un billet un peu moins approximatif que celui-ci aussi vite que mes capacités d’apprentissage le permettront.

Et pour aller plus loin

Site : https://networkx.github.ioe/

La documentation disponible en ligne est exclusivement en anglais : voir par exemple la très bonne présentation de Derek Greene à cette adresse : http://mlg.ucd.ie/files/summer/tutorial.pdf

Séances ElementR sur les flux avec R

C’est un peu comme un cross-over entre deux séries que Wikipédia(c) définit aussi ici d’incursion, pour caractériser « […] une production qui regroupe des personnages dont les aventures se déroulent habituellement dans des séries différentes. »

On souhaite en effet signaler la présentation de programmes R proposée par ElementR, qui portent sur  des thèmes proches de ceux qui sont habituellement traités par le groupe fmr, en particulier :

– la session n°3 qui porte sur l’analyse de flux et modèles gravitaires, ici

– la session n°5 sur la cartographie de flux, ici 

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