Groupe fmr – séance du 21 février 2017

Paul Gourdon, doctorant à Géographie-cités, présentera ses travaux. Sa présentation s’intitule : « Construire un panorama de la coopération transnationale entre villes européennes »

Voici un court texte de présentation.

Réseaux de villes, associations de municipalités, city-to-city cooperation (Buis 2009), diplomatie des villes (Viltard 2010), Transnational Municipal Networks (Bulkeley et al. 2003; Keiner et Kim 2007) ; les termes ne manquent pas pour décrire et promouvoir la coopération et l’échange d’informations entre collectivités locales (Campbell 2013; Barber 2015). Pourtant, les liens troubles entre domaines de l’action politique, marketing territorial et champs académiques n’assurent pas un contenu théorique solide et unifié sur lequel s’appuyer. L’objectif de cette présentation est de questionner les approches géographiques de la coopération territoriale (Bussi 2009; Escach 2014) et de préciser l’appareillage conceptuel et méthodologique utilisé pour rendre compte de ces « réseaux de villes » qui ont, a priori, peu à voir avec les réseaux (études des flux) tels qu’ils sont mobilisés dans le cadre théorique des systèmes de villes (Pumain 1995; Cattan 1999). Ici, le sens politique du mot « réseau » nous interpelle : les associations transnationales de municipalités peuvent-elles être traitées comme des réseaux sociaux (Degenne and Forsé 2004; Wasserman and Faust 1997; Lazega 2013) ?

Construire un panorama de la coopération transnationale entre les villes européennes permet de s’interroger sur les spécificités de l’espace européen comme espace de coopération (Ewen et Hebbert 2007) et d’envisager sous un autre angle les transformations contemporaines (décrites par la science politique) qui font des municipalités des acteurs de premier plan (Brenner 2004; Le Galès 2011). Il s’agira de voir quels peuvent être les apports d’un travail à l’échelle d’une Europe aux contours flous et d’une mobilisation de la théorie des graphes pour appréhender un champ de recherche qui s’est construit principalement sur l’articulation de monographies (Barbier 2015).

Prochaines séances

21 février : présentation et discussion des travaux de Paul Gourdon, doctorant à Géographie-cités
21 mars : QGis pour l’analyse et la représentation de matrice de flux par Françoise Bahoken
25 avril : présentation et discussion des travaux de Mattia Bunel, Ingénieur d’étude ERC WorldSeastems/ UMR Géographie-cités
23 mai : R pour l’analyse de réseaux par Serge Lhomme et 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.

10 janvier 2017 : Analyse de graphe avec QGis

La prochaine séance du groupe fmr aura lieu le mardi 10 janvier 2017 à 10h, au 13 rue du four, 5e étage, bibliothèque, Paris. Elle portera sur l’analyse de graphes planaires (mais pas seulement) avec QGIS,
Séance animée par Ryma Hachi et Serge Lhomme.

Cette séance sera décomposée en deux parties : une première partie présentera l’extension nommée « Network_analysis » (http://serge.lhomme.pagesperso-orange.fr/dev.html) ; une deuxième partie sera consacrée à l’extension « Spatial Design Network Analysis » (sDNA) (http://www.cardiff.ac.uk/sdna/).
Dans les deux cas, il faudra bien entendu vous munir d’une version de QGIS (http://www.qgis.org/fr/site/forusers/download.html). A titre d’information, la version 2.14 est parfaitement adaptée.

Pour la partie consacrée à l’extension « Network_analysis », il faudra télécharger le dossier zippé suivant : http://serge.lhomme.pagesperso-orange.fr/data/network_analysis_1_2.zip. Attention, si votre version de QGIS est un peu datée (inférieure à la version2.4), veuillez aussi télécharger ce dossier : http://serge.lhomme.pagesperso-orange.fr/data/network_analysis_1_1.zip. Pour l’installation de cette extension, c’est simple et rapide, elle pourra donc être effectuée juste avant le début de la séance (à 9h45). Les données de cette partie sont téléchargeables en suivant ce lien : https://faust.u-pec.fr/get?k=2slxm3mKYoxMmJY6L1WCette première partie permettra d’aborder les questionnements liés à la différenciation entre effets réseaux et effets spatiaux, de tester les propriétés scale-free d’un graphe, de générer et de « simplifier » des graphes spatialisés (planaires ou non planaires) à partir de données diverses.

La deuxième partie permettra d’aborder plus particulièrement le cas des réseaux intra-urbains (le réseau de rues en l’occurrence), avec la présentation de l’extension sDNA, particulièrement adaptée aux données type OpenStreetMap.
Sur cette page : http://www.cardiff.ac.uk/sdna/software/download/ vous pourrez demander un numéro de série (gratuit), puis télécharger l’extension. Il n’existe pas de version Mac, et il faut a minima QGIS 2.8.
Une fois l’extension téléchargée, son installation est relativement simple (elle pourra également être effectuée juste avant la séance).
L’extension sDNA requiert des données au format SIG (shapefile). Nous ferons un test sur le réseau de rues de Paris au XIXe siècle (données téléchargeables ici : https://filex.univ-paris1.fr/get?k=nsOl3HqSpK0ydOmKjDr). Nous verrons comment préparer le réseau, calculer des indicateurs (de centralité…), puis nous discuterons les résultats.

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

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.

 

 

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

 

 

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

Réseaux virtuels, réseaux éphémères – 4e Journée d’études du groupe fmr – ANNULÉE

Faute d’un nombre suffisant de propositions, la 4e journée d’études du groupe fmr est annulée.

Réseaux virtuels, réseaux éphémères

Appel à communications

Les qualificatifs de « virtuels » et d’« éphémères » s’appliquent à des objets dont l’existence actuelle, c’est-à-dire en acte, est respectivement immatérielle, éventuelle et temporaire. Les réseaux sociaux reconstitués à partir des informations issues de Facebook ou de Twitter peuvent ainsi avoir l’une et/ou l’autre de ces deux propriétés. Plus globalement, internet a démultiplié les possibilités d’analyse de ces groupes, sous la forme d’objets réticulaires, dont la réalité et la pérennité des relations ne sont pas assurées. Souvent jugé caractéristique de notre époque, ce phénomène ne laisse pas indifférent les chercheurs en sciences sociales : les plus géographes d’entre eux se posent d’ailleurs la question de l’inscription spatio-temporelle des réseaux identifiables sur internet. On peut penser, entre autres, aux réseaux virtuels générés par des enjeux politiques, culturels, sportifs ou scientifiques qui peuvent provoquer des rassemblements et des mobilités dans l’espace physique, en lien avec les infrastructures. Si les réseaux virtuels et/ou éphémères semblent se distinguer a priori des réseaux dits « techniques » ou « spatiaux », leur ancrage physique détermine d’une certaine façon leur existence et leur évolution.

Face à ce type d’objets, nous rencontrons des problèmes méthodologiques inédits. Aussi, c’est souvent en s’intéressant à la nature et à la temporalité (la fréquence ou la durée) des interactions qui le composent que le caractère éphémère d’un réseau, virtuel ou non, peut être défini. Les notions de proximité temporaire sont d’ailleurs intéressantes à envisager à cet égard, et opérantes tant dans le champ des mobilités humaines spatialisées que de celui de l’action collective. En fait, ce peut être les liens, les éléments en relation, ou encore l’articulation des deux notions qui peuvent être virtuels et/ou éphémères.

Une fois l’objet défini, il reste à voir dans quelle mesure ce dernier résiste aux méthodes traditionnelles de l’analyse de réseau. En particulier, comment extraire un graphe à partir d’un phénomène virtuel et/ou éphémère, et comment l’analyser ? Quels sont les sources d’information, les « traces » ou les « marqueurs » relationnels que l’on peut exploiter et dans quelles conditions ? Comment relever les défis associés à la visualisation, l’exploration et la modélisation d’un tel réseau ? Enfin, dans la mesure où l’on aurait affaire à un réseau à la fois virtuel et éphémère, est-il possible de faire un lien entre ces deux propriétés ?

L’objectif de cette journée est de rassembler différents points de vue sur la manière d’appréhender des réseaux considérés comme « virtuels » et/ou « éphémères ». Il s’agira moins de proposer des réponses définitives que d’ouvrir des pistes de réflexion, afin d’enrichir la compréhension des réseaux étudiés et d’identifier d’éventuels transferts de méthode. Pour cela, la journée privilégiera les analyses concrètes, réalisées sur un corpus empirique. Elle n’impose aucune limite disciplinaire.

Modalités de soumission

Les propositions de communication seront évaluées par le comité scientifique.

En cas d’acceptation du résumé, un texte long (de 10 à 12 pages) est impérativement attendu pour le 30 juin 2015.

L’ensemble des textes sera édité dans la collection Hal-Shs du groupe fmr. Des consignes précises de mise en forme seront envoyées aux auteur-e-s retenu-e-s.

Valorisation

Une sélection d’articles fera l’objet d’une publication dans la revue Netcom, Réseaux, Communication et Territoires (http://www.netcom-journal.com/)

Nous encourageons vivement les doctorant-e-s et jeunes docteur-e-s à participer à cette journée.

Consignes pour le résumé

Indiquer précisément titre, mots-clés (3 à 5), nom, prénom, affiliation et mails du ou des auteur-e-s.

Étant donné le format demandé, trois à quatre références bibliographiques nous semblent un nombre suffisant.

Dates importantes

  • 30 mars : envoi des propositions (1 page maximum) à groupe_fmr@yahoo.fr

  • 15 avril : notification aux auteur-e-s

  • 30 juin : envoi des textes complets (10 à 12 pages)

  • 15 Septembre: date limite d’inscription

  • 17 septembre : date de la journée

  • Courant octobre : édition des actes de la journée d’étude

Lieu : la journée aura lieu à l’Institut des Systèmes Complexes (ISC) de Paris, situé au 113, Rue Nationale, 75013 Paris. http://www.iscpif.fr/

Comité scientifique et d’organisation

Françoise Bahoken, Laurent Beauguitte, César Ducruet, Serge Lhomme, Marion Maisonobe

Télécharger l’appel en pdf.

ENSAI TD 3 – Analyser et visualiser les réseaux avec Cytoscape et Gephi

Gephi et Cytoscape sont deux logiciels open-source et gratuits adaptés à la visualisation de grands graphes. Leurs capacités d’analyse (surtout pour Gephi) sont par contre relativement limitées.

Déroulement du TD

Prise en main de Gephi (version 0.8.2 beta)

Présentation de l’interface : un menu principal, trois fenêtres distinctes (vue d’ensemble, laboratoire de données, prévisualisation) et une vue d’ensemble en 3 colonnes (nœuds, liens et spatialisation ; graphe ; statistiques et filtre)

Options de visualisation – jeu de données Les Miserables.gexf : naviguer dans le graphe (clic droit, molette) ; sélectionner un sommet ; afficher les labels et les faire varier (police, mise en forme, taille).

Mesurer et filtrer : calculer le degré et le degré pondéré, calculer la modularité. La taille des sommets sera fonction du degré pondéré, leur couleur de la classe (modularité) et l’épaisseur des liens variera selon l’intensité du lien. Faire varier les paramètres proposés (couleur, taille, étendue). Sélectionner uniquement les sommets de degré supérieur ou égal à 3 (fenêtre filtre sur la droite).

Préparer l’exportation des résultats (données et image)

Importer ses propres données (reprendre le mini-graphe du TD1) : créer un projet puis aller dans le laboratoire de données, importer les fichiers liens et sommets (format .csv) en cliquant successivement sur Nœuds/Liens et Importer une feuille de calcul. Les noms de colonnes doivent être Source;Target;Weight (optionnel) pour le fichier des liens ; Id-attribut1-attribut2 etc. pour le fichier des sommets. Gephi propose par défaut un typage des variables qu’il peut être nécessaire de modifier.

import_gephi1

Prise en main de Cytoscape

Présentation de l’interface : un menu principal, un volet à droite sur les propriétés, une fenêtre de visualisation et un volet en bas sur les fichiers chargés

Options de visualisation – jeu de données Escherichia coli : naviguer dans le graphe ; sélectionner un sommet ; faire varier les spatialisations et les styles.

Mesurer et filtrer :  Tools > NetworkAnalyser > Network Analysis > Analyse Network. Pour les intégrer à la visualisation, Tools > NetworkAnalyser > Network Analysis > Generate Styles from Parameters… La taille des sommets sera fonction du degré, leur couleur de la proximité (closeness) et l’épaisseur des liens variera selon l’intermédiarité. Extraire les composantes connexes. Sélectionner les sommets de degré supérieur ou égal à 2 et créer le graphe correspondant (onglet Select puis File > New network > From selected nodes…).

Préparer l’exportation des résultats (données et image)

cyto3

Format des données (reprendre le mini-graphe du TD1) : pour le point g, le plus simple est de créer un lien fictif g-g dans le fichier .csv de départ puis de supprimer les boucles après l’importation (Edit > Remote Self-Loops). Pour l’importation des liens, Ctrl + L puis afficher les options de tabulation, la présence ou non de noms de colonnes, l’origine, la destination et le type d’interactions (par défaut pp – protein-protein). Puis importer le fichier des attributs (File > Import > Table > File) et faire la jointure entre les deux fichiers.

cyto1

ENSAI Cours 5 – Traitements et modélisations statistiques

Avertissement devenant rituel : je ne sais pas (pas encore) rédiger correctement mes cours. Il s’agit donc plus ici de notes de cours grossièrement mises en forme que d’un cours en ligne à proprement parler. Le .zip téléchargeable ici contient le script R commenté et le jeu de données utilisé pour ce cours.

Introduction

L’un des grands défauts de la majorité des mesures en analyse de réseau (quelle que soit la discipline) est leur côté exclusivement descriptif. Or la volonté de modéliser statistiquement les réseaux observés est ancienne (Moreno et Jennings, 1938 ; Rapoport, 1953). Depuis les années 80, plusieurs modèles ont été proposés, chacun tentant de dépasser les limites de ses prédécesseurs (cf Beauguitte, 2012). Une première partie liste les traitements bivariés et multivariés fréquemment utilisés, la deuxième partie s’intéresse aux modèles ERGM et la dernière au modèle SIENA. Comme toujours avec les modèles statistiques, leur utilisation suppose des hypothèses a priori que le modèle permettra d’infirmer ou de valider.

1 Traitements statistiques bi et multivariés

Un traitement statistique possible est de tester les relations entre une propriété et une autre (le degré entrant est-il corrélé au degré sortant ?). Étudier la distribution d’une propriété des sommets (ex. degré) et chercher à trouver la fonction résumant cette distribution est également une des possibilités (souvent exploitée) offerte (cf cours 4). Dans la mesure où de très nombreuses mesures sont disponibles, il est logique que les analyses multivariées type analyses en composantes principales soient utilisées depuis des décennies pour créer des classes homogènes de sommets (cf l’article de Muraco, cours 3).

2 Le modèle ERGM (Exponential random graph model)

Pour savoir si le graphe étudié est significativement différent d’un graphe aléatoire, une première approche est de générer x graphes aléatoires de même taille et densité et de comparer les structures obtenues dans le graphe observé et dans les graphes aléatoires. La méthode est pertinente mais présente un inconvénient majeur : il faut tester les structures les unes après les autres sans prendre en compte les interdépendances entre ces configurations. Le modèle ERGM permet de pallier à cet inconvénient et peut s’appliquer à réseau orienté ou non, booléen, one-mode ou two-mode, simple ou multiple. Il présente un défaut majeur : les algorithmes utilisés sont exigeants et ce modèle s’applique mal aux grands réseaux.

2.1 Principes

Le modèle ERGM repose sur un pré-supposé théorique fort : la structure d’ensemble d’un réseau peut s’expliquer par l’accumulation de micro-structures locales (dyades et triades) et les mécanismes de formation de liens à l’intérieur de ces micro-structures. Ces micro-structures sont appelés local network patterns ou network configurations et donnent les paramètres du modèle. Il s’agira donc de choisir, en fonction d’hypothèses précises, quels sont les paramètres à introduire dans le modèle. Par exemple, si la transitivité est supposée élevée (réseau personnel d’amitié), le nombre de triangles doit être inclus dans le modèle. Les résultats du modèle permettent de savoir si tel ou tel paramètre est significativement plus présent dans le réseau observé qu’attendu. On différencie les variables endogènes et les variables exogènes : une variable exogène peut affecter la présence d’un lien dans le réseau mais l’inverse n’est pas vrai (ex. la variable genre peut expliquer la présence de liens mais la présence de liens n’affecte pas le genre).

La figure ci-dessous présente diverses configurations locales – cette liste est loin d’être exhaustive – pouvant être observées dans un réseau orienté et non orienté.

configuration

Si on lie ces configurations avec des hypothèses liées au réseau étudié, on peut obtenir des configurations de ce type.

ergm

La différence majeure avec les modèles type régression logistique est qu’ici les observations (i.e. les liens) ne sont pas supposées indépendantes.

2.2 Déroulement

Les étapes pour mener à bien un modèle ERGM sont les suivantes :

  • formuler des hypothèses claires et les relier à des configurations spécifiques (activité et degré sortant ; popularité et degré entrant ; transivité des relations et nombre de triangles ; homophilie et variable attributaire potentiellement explicative etc.)
  • identifier les variables pertinentes (endogènes et exogènes)
  • construire le modèle
  • estimer les paramètres les plus probables ayant donné lieu à cette configuration (maximum de vraisemblance) et les interpréter (significativité, écart-type). Le paramètre estimé doit être supérieur au double de la valeur absolue de l’écart-type pour être significatif (idem dans le modèle SIENA).
  • évaluer la qualité d’ajustement du modèle (goodness of fit). Une fois le modèle ajusté, on simule des réseaux suivant ce modèle pour voir si d’autres paramètres (non-fitted) sont centraux ou périphériques dans la distribution. L’idée de base est la suivante : est-ce que des paramètres non inclus sont capturés correctement par le modèle ? Les t-ratios doivent être inférieurs à |0.1|. S’ils sont supérieurs à |2|, ils signalent des effets non pris en compte par le modèle.

L’objectif est de construire le modèle le plus économe et le plus explicatif possible. L’étape la plus importante est bien entendu le choix des paramètres puis l’interprétation des résultats. Pour un graphe non orienté, un bon point de départ est de prendre en compte la densité, le degré et les triangles. Pour un graphe orienté, on différenciera degré entrant et sortant.

2.3 L’exemple des relations sexuelles dans la série Grey’s anatomy (d’après Benjamin, 2012)

Le jeu de données utilisé (grey.RData) liste les relations sexuelles entre personnages de la série Grey’s anatomy. Visualiser le graphe en colorant les sommets selon le genre montre une tendance très nette à l’hétérosexualité.

Screenshot - 23012015 - 15:43:07

Le modèle utilisant le nombre de liens et le genre donne de bons résultats en ce qui concerne la densité et la tendance à l’hétérosexualité. Par contre, le modèle prévoit un nombre non négligeable de sommets ayant un degré à zéro. Sur la figure ci-dessous, les box-plots montrent les propriétés des graphes simulés et le trait noir celles du graphe observé. La différence concernant les sommets de degré 0 apparaît clairement. En clair, les graphes simulés basés sur ces propriétés entraînent une proportion non négligeable d’abstinent-e-s.

gof

Le script commenté détaille les différentes étapes et l’interprétation des résultats. Il faut cependant noter que le package ergm n’est pas le plus simple à utiliser (nombre élevé de paramètres et d’options).

3 Le modèle SIENA (Simulation Investigation for Empirical Network Analysis)

Le modèle SIENA est grosso modo l’équivalent du modèle ERGM mais appliqué à des graphes longitudinaux : la population d’acteurs est supposée stable (ce qui est une des grandes limites du modèle) et les relations dans cette population sont mesurées à plusieurs reprises. Développé par Tom Snijders, le modèle cherche à expliquer l’apparition et la disparition de liens en incluant des variables structurales et des variables attributaires. L’article de Federico de la Rua (2004) fournit une excellente introduction à ce modèle et ce qui suit n’est qu’un résumé succinct de cet article. De nombreux développements ont par ailleurs été faits depuis 2004 (réseau 2-mode, multigraphe, gestion des données manquantes etc.).

3.1 Principes

L’objectif de la modélisation est d’expliquer la présence et l’évolution des liens au sein d’une population. Comme pour tous les modèles, cela suppose de formuler des hypothèses au préalable. Il est nécessaire d’avoir le réseau complet à au moins deux moments t et t+1. La variable dépendante analysée est le changement de relations dans le réseau représenté par deux (ou plus) graphes orientés parmi un nombre fixe d’acteurs. Au niveau théorique, le modèle repose sur la théorie de l’action orientée par un but (purposive action) et postule que les acteurs réalisent des choix (établissement, maintien, suppression des liens) pour maximiser leur utilité, ce qui détermine la structure ultérieure du réseau. L’état du réseau à un moment donné conditionne les états postérieurs de celui-ci (d’où l’utilisation de chaînes de Markov). Il n’y a donc pas de mémoire des individus (seul t est pris en compte pour déterminer t+1), ni de stratégie à long terme (supprimer une relation à t+1 pour pouvoir en créer une à t+n).

D’autres postulats sont posés  :

  • les acteurs agissent de façon indépendante, non coordonnée ;
  • les acteurs ont une connaissance totale des agencements des liens actuels dans le réseau (ce postulat est d’ailleurs implicite chaque fois qu’on mesure des plus courts chemins dans un réseau – proximité, diamètre – ou des mesures mobilisant les plus courts chemins comme l’intermédiarité) ;
  • les changements ont lieu un après l’autre et que tous les acteurs ont la même probabilité de réaliser un changement.

Ces différents postulats sont liés à des limitations techniques (réduire le nombre de paramètres à ajuster) mais sont très discutables au niveau théorique.

3.2 Déroulement

Construire un modèle SIENA suppose les étapes suivantes :

  • formuler des hypothèses et les relier à des configurations spécifiques ;
  • tester le modèle ;
  • étudier les paramètres et leurs écart-types : on considère un paramètre comme significatif quand sa valeur est au moins le double de son écart-type.

Il est conseillé de toujours inclure dans le modèle la densité, car c’est un effet de contrôle pour tous les autres.

3.3 Exemple d’application

Voir les scripts disponibles sur la page personnelle de Tom Snijders (http://www.stats.ox.ac.uk/~snijders/siena/)

Conclusion

Longtemps peu maniables, les modèles statistiques d’analyse de réseaux font désormais partie des pratiques courantes en analyse des réseaux sociaux (manuel de référence publié en 2013 par Lusher et al., logiciels dédiés, nombreux articles utilisant ces méthodes etc.). Ces modèles restent cependant peu adaptés aux grands graphes et peuvent parfois être délicats à paramétrer.

Références

L. Beauguitte, 2012, Analyse de graphe et modèles statistiques. Du modèle p1 à l’ERGM, collection fmr
Benjamin, 2012, Lessons on exponential random graph modeling from greys anatomy hooks-up, http://badhessian.org/2012/09/
A. de Federico de la Rua, 2004, L’analyse longitudinale de réseaux sociaux totaux avec Siena, Bulletin de méthodologie sociologique, (84):5–39.
D. Lusher, J. Koskinen et G. Robins, 2013, Exponential Random Graph Model for Social Networks, Cambridge University Press
J.L. Moreno et H.H. Jennings, 1938, Statistics of social configurations. Sociometry, 342-374
A. Rapoport, 1953, Spread of information through a population with socio-structural bias: II. Various models with partial transitivity, The bulletin of mathematical biophysics, 15(4):535-546

ENSAI Cours 6 – Représentations des réseaux

Avertissement devenant rituel : je ne sais pas (pas encore) rédiger correctement mes cours. Il s’agit donc plus ici de notes de cours grossièrement mises en forme que d’un cours en ligne à proprement parler. Ces notes seront utilement complétées par le visionnage de la présentation téléchargeable ici.

Introduction

L’analyse de réseau est basée sur la théorie des graphes et du calcul matriciel et n’impose a priori pas de représentation graphique spécifique. Pourtant, très tôt (cf Moreno, 1934), l’habitude a été prise de montrer graphiquement la structure du réseau étudié (Bahoken et al., 2013). La représentation graphique de données quantitatives suppose le respect d’un certain de règles visant à favoriser la lisibilité de la figure produite (partie 1). En fonction de la nature des données disponibles et de l’objectif de la représentation, il est possible de choisir entre représentation matricielle, représentation de graphe et cartographie de flux (partie 2). La représentation des grands réseaux peut poser des problèmes et nécessiter le recours à d’autres formes de représentation et des approches mixtes sont également possibles (partie 3).

1 Notions de sémiologie graphique

L’objectif de la sémiologie graphique, dont le créateur français est Jacques Bertin (1963), est d’établir un certain nombre de règles visant à favoriser la lecture et l’interprétation correcte des graphiques produits, qu’il s’agisse de diagrammes, de cartes, de réseaux etc. Il faut noter que si un courant anglophone a basé ces règles sur des études empiriques liées à la perception et à la cognition, les règles forgées par Bertin ne sont pas basées sur de telles études… Selon Bertin, seule la variable visuelle taille permet de représenter des données quantitatives portant sur des stocks quand la valeur ou la couleur traduisent des relations quantitatives continues, segmentées en classes. Si la population de mon réseau est divisée en classe d’âge par exemple, il est autorisé d’utiliser des couleurs différentes (éventuellement graduées) pour colorer mes sommets mais la taille ne pourra varier qu’en fonction d’une quantité (le degré par exemple).

Compléter ces règles par les trois principes de l’excellence graphique définis par Tufte (1983) est un bon moyen pour produire des figures lisibles. Ces trois principes sont les suivants : « L’excellence graphique est une présentation bien conçue des données d’intérêt [. . .], [elle] vise à communiquer des idées complexes avec clarté, précision et efficacité ; [elle] est ce qui donne au lecteur le plus grand nombre d’idées dans le temps le plus court, tout en utilisant le moins d’encre sur un minimum d’espace » (Tufte, 1983, p. 51).

Dans le cadre d’une figure destinée à transmettre un message (hors démarche exploratoire donc), il est nécessaire que cette image soit accompagnée d’une légende, tout comme il est recommandé de préciser les outils de visualisation utilisés (logiciel et algorithmes). Il est fréquent de voir des images où les sommets sont de différentes formes, de différentes couleurs, les liens d’épaisseur variable et aucun indice ne permet de savoir ce que représentent ces formes, ces couleurs et ces épaisseurs…

2 Matrice, graphe et carte de flux

Deux formes de représentation sont toujours possibles en analyse de réseau (la matrice et le graphe), une troisième l’est parfois selon les données utilisées (la carte*).

Le fait d’ordonner une matrice, c’est-à-dire de permuter lignes et colonnes pour faire ressortir les structures du réseau étudié, est l’une des moyens les plus efficaces pour visualiser la structure d’ensemble et les relations individuelles dans un réseau. Cette matrice ordonnée peut éventuellement être transformée en matrice bloquée représentant les liens entre les principales parties du réseau (cf cours 2 et le passage sur l’équivalence). Différents tests, menés notamment par l’équipe de Jean-Daniel Fekete, ont montré qu’il était plus rapide de trouver une information précise dans une matrice ordonnée que dans une représentation sous forme de graphe.

Dès les premiers sociogrammes dessinés manuellement par Moreno dans les années 1930, un certain nombre de conventions vont être utilisées pour représenter les graphes ; elles vont ensuite s’imposer et être intégrées dans la plupart des algorithmes existants. Trois grands principes de représentation s’imposent dès le départ : 1) les sommets les plus connectés sont placés au centre de la figure ; 2 ) les sommets les moins connectés sont placés en périphérie de la figure ; 3) il faut limiter, autant que possible, le chevauchement des liens. À noter que Moreno faisait le choix de représenter, sur le même graphe, les phénomènes d’attractions et de répulsions, à l’aide de symboles géométriques (ligne, cercle, triangle) de couleurs noires et rouges 2 . Ce mode de représentation multiplexe n’est plus utilisé aujourd’hui, non pas parce qu’il manque d’efficacité, mais parce qu’il ne semble pas faire partie des possibilités offertes par les logiciels actuels…

Dans les faits, l’ensemble des algorithmes de visualisation pourrait désormais être regroupé en deux grandes familles. La première famille concerne les algorithmes issues de l’analyse de données. La deuxième famille, plus récente, concerne les algorithmes de dessin fondés sur les forces (Force-based ou Force-directed algorithms). Les algorithmes issus de l’analyse de données déterminent la position des nœuds en appliquant un traitement statistique sur la matrice d’adjacence. Cette matrice n’est autre qu’une matrice de similarité (de proximités) ou de covariance (pour les analyses en composantes principales). Les algorithmes développés tentent alors de représenter au mieux cette matrice dans un espace en deux ou trois dimensions. Ainsi les distances observées doivent être aussi proches que possible de celles obtenues à partir de l’algorithme. L’objectif est donc de minimiser une fonction nommée « fonction de stress ». Dans les algorithmes fondés sur la force, les nœuds peuvent être considérés comme des particules de même charge qui se repoussent et les arcs peuvent être assimilés à des ressorts qui tendent à rapprocher les nœuds voisins. Ces algorithmes cherchent alors à minimiser l’énergie du système en déplaçant les nœuds. Il faut noter que le même algorithme testé sur le même jeu de données dans différents logiciels donne parfois des résultats très différents les uns des autres. La pratique la plus commune reste bien souvent de tester différents algorithmes jusqu’à obtenir une image à peu près lisible et interprétable.

La représentation la plus fréquente des réseaux bipartis est d’aligner en haut l’un des groupes, en bas l’autre groupe et de tracer les liens entre les deux. Cette habitude ne limite pas les chevauchements de liens qu’il serait facile d’éviter si ces contraintes – arbitraires – de position n’étaient pas respectées.

La cartographie des flux pose un certain de problèmes qui peuvent limiter la lisibilité de l’information (Bahoken, 2011). Les chevauchements de liens ne peuvent la plupart du temps être évités d’où le fameux effet spaghetti. Les liens longs (France – Nouvelle Zélande) attireront davantage l’œil que les liens courts (France – Belgique), même si les liens courts sont plus intenses, plus épais, de teinte plus foncés etc. Différentes solutions ont été proposées : la plus radicale – mais qui n’est plus permise par les logiciels actuels – est de déplacer les lieux pour faire de la place aux liens (cf les cartes de flux de Minard) ; le filtrage des liens (flux dominants, flux majeurs) ; la modification de la projection ; la transformation des flux en stock (représentation par cercles proportionnels ou anamorphoses des marges de la matrice).

La multiplication des plate-formes de visualisation interactives facilite l’exploration des matrices, des réseaux et des cartes de flux. Mais nous sommes alors dans un cadre exploratoire et non dans un cadre de communication d’un résultat. Laisser à l’utilisateur la liberté de jouer avec les couleurs, les tailles, les représentations etc. est aussi un moyen de ne pas choisir quelle information faire passer via les graphiques.

3 Représentation des réseaux complexes et approches mixtes

Si la représentation de graphe peut être lisible pour quelques dizaines voire quelques centaines de sommets – et encore, si la densité de liens est faible -, il devient illusoire de penser produire une image quand le réseau étudié comporte quelques (centaines de) milliers de sommets. Si des cartes ou des graphes de ce type sont régulièrement produits, l’enjeu est essentiellement technique – et parfois esthétique (cf la devenue fameuse carte mondiale des liens facebook et la lecture critique faite en 3 billets par T. Joliveau sur le blog monde géonumérique). L’idée géniale des physiciens a été d’utiliser d’autres types de graphiques afin de révéler une propriété donnée des réseaux étudiés, par exemple montrer la distribution des degrés et tracer la courbe la résumant pour établir si le réseau est ou non sans échelle.

Il est possible enfin de croiser les approches, et par exemple de mêler matrice pour les parties denses et graphe pour les parties peu denses d’un réseau (cf le logiciel NodeTrix), de produire des matrices en trois dimensions pour introduire la dimension temporelle (logiciel Cubix).

Conclusion

Si la sociométrie a placé le dessin des relations au cœur de son dispositif (cf cours 1), la social network analysis a inversement eu un recours limité à la représentation graphique des relations étudiées et la première décennie de la revue Social networks est d’une étonnante pauvreté graphique (cf cours 2). En géographie, la domination des représentations cartographiques projetées a longtemps été un frein à des visualisations alternatives et parfois plus efficace. Par contre, les études sur les réseaux complexes ont simultanément vu l’apparition de nouveaux modes de représentation et un fort intérêt pour les défis techniques liés à la visualisation. La multiplication des logiciels et la puissance des ordinateurs actuels permettent de réaliser facilement des représentations soignées. Le respect des règles basiques de sémiologie graphique, la réalisation systématique de légende (impossible avec la plupart des logiciels existant) – que représentent les liens ? les épaisseurs ? les sommets ? les couleurs… – pourraient permettre de dépasser l’effet joli image trop souvent rencontré.

Note

* Les spécialistes des web studies et de la visualisation de données (data viz) utilisent très souvent le terme de carte et de cartographie pour désigner la représentation de réseaux. Les nombreuses cartographies du web réalisées ces dernières années sont parfois des cartes, le plus souvent des graphes.

Pour aller plus loin
F. Bahoken, 2011, Représentation graphique des matrices. Graphe et/ou carte des flux ?
F. Bahoken, L. Beauguitte et S. Lhomme, 2013, La visualisation des réseaux. Principes, enjeux et perspectives
J. Bertin, 1967, Sémiologie graphique. Les diagrammes – Les réseaux – Les cartes, Éditions Gauthier-Villar
G. Garrote, 2014, Réseaux : de la notion à l’analyse. Heurs et malheurs d’un outil, http://reshist.hypotheses.org/464
E.R. Tufte, 1983, The Visual Display of Quantitative Information, Graphics Press, Cheschire
Site de l’équipe animée par Jean-Daniel Fekete à l’INRIA : http://www.aviz.fr/