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

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/

R et igraph – revue de détail

Suite du billet consacré à statnet il y a peu ici même.

L’objectif du billet est le même que pour celui signalé une ligne au dessus : importer et effectuer une série de mesures sur le graphe suivant. Téléchargement des fichiers de données et du script commenté ici (encodage en utf-8).
td1plot

Importer ses données

L’importation des données avec igraph est plus simple dans la mesure où les liens et les attributs des sommets peuvent être importés simultanément à l’aide de la commande graph.data.frame – et la gestion des sommets isolés ne pose donc aucun problème particulier. En ce qui concerne les liens, igraph considère que les deux premières colonnes correspondent aux origines et aux destinations, toutes les éventuelles colonnes suivantes seront considérées comme des attributs des liens.

Après transformation, taper le nom de l’objet créé permet d’obtenir à peu près les mêmes informations qu’avec statnet mais sous une forme un peu moins lisible.

library(igraph)

liens <- read.table("liens2.txt", header=TRUE, sep=";")
attributs <- read.table("attributs.txt", header=TRUE, sep=";")

g <- graph.data.frame(liens, vertices = attributs)
g
IGRAPH DN-- 7 8 -- 
+ attr: name (v/c), ANC (v/n), TEAM (v/c), I (e/n)

g est donc un objet igraph de type directed network (DN), comprenant 7 sommets et 8 liens. Il existe 3 attributs pour les sommets (attr v), deux de type character (name et TEAM), un de type numeric (ANC (v/n)) ; un attribut numérique I pour le lien.

Filtrer les données

Sélectionner une partie du graphe en fonction d’un attribut (des sommets et/ou des liens) est d’une grande simplicité une fois comprise la logique de la syntaxe.

Si je souhaite supprimer les liens d’une intensité inférieure à 2

g2 <- delete.edges(g,E(g)[I<2])

soit, si l’on décompose, la fonction delete.edges (nom du graphe, E comme edge (nom du graphe) [ attribut et condition]). Si l’on veut supprimer des sommets, on remplace par delete.vertices et E devient V comme ici où je supprime les sommets de degré inférieur à 2.

g22 <- delete.vertices(g, V(g)[degree(g) < 2])

Si l’on supprime des sommets, les liens adjacents disparaissent également. Si l’on supprime des liens, par défaut, tous les sommets du graphe restent présents.

Mesurer

La recherche de la densité (graph.density) donne – et c’est heureux – le même résultat que statnet, soit 0.19 (8/42).

La recherche des composantes connexes (clusters) renvoie une liste de 3 objets, l’appartenance des sommets (les sommets abcd sont dans la composante connexe numérotée 1), la taille des composantes connexes et leur nombre.

$membership
[1] 1 1 1 1 2 2 3
$csize
[1] 4 2 1
$no
[1] 3

Contrairement à statnet, igraph considère par défaut que la connexité faible est recherchée. Pour la connexité forte, il faudra utiliser l’option mode = « strong ».

La recherche des cliques (fonction cliques) est ici efficace mais, par défaut, igraph fournit toutes les cliques de taille 1, 2 etc. Il est donc conseillé d’indiquer un min. La direction des liens n’est pas et ne peut pas être prise en compte. Les commandes dyad.census et triad.census donnent exactement les mêmes résultats que statnet mais la présentation est moins claire ici pour cette dernière fonction car les codes MAN ne sont pas rappelés. Le résultat reproduit ci-dessous n’est pas très simple à interpréter.

 triad.census(g) 
 [1] 11 12  8  0  1  0  1  0  1  0  0  0  1  0  0  0

La commande degree fournit par défaut est la somme des degrés entrants et sortants. La normalisation (normalized = TRUE) se fait ici par le degré maximal possible. Si je calcule les degrés entrants normalisés, j’obtiens le résultat suivant :

 degree(g, mode="in", normalized = TRUE) 
    a         b      c     d      e       f         g 
0.1666667 0.3333333 0.50 0.000 0.1666667 0.1666667 0.00

Le degré entrant de c est 3, il y a 7 sommets donc le maximum possible est de 6 (pas de boucle) : c a donc un degré entrant normalisé de 0.5. La fonction degree.distribution donne la proportion de sommets ayant un degré zéro, un, deux etc. Mais si on visualise avec la fonction plot(degree.distribution(g)), l’axe des abscisses est faux (il commence à un au lieu de zéro). Et si vous faites partie des adeptes du scale-free, le fameux plot log log s’obtient aisément (voir le script) mais il n’a évidemment aucun intérêt pour un réseau aussi modeste.

La fonction closeness appliquée à un graphe non connexe donne les résultats aberrants suivants :

      a          b          c          d          e          f          g 
0.03333333 0.03333333 0.02380952 0.04000000 0.02777778 0.02777778 0.02380952

Il n’est par définition pas possible de calculer une centralité de proximité pour un sommet isolé, igraph y parvient… La solution permettant d’obtenir un résultat cohérent est de décomposer le graphe puis de la mesurer sur chacune des composantes considérée individuellement. L’option mode= »all » permet d’ignorer la direction des liens.

g2 <- decompose.graph(g)
plot(g2[[1]])
sapply(g2, closeness, mode="all")
[[1]]
        a         b         c         d 
0.2500000 0.3333333 0.3333333 0.2500000 
[[2]]
e f 
1 1 
[[3]]
  g 
NaN

Le résultat est plus crédible (NaN soit Not a Number pour g effectivement). 1 pour e et f, c’est logique. Mais pourquoi 0.25 pour a et d, 0.33 pour b et c. Petit rappel : pour mesurer la closeness, on divise 1 par la somme des plus courts chemins entre un sommet et tous les autres. Pour a et d, on a donc 1/(1+1+2) ; pour b et c, 1/(1+1+1). À retenir en résumé : faire attention avec la fonction closeness qui peut facilement donner des résultats absurdes…

La fonction betweenness donne les mêmes résultats que statnet mais igraph propose également de mesurer l’intermédiarité des liens, c’est-à-dire le nombre de plus courts chemins empruntant un lien donné. Par définition, cette intermédiarité des liens sera toujours supérieure ou égale à 1 (le lien entre a et b est placé sur le plus court chemin entre ces deux points). Les résultats sont présentés dans l’ordre des liens du fichier de départ. Soit le résultat suivant (les codes des liens ont été rajoutés manuellement a posteriori) :

edge.betweenness(g, directed=TRUE) 
   ef fe  ab  ba  ac db dc bc
[1] 1  1   1  2   1  2   1   1
edge.betweenness(g, directed=FALSE)
    ef  fe  ab        ba         ac      db        dc         bc
[1] 0.5 0.5 0.8333333 0.8333333 1.3333333 1.6666667 1.3333333 1.0

Si on prend en compte l’orientation des liens, tous ont un minimum de 1 et le lien ba atteint 2 : il se situe en effet sur les plus courts chemins ba et dba.  Si on ne la prend pas en compte, les résultats sont difficiles à comprendre. Pourquoi des résultats différents pour les liens db, dc, ab et ba ? Tout simplement parce qu’il y a trop de liens pour l’opération demandée : si je ne tiens pas compte de la direction, mon graphe ne comprend que 6 liens.  Donner des résultats pour 7 oblige à des pondérations étranges… La solution la plus pertinente est de transformer d’abord le réseau en réseau non orienté (as.undirected) puis de mesurer l’intermédiarité des liens. On obtient alors un résultat cohérent :

[1] 1.5 1.5 1.0 1.5 1.5 1.0

1 correspond ici aux liens ef et bc et les quatre autres liens obtiennent un score identique. Chacun est placé sur le plus court chemin entre ses sommets terminaux et est l’un des deux plus courts chemins entre a et d : tous ont donc 1.5.

La fonction transitivity (nombre de triangles fermés parmi les voisins d’un sommet) ne permet pas de prendre en compte l’orientation des liens : il est donc nécessaire pour obtenir des résultats corrects de prendre le graphe non orienté. On obtient alors les résultats suivants

transitivity(g3, "local")
[1] 1.0000000 0.6666667 0.6666667 1.0000000       NaN       NaN       NaN

a et d sont situés à la pointe dans des triangles fermés donc la transitivité est de 1 ; efg ne font pas partie de triades donc le résultat n’est pas un nombre (NaN = Not a Numer). b et c sont voisins et tous deux liés à a et à d ; comme il manque 1 lien entre a et d, ils obtiennent un score de 2/3 (2 triangles fermés sont présents sur 3 possibles). La recherche des plus chemins, par défaut, ne tient pas compte non plus de l’orientation des liens. La fonction centralization donne des résultats corrects pour les graphes k-réguliers (score de 0) et non valides pour les graphes en étoile (voir le script où un graphe étoilé de 10 sommets obtient un score de centralisation par le degré de 0.8 seulement). En ce qui concerne les graphes bipartis, même remarque que pour statnet : igraph permet d’en définir, d’en représenter mais ne permet pas de les analyser – lorsqu’une mesure est lancée, il est considéré comme un one-mode.

Pour résumer : il est beaucoup plus facile d’importer ses données et de les filtrer avec igraph, il est aussi beaucoup plus facile d’obtenir des résultats aberrants si l’on n’est pas attentif… À venir très prochainement, un billet détaillé consacré au package bipartite.

R et statnet – revue de détail

Suite aux cours et aux TD donnés à l’ENSAI, j’ai découvert de nouveaux (et agaçants) problèmes liés à l’analyse de réseau avec R. De plus, la nécessité de commenter les résultats m’est clairement apparue. Ce billet vise donc à détailler au maximum les étapes et les résultats produits par le package statnet – un billet consacré à igraph est en cours de préparation. Le script et les fichiers de données sont téléchargeables ici.

Rappel : statnet (et igraph) permettent d’analyser des graphes non valués et one-mode. Si statnet permet de mener des modèles type ERGM, igraph est plus simple d’utilisation. Pour l’analyse de réseau biparti avec R, oubliez statnet et igraph (qui proposent pourtant des options bipartite=TRUE) et voyez plutôt du côté du package bipartite qui est, à ma connaissance, le seul à donner des résultats corrects pour ce type de réseau (voir la démonstration dans le script).

1. Liens, attributs et isolés : sur le format et l’importation des données

Le graphe fictif qui va servir d’exemple tout au long de ce billet représente les interactions autour d’une machine à café dans une petite entreprise : la population est constituée de 7 individus répartis en 2 équipes et de niveaux d’ancienneté différents. Un lien signale qu’une personne a payé un café à une autre. Le graphe est simple : pas de boucle (on ne prend pas en compte les cafés que s’offre une personne) ; pas de liens de nature différente. Il est orienté (une personne offre à une autre) et valué (combien de cafés ont été offerts par une personne à une autre dans la semaine ?).td1plot

Les sommets sont définis par deux attributs : un attribut quantitatif relatif à l’ancienneté (ANC – taille du sommet), un attribut qualitatif relatif à l’équipe (TEAM – couleur du sommet). Les liens sont définis par une direction et une intensité (INT). La valeur des attributs est donnée dans le tableau ci-dessous.

td11

Un rappel important : statnet (comme igraph) ne prend pas en compte de l’intensité des liens pour les calculs. Elle peut juste être utilisée pour la représentation graphique.

Premier problème : statnet génère un graphe à partir d’une liste de liens. Or, le sommet g est isolé. Une solution est de créer dans son fichier de départ un lien fictif g-g puis de préciser lors de l’importation qu’il n’y a pas de boucle.

L’importation des données se fait en deux temps (liens, attributs des sommets). La transformation en objet network, manipulable par statnet, nécessite de ne prendre en compte que les deux premières colonnes (origine – destination). Taper ensuite le nom du graphe permet d’en connaître les caractéristiques. De façon étrange, alors qu’il n’y a pas de boucle, statnet indique malgré tout 9 liens et non 8. Pourtant, le calcul de la densité (cf infra) donne un résultat correct – seuls les 8 liens réellement présents sont donc pris en compte dans les calculs.

library(statnet)
#import fichier
 liens <- read.table("liens.txt", header=TRUE, sep=";")
 attributs <- read.table("attributs.txt", header=TRUE, sep=";")
g <- as.network(as.matrix(liens[,-3]), loops = FALSE)
g
 Network attributes:
 vertices = 7
 directed = TRUE
 hyper = FALSE
 loops = FALSE
 multiple = FALSE
 bipartite = FALSE
 total edges= 9
 missing edges= 0
 non-missing edges= 9
Vertex attribute names:
 vertex.names
No edge attributes

Pour l’instant, les sommets ont un attribut (leur nom) et les liens n’en ont aucun. Les lignes suivantes permettent de transférer les données des data.frame vers l’objet network.

g %v% "ANC" <- attributs$ANC
g %v% "TEAM" <- as.numeric(attributs$TEAM)
g %e% "INT" <- liens$I

Si l’on tape à nouveau g, on observe que les attributs sont désormais plus nombreux.

 Vertex attribute names:
 ANC TEAM vertex.names
Edge attribute names:
 INT

Il est sans aucun doute possible de filtrer le graphe selon les attributs des liens et des sommets (par exemple, extraire le graphe des relations entre membres de l’équipe A) mais si l’opération est facile avec igraph, elle ne l’est pas avec statnet (i.e. je n’ai pas trouvé comment faire, si ce n’est en filtrant les données en amont, avant la transformation en graphe…).

Pour obtenir la figure ci-dessus, deux options sont possibles : appeler les données des data.frame, appeler les attributs de l’objet network. Le résultat est heureusement le même.

#à partir des fichiers de départ
gplot(g, gmode="digraph", displaylabels=TRUE, vertex.col=nodeColors, 
      vertex.cex= log(attributs$ANC), edge.lwd = liens$I*2)

#à partir des attributs de l'objet network
gplot(g, gmode="digraph", displaylabels=TRUE, vertex.col=nodeColor, 
      vertex.cex= log(g %v% "ANC"), edge.lwd = g %e% "INT")

2. Quelques mesures et quelques précisions

Le calcul de la densité (fonction gden) donne comme résultat 0.1904762, ce qui correspond bien à 8 (nombre de liens présents) divisé par 7*6 (nombre de liens possibles) – pour mémoire, dans un graphe simple orienté de n sommets, le nombre maximum de liens est égal à n*(n-1).

Le nombre de composantes connexes s’obtient avec la fonction components et donne ici comme résultat 5. Pourquoi 5 ? Par défaut, statnet considère que, dans un graphe orienté, la connexité recherchée est la forte : il doit exister un chemin (une suite de liens orientés) entre toute paire de sommets au sein d’une composante connexe. La composition des 5 composantes connexes est obtenue avec la commande component.dist. Si l’on souhaite les composantes faiblement connexes (au nombre de 3), il suffit de modifier l’option.

components(g)  #   5 composantes fortement connexes
cs <- component.dist(g) 
cs$membership #  et leur composition

components(g, connected="weak") #  3 composantes faiblement connexes
cw <- component.dist(g,connected="weak")
cw$membership #composition
cw$csize      #et taille

La liste des plus chemins – retour de la commande geodist – comprend deux matrices : $counts donne le nombre de plus courts chemins entre paires de sommets (il peut très bien y avoir plusieurs plus courts chemins entre deux sommets) ; $gdist donne la longueur en liens des plus courts chemins. La commande dyad.census donne un résultat facilement interprétable (nombre de liens mutuels, asymétriques et nuls). La commande triad.census donne en sortie le code MAN (mutuel, asymétrique, nul) des triades et le nombre de triades respectives. Dans le graphe fictif étudié, il n’y a aucune triade complète, et donc 0 sous le code 300.

Il est déconseillé d’utiliser la commande clique.census : même avec un graphe aussi petit, et sur un ordinateur récent et plutôt puissant, RStudio plante…

En ce qui concerne le degré, la commande degree fournit par défaut la somme des degrés entrants et sortants par sommet. Si l’on choisit de normaliser, la somme des degrés des sommets sera égale à 1 (le mode de normalisation est différent dans igraph). Le graphe étant non connexe, la commande closeness donne un résultat égal à zéro pour tous les sommets (igraph donne lui des résultats aberrants). La centralité d’intermédiarité (betweenness) donne ici 0 pour tous les sommets sauf pour b qui obtient 1 : il y a en effet un seul plus court chemin (dba) passant par b. Si l’on ne prend pas en compte la direction des liens, tous les autres sommets restent à zéro et b descend à 0.5. Pourquoi ? Il y a deux plus courts chemins entre d et a (dba et dca), et 1 sur 2 passe par b. Que c reste à zéro est par contre difficilement explicable… (si vous avez une idée, n’hésitez pas à la soumettre).

Enfin, et je termine ici pour l’examen détaillé de certaines fonctions de statnet, la mesure de la centralisation du graphe est correcte dans statnet – on obtient bien 0 avec un graphe type cercle et 1 avec un graphe étoilé – mais elle donne des résultats erronés dans igraph

Dernier point qui concerne les graphes bipartis : statnet permet (difficilement) de les importer puis de calculer des indicateurs mais ceux-ci sont faux. Dans l’exemple du script, nous avons 7 liens, 3 événements et 4 acteurs. Si les 4 acteurs participent aux 3 événements, le graphe est complet, la densité de 1 et le nombre de liens égal à 12. Or, la commande gden donne comme résultat 0.33, soit 7*2 / 7*6 – dans un graphe simple non orienté de n sommets, la densité est égale à 2n / n(n-1). Et si vous tentez l’expérience avec igraph, le résultat est le même. Le seul – et très relatif – intérêt est de pouvoir passer ensuite à des matrices acteurs-acteurs ou événements-événements. Cette dernière opération est possible sans ces packages en multipliant la matrice m par sa transposée pour obtenir la matrice acteurs-acteurs

m %*% t(m)

ou en faisant l’opération inverse (matrice événements-événements)

t(m) %*% m

ENSAI Cours 4 – L’analyse des réseaux complexes

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

Au milieu des années 90, l’étude des réseaux dans les différentes disciplines (sociologie, géographie, écologie etc.) a atteint un stade de « science normale » au sens kuhnien du terme : on sait quels réseaux étudier, comment recueillir les méthodes, comment les traiter et comment interpréter les résultats. Des raffinements sont proposés (multiniveau, modèles statistiques) mais chacun travaille dans son pré carré. L’arrivée brutale et inattendue des mathématiciens et surtout des physiciens à la fin des années 90 bouleverse le paysage scientifique relatif à l’analyse de réseaux.

1. Trois grandes familles de réseaux

Jusque 1998, l’étude des réseaux repose (implicitement ou explicitement) sur le modèle des graphes aléatoires défini dans les années 50 par Erdös et Renyi. Deux nouveaux modèles sont proposés à la fin des années 90 et prétendent révolutionner l’étude des réseaux, voire fonder une science des réseaux.

1.1 Le graphe aléatoire (random graph)

Modèle mathématique de réseau proposé par Erdös et Rényi. Un mot sur Erdös : auteur de plus de 1500 articles, n’a jamais eu un poste fixe dans une institution, passe son temps à aller chez des collègues pour résoudre des problèmes avec eux. Il existe un jeu populaire chez les mathématiciens : le nombre d’Erdös (voir le site http://www.oakland.edu/enp). Le principe est simple : Erdös a 0, ses co-auteurs (plus de 500) ont 1, si l’on a écrit non avec Erdös lui-même mais avec un de ses co-auteurs, on a un nombre de 2 etc. La version grand public existe pour le cinéma : l’Oracle de Kevin Bacon (si un acteur ou une actrice a tourné dans un film avec Bacon, nombre de 1 etc.). Il s’agit d’un jeu développé par des étudiant-e-s américain-e-s dans les années 90 prétendant que Kevin Bacon était l’acteur le plus central du cinéma – ce qui est évidemment faux (https://oracleofbacon.org/) – mais leur a permis de passer dans une émission de télévision populaire à l’époque.

Erdös écrit huit articles avec Rényi entre 1959 et 1968 sur les réseaux (mais il a publié avant sur le sujet). Ils proposent un modèle mathématique de formation de graphe : fixer un nombre de sommets, une probabilité de relations entre ces sommets et générer des liens (non orientés) de manière aléatoire entre sommets (ni boucle ni liens multiples). Deux propriétés des graphes aléatoires peuvent être soulignées : si le graphe est grand, et malgré le (grâce au) placement aléatoire des liens, tous les sommets auront à peu près le même degré, ce dernier suivant une distribution de Poisson (et donc existence d’un pic permettant de résumer les propriétés du graphe) ; il y a émergence d’une composante connexe géante quand le degré moyen atteint 1. Ce modèle de réseau aléatoire ne prétend pas refléter une quelconque réalité sociale – les deux modèles suivants ont une toute autre prétention…

1.2 Le graphe petit-monde (small-world network)

Des recherches scientifiques devenues un mythe populaire : Milgram et les six degrés de séparation.

Milgram, sociologue américain, très connu pour ses travaux sur l’obéissance à l’autorité (From Obedience to Authority, Harper and Row, 1969 – cf I comme Icare) lance une expérience dans les années 60 : des personnes dans des trous perdus (Wichita, Kansas et Omaha, Nebraska) doivent envoyer un courrier à un agent de change à Boston. La consigne principale est d’envoyer le courrier à quelqu’un qu’ils connaissent (If you know the target person on a personal basis, mail this folder directly to him (her). Do this only if you have previously met the target person and know each other on a first name basis), l’objectif de la recherche étant de mesurer la longueur de la chaîne relationnelle créée. L’étude conclue par une longueur moyenne de 5. Ce résultat devient un mythe populaire : l’idée qu’il existe entre deux individus quelconques six degrés de séparation (six liens personnels). Or, des travaux récents (Kleinfeld, 2002) ont montré que les résultats de Milgram étaient peu solides : à l’origine, 300 personnes devaient expédier le courrier depuis le Nebraska. En fait, 100 vivaient à Boston, 200 dans le Nebraska dont la moitié appartenait au même milieu professionnel que la cible… Sur 96 personnes obéissant aux critères voulus, seules 18 lettres ont atteint leur cible…

En 1998, Watts et Strogatz, deux mathématiciens (un doctorant et son directeur de thèse), choisissent de renverser la perspective : non pas se demander si tel ou tel réseau est petit-monde mais prendre un réseau et le transformer pour qu’il devienne petit-monde. Watts avoue n’avoir à peu près rien lu sur le sujet pour ne pas se laisser décourager (la descendance de l’article de Milgram est très fournie). Le modèle est simple : partir d’un graphe k-régulier (tous les sommets ont le même degré), supprimer un lien et le remplacer par un lien aléatoire. Ils découvrent que la transitivité (qu’ils nomment clustering coefficient en raison de leurs lacunes bibliographiques) reste longtemps élevée mais la longueur moyenne des plus courts chemins chute très rapidement. Une deuxième version du modèle met en évidence le fait suivant : quelle que soit la taille du réseau, les 5 premiers liens aléatoires générés réduisent la longueur moyenne des chemins par deux.

L’article a un très fort impact et entraîne une multiplication frénétique des mesures : à peu près tous les réseaux (exceptés certains réseaux techniques en raison des contraintes de localisation) sont small-world… L’intérêt social est peu évident de l’aveu même de Watts (2003). Comme il l’écrit, « the real issue is that there is a big difference between two people being connected by a short path and their being able to find it.[p. 136] […] But even if it is true that everyone can be connected to everyone else in only six degrees of separation, so what? How far is six degrees anyway? From the point of view of getting a job, locating information, or getting yourself invited to a party, anyone more distant than a friend of a friend is for all intents and purposes, a stranger. So […] anything more than two degrees might as well be a thousand. » [p. 299-300]

1.3 Le graphe sans échelle (scale-free network)

Albert et Barabási (doctorante et directeur de thèse) s’intéressent à la distribution des degrés au sein des réseaux (notamment ceux étudiés par Watts et Strogatz) et découvrent qu’elle obéit à une loi de puissance, ce qui n’est prévu ni dans le cas du graphe aléatoire ni dans le cas du graphe petit-monde. Ils proposent alors un modèle dynamique de réseau (un sommet est ajouté à chaque temps t) fondé sur le mécanisme de l’attachement préférentiel : plus un sommet a un degré élevé, plus un nouveau sommet aura tendance à se connecter avec celui-ci. La distribution des degrés est donnée sous forme de probabilités : la probabilité qu’un sommet choisi aléatoirement ait un degré k suit une loi telle que P(k) = k. Ils proposent un article à Science en 1999 avec ces 2 principes, l’article est rejeté, l’auteur insiste auprès de la revue et l’article est finalement publié. Cet article a un impact étonnant, en physique et dans bien d’autres disciplines.

Pourquoi nommer ces réseaux sans échelle ? Dans un graphe aléatoire, la grande majorité des sommets a un même degré et les sommets s’écartant de cette moyenne sont rares. À l’inverse, la distribution en loi de puissance des degrés dans un réseau sans-échelle ne permet pas de donner une valeur résumant cette distribution. Une des limites du modèle proposé, limite qui sera résolue dans des articles ultérieurs, concerne la prime donnée au premier arrivant : plus un sommet est ancien, plus il doit être central or, qu’il s’agisse des portails de recherche sur internet (Google) ou des citations scientifiques, cette règle est régulièrement violée.

Cet article a eu un impact énorme alors qu’il mettait en évidence une découverte très relative. Les lois de puissance étaient connues (en sciences sociales et dures) depuis des décennies, tout comme le mécanisme de l’attachement préférentiel. Pareto au 19e siècle met en évidence la très forte inégalité de distribution de richesse (une poignée de très riches, une large majorité de pauvres) ; Merton au 20e met en évidence l’effet de Matthieu (Matthew effect – d’après la parabole biblique) : plus un acteur est fortement connecté, plus il a de chances d’attirer de nouveaux liens : la loi de puissance était également présente dans les modèles de Zipf (1949) ou d’Herbert Simon (1955). Cette découverte relative n’empêchera nullement Barabási et ses émules de prétendre trouver la solution à presque tous les problèmes économiques et sociaux imaginables (cf son ouvrage Linked).

2. Questions de recherche, données, méthodes

Les questions de recherche sur les réseaux dits complexes sont à peu près les mêmes qu’en SNA ou qu’en géographie : comment se forme le réseau ? quelles sont ses propriétés ? quels sont les acteurs ou les liens les plus centraux ? quelle est leur vulnérabilité ? etc. La nouveauté vient du type de réseaux étudiés (n’importe lequel pourvu qu’il soit grand…) ainsi que des méthodes (où la nouveauté est parfois relative). En ce qui concerne les données, the bigger the better et le sens thématique apparaît souvent très secondaire : tout ou presque peut être étudié à l’aide des méthodes proposées. Le recueil automatisé d’informations en ligne explique l’intérêt pour les réseaux sociaux de l’internet (facebook, twitter) et les base de données (bibliométrie). Si les formalisations mathématiques sont parfois innovantes, leur apport thématique est souvent limité, ce qui est d’ailleurs normal : comme le souligne Watts (2003, p. 6), « The essential problem is that the physicists developed their tools to adress physics questions; not social or economic ones […] The result is that the method looks very impressive and produces lots of elegant results, but it doesn’t solve the actual problem because it’s not about the actual problem » (en italique dans le texte).

De très nombreuses méthodes et mesures ont été proposées, certaines étant des adaptations de mesures existantes, voire des mesures déjà existantes renommées (cf le cas du clustering coefficient supra). La notion de graphe assortatif et disassortatif est intéressante : un graphe est dit assortatif lorsque les sommets de degrés comparables tendent à se connecter entre eux (les gros avec les gros, les petits avec les petits).

La taille des réseaux étudiés oblige à innover : les algorithmes de détection des cliques sont par exemple inadaptés aux grands réseaux ; les modèles statistiques type ERGM (cf cours 5) ont eux aussi inapplicables donc une autre famille de modèles – dont les principes sont proches – est proposée. Une des méthodes de partitionnement de graphe ayant eu le plus de succès est celle proposée par Newman et Girvan : a) calculer l’intermédiarité des liens du graphe, b) supprimer celui qui a la plus forte (en cas de betweenness égale, en tirer un au sort), c) recalculer l’intermédiarité des liens restants et b) à nouveau. La pertinence du découpage obtenu est vérifiée via le calcul de la modularité (modularity). Les partitions créées ne correspondent pas nécessairement dans ce dernier cas à des groupes fortement connexes (tout sommet est obligatoirement affecté à un cluster).

3. Apports et limites des complex networks studies

Les physiciens ont donné un coup de fouet salutaire à l’analyse de réseaux en général. Il y a eu un essor énorme (sans doute plus quantitatif que qualitatif) des études sur les réseaux. Deux phases peuvent être distinguées : celle du prédateur dominant ; celle du prédateur collaboratif. La première phase était (est parfois encore) marquée par une ouverture disciplinaire nulle, la redécouverte de mesures anciennes sans citation des premiers auteurs, la prétention à aborder et à résoudre tous les problèmes (économiques, sociaux, technologiques etc.). La deuxième phase (inégalement atteinte) montre besoin de collaborer avec les autres disciplines, et notamment les SHS, pour donner un sens aux résultats obtenus.

Ces deux modèles ont fortement percolé dans les autres disciplines et des phénomènes d’imitation/importation plus ou moins maîtrisés sont apparus. Comment l’expliquer ? Il y a sans doute un aspect lié à l’habitus disciplinaire des physiciens : force de frappe, accès aux revues prestigieuses (Nature, Science), budgets différents (i.e. très largement supérieurs), habitudes de publication (accès ouvert via arXiv, articles courts, illustrés, paraissant à un rythme soutenu), partage des données, sens de la communication (moins de 3 ans pour Watts et Barabási pour écrire des ouvrages de vulgarisation) et choix peu risqué des sujets de recherche (pour citer Watts une dernière fois : « Physicists, it turns out, are almost perfectly suited to invading other people’s disciplines, being not only extremely clever but also generally much less fussy than most about the problems they choose to study »). Les études small-world/scale-free ont donné lieu à un véritable effet de mode scientifique – qui dure encore aujourd’hui. Les physiciens ont également proposé des outils adaptés à l’étude des grands réseaux (ex. réseaux de villes, de multinationales) susceptibles d’intéresser d’autres disciplines (géographie, science régionale).

En ce qui concerne les apports, la proposition de modèles alternatifs au graphe aléatoire (statistiquement intéressant mais d’une pertinence sociale très limitée) est très utile : même s’il s’agit d’un recyclage pour le réseau scale-free, et même s’il est rare de trouver des réseaux qui ne soient pas small-world. L’autre apport majeur consiste dans les méthodes pour analyser et surtout pour représenter les propriétés des grands réseaux. Utiliser par exemple la distribution des degrés pour résumer une propriété d’un réseau au lieu du traditionnel graphe était une idée brillante.

Deux articles

Duncan J. Watts et Steven H. Strogatz. « Collective dynamics of ‘small-world’networks » Nature 393.6684 (1998): 440-442 (plus 24 500 citations selon Google scholar, consulté le 8 janvier 2015)

R. Guimera, S. Mossa, A. Turtschi et L.N. Amaral. The worldwide air transportation network: Anomalous centrality, community structure, and cities’ global roles. Proceedings of the National Academy of Sciences, 2005, 102(22), p. 7794-7799.

  • Quelles sont les questions de recherche ?
  • Quelles sont les données utilisées ?
  • Quelles sont les méthodes utilisées et quels sont les principaux résultats ?
  • Quel type d’illustration est utilisé ?

Références

Albert-László Barabási, 2003, Linked. How Everything is Connected to Everything Else and What It Means for Business, Science, and Everyday Life, Plume book, New York
Judith S. Kleinfeld, 2002, The small world problem, Society, 39(2):61-66 et 2002; Could it be a big world after all? The six degrees of separation myth, Society, 12.
Mark Newman, 2010, Network: An Introduction, Oxford University Press
Duncan J. Watts, 2003, Six degrees. The science of a Connected Age, William Heinemann, London

ENSAI TD2 – Manipulation de matrices et cartographie de flux avec R

L’objectif du TD est double : manipuler des matrices pour cartographier des indicateurs calculés à partir des marges (cf cours 3) ; mettre en œuvre avec R les méthodes de flux dominants, de flux majeurs et les modèles gravitaires. Ce TD reprend en partie une séance donnée avec Claude Grasland dans le cadre du groupe elementR (cf ce billet). Outre Claude Grasland, les scripts utilisés pour ce TD doivent beaucoup à Timothée Giraud (cf le blog R Géomatique), Nicolas Lambert (cf le blog néocarto) et Malika Madelin.

Packages utilisés : reshape2, maptools, rCarto, RColorBrewer.

Les données utilisées sont les migrations entre les dix régions tchécoslovaques en 1965 (téléchargement).

Manipulations de base

Deux manipulations sont nécessaires pour travailler sur les matrices : passer d’une matrice carrée à un format origine – destination – flux et réaliser l’opération inverse. De plus, pour cartographier des flux, il est nécessaire d’avoir un fond de carte au format .shp (avec des codes pour les unités spatiales similaires aux codes utilisées dans les fichiers de données pour permettre la jointure), de calculer les coordonnées des centroïdes et enfin les distances entre ces centroïdes. L’exemple ci-dessous détaille les étapes :

library(reshape2)

#passage data.frame type matrice en objet matrix

#importation de la matrice
tab <- read.table("matrice.csv", ... ,stringsAsFactors=FALSE)

#passage d'un objet data.frame à un objet matrix
mat <- as.matrix(tab[,-1])
row.names(mat) <- tab[,1]

#passage d'une matrice au format origine - destination - flux
tabflow <- melt(mat)
names(tabflow) <- c("i","j","Fij")
head(tabflow)

#passage d'une liste i-j-Fij au format matrice
tempo <- melt(tabflow,
             id.vars=c("i","j"),
             measure.vars="Fij")
tempo2 <- dcast(tempo, i~j)
matflow2 <- as.matrix(tempo2[,-1])
rownames(matflow2) <- tempo2[,1]

library(maptools)

#import d'un shape
fdc <- readShapeSpatial("carte.shp")

#calcul des centroides
centres <- cbind(fdc@data[,"CODE"], as.data.frame(coordinates(fdc)))
colnames(centres) <- c("CODE","X","Y")
head(centres)

#calcul de la distance
#2 étapes : passer en format long et coller les xi, yi, xj, xj
#appliquer la formule dij = round(sqrt((xi-xj)**2 + (yi-yj)**2)/1000, 1)

Déroulement du TD

Les scripts détaillant toutes les étapes sont disponibles ici.

Opérations élémentaires sur les matrices

  • importer le fichier matmig_1961_1965.csv et le tranformer en objet matrice (Fij)
  • calculer la transposée (Fji)
  • calculer le volume et le solde des échanges
  • à l’aide de la fonction apply, calculer les sommes marginales (arrivée, départ, volume, solde, asymétrie)
  • importer le fichier tch10.shp
  • cartographier différents indicateurs à l’aide du package rCarto (somme des départs, volume et asymétrie migratoire)
  • cartographier les flux d’émigration

Voici deux exemples de cartes à produire.

solde

echanges

Flux dominants et flux majeurs

  • à l’aide des fonctions apply, sum, max et de l’argument which.max, déterminer les flux dominants
  • à l’aide des foncions apply et rank, déterminer les flux majeurs (x premiers flux de i vers j)
  • repérer les flux supérieurs à 2% du volume total des flux et les cartographier

Modèles gravitaires

  • calculer les marges de la matrice de flux et les centroïdes des dix régions
  • passer la matrice en format i – j – Fij et coller masses et coordonnées
  • importer le fichier attributaire tchpop_1965_1990.csv et coller les éléments utiles au tableau i j Fij
  • le tableau final comprendra les éléments suivants : i j Fij Fji Fi Fj Xi Yi Xj Yj Dij POPi POPj
  • tester un modèle gravitaire prenant en compte masses et distance de type glm(Fij~log(POPi)+log(POPj)+log(Dij), data=mydata, family=poisson)
  • étudier les paramètres – summary(model) –, analyser la variance puis calculer et cartographier les résidus
  • mêmes étapes avec un modèle à double contrainte (origine et destination) – glm(Fij~i+j+log(Dij), data=mydata, family=poisson)

ENSAI Cours 3 – Réseaux spatiaux et analyse de flux

Avertissement : 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

Si sociologie, physique et informatique étudient de manière préférentielle voire exclusive des réseaux non planaires, l’étude de réseaux techniques, territoriaux et planaires a très longtemps caractérisé les approches géographiques des réseaux. Si certain-e-s géographes s’intéressent depuis le milieu des années 90 à d’autres types de réseaux et ont, de fait, renouvelé leurs approches méthodologiques, important notamment des mesures proposés par les physiciens (Ducruet et Beauguitte, 2013), la grande majorité des travaux géographiques contemporains reste marquée par le caractère planaire des réseaux étudiés.

Dans l’un des ouvrages de référence sur l’étude géographique des réseaux (Dupuy, 1988), le réseau est ainsi défini : « toute infrastructure permettant le transport de matière, d’énergie ou d’information, qui s’inscrit sur un territoire où elle est caractérisée par la topologie de ses point d’accès ou points terminaux, de ses arcs de transmission, de ses nœuds de bifurcation ou de communication ».

Historiquement, l’un de premiers objets étudié par la géographie et mobilisant l’analyse de réseau fut la morphologie fluviale : comment caractériser les cours d’eau et leurs affluents ? Le caractère planaire se double dans ce cas de la structure en arbre du réseau étudié. Horton et Strahler proposeront dans les années 40-50 une classification hiérarchique des cours d’eau. Puis des méthodes d’analyse ont été mises au point pour l’étude des réseaux d’infrastructures et notamment les réseaux de transport. Une seconde tradition disciplinaire concerne l’analyse des flux entre lieux (graphes valués non planaires).

1 L’analyse des réseaux techniques

Les réseaux techniques présentent au moins deux caractéristiques distinctes par rapport aux réseaux sociaux : ils ont nécessairement une inscription spatiale (coordonnées précises pour les sommets, tracé donné pour les liens) et ils servent à transporter une quantité donnée (de personnes, de biens, d’énergie etc). On aura donc affaire à des réseaux le plus souvent valués et spatialement contraints. Leur étude et leur représentation différeront donc – tout comme les logiciels utilisés (SIG).

1.1 Les fondateurs

Deux ouvrages ont exercé une influence majeure sur l’étude géographique des réseaux : une thèse, éditée en 1963 (Kansky, 1963, The structure of transportation networks) et un manuel édité en 1969 (Chorley et Haggett, 1969, Network analysis in geography). L’ouvrage de Kansky s’intéresse uniquement aux réseaux de transports dont les sommets et les lignes s’inscrivent sur le territoire – en excluant donc le transport aérien (« The essential elements of transportation networks are thus man-made features located on the earth’s surface in geometric patterns »). Le spectre couvert par le manuel de Chorley et Haggett est plus large mais la focalisation sur les graphes planaires reste prédominante, tout comme la prise en compte de la valuation des liens (distance, intensité, etc.). Si le graphe est utilisé pour présenter les différents indicateurs proposés, les études empiriques sont illustrées très majoritairement par le marqueur disciplinaire numéro un en géographie : la carte.

Kansky propose pour l’étude des réseaux une série d’indicateurs inspirés par les travaux du mathématicien Claude Berge : simples à calculer, prenant en compte des indicateurs basiques (nombre de liens, nombre de sommets, distance, intensité des relations), ils restent aujourd’hui encore très largement utilisés. Très pédagogique, largement illustré par des petits graphes permettant de détailler le calcul (et l’interprétation) des indices présentés, et proposant une étude empirique solide sur le réseau ferré sicilien, l’ouvrage reste tout à fait recommandable.

Les indices Kansky se répartissent en deux catégories : ceux basés sur des ratios (nommés par des lettres grecques) ; ceux basés sur des « individual elements of transportation networks ».

Soit un graphe avec E le nombre de liens, V le nombre de sommets et P le nombre de composantes connexes :

  • alpha = ratio entre le nombre de circuits présents et le nombre de circuits possibles : il varie entre 0 (arbre) et 1 (graphe complet). Pour les graphes planaires, la formule est (EV+P) / (2V – 5) ; pour les graphes non planaires alpha = (EVP) / (V(V-1)/2 * (V-1)). C’est un indicateur de connectivité ;
  • beta = E/V. Une valeur inférieure à 1 signale un arbre ou un graphe non connexe, une valeur égale à 1 signale la présence d’un seul circuit ; beta ne peut dépasser 3 pour un graphe planaire (pas de limite supérieure pour un graphe non planaire). L’indice beta correspond au degré moyen ;
  • gamma : ratio entre le nombre de liens présents et le nombre de liens possibles. Une formule est proposée pour les graphes planaires – gamma = E / 3(V-2) – et une autre pour les graphes non planaires – gamma = E / (V * (V-1)/2). Le terme densité employé dans les autres disciplines (et connectance en écologie) est synonyme ;
  • eta : longueur moyenne des liens, exprimé généralement en kilomètres ;
  • pi : flux total divisé par le long des plus courts chemins kilométriques (ou diamètre kilométrique) ;
  • theta : flux total divisé par le nombre de liens (intensité moyenne) ;
  • iota : distance totale divisée par le flux total.

Mesures sur des éléments individuels

  • nombre cyclomatique mu = E – V + P. Plus il est élevé, plus le réseau est dense ;
  • diamètre du graphe (plus long des plus courts chemins kilométrique) ;
  • nombre associé (associated number) : pour chaque sommet, distance au sommet qui est le plus éloigné dans le réseau ;
  • degré de connectivité : soit le nombre maximal de liens d’un réseau non planaire (V*V-1)/2, le degré de connectivité est égal à ce nombre maximal divisé par le nombre de liens (inverse de l’indice gamma) ;
  • indice de Shimbel (proposé par cet auteur en 1953 dans le Bulletin of Mathematical Biophysics) : somme des distances entre un sommet et tous les autres sommets du réseau. La distance peut être mesurée de façon topologique (distance mesurée en nombre de liens) ou pondérée (par une distance, un flux, une intensité etc.) ;
  • indice de détour (circuity) : écart moyen entre la différence au carré des distances réelles et des distances à vol d’oiseau.

Dans sa thèse, Pascale Dancoisne (1984) signale que 3 indices proposés par Berge ne sont pas repris par Kansky : le nombre de connectivité (nombre de sommets à supprimer pour que le graphe ne soit plus connexe), l’indice de connexité (nombre de liens à supprimer pour rendre le graphe non connexe) et l’indice chromatique ( nombre minimal de couleurs à utiliser pour que 2 sommets voisins soient de couleur différence).

Exercice : soit le réseau (fictif) de villes ci-dessous : les chiffres en gras et en italique indiquent la distance entre villes, les autres la population. Proposez une ou deux mesures globales sur le réseau et une ou deux mesures locales (indices Kansky ou indices issus de la SNA, prenant en compte ou non la valuation des sommets et des liens). Si vous deviez proposer un nouveau tronçon routier, où le placeriez-vous  et pourquoi ? Quel serait son impact sur les performances globales et les situations locales ?

exokansky

1.2 Données, questions de recherche et méthodes

Les données liées aux réseaux techniques concernent essentiellement les coordonnées (des sommets), les tracés (des lignes), la capacité de charge du réseau et le trafic porté par le réseau. Ainsi, un réseau routier sera classiquement représenté par des voies (liens), des carrefours (sommets), des capacités (mesurées par le type de route, la vitesse limite etc.) et des données de trafic. La représentation se fait par un graphe planaire, valué et le plus souvent spatialisé. L’accès à ces données a longtemps été difficile voire payant (ex. matrice des distances entre communes françaises). Les données sur les trafics peuvent également être d’accès difficile. Par ailleurs, le passage du réseau réel au graphe (nécessairement simplifié) suppose une série de choix qui ne sont pas toujours explicités (quels tracés sont retenus comme liens ? quels carrefours sont retenus comme sommets ?)

Les principales questions de recherche concernent l’accessibilité des sommets, l’efficacité du réseau, sa vulnérabilité et son aménagement. Contrairement à la sociologie, il est en effet fréquent que l’analyse des réseaux techniques serve à préconiser la modification du réseau étudié (aspect applicatif fort), ce qui suppose la prise en compte des coûts associés (créer un tronçon de TGV a un coût largement supérieur à l’ajout d’un-e ami-e sur facebook…). Il y a une tension entre efficacité du réseau et équité territoriale. À noter également que les réseaux techniques sont généralement redondants (existence de plusieurs chemins entre sommets voire multiplexité des liens) afin de gérer le mieux possible les aléas. Cette redondance rend les réseaux techniques plus complexes, plus coûteux mais permet un fonctionnement correct même en cas de perturbations récurrentes (cf le cas du métro parisien qui est dans les parties les plus denses un multigraphe non planaire).

Les méthodes classiques d’analyse sont le calcul d’indices (ceux de Kansky ou d’autres) avant et après un changement (réel ou projeté), la simulation de trafic et l’analyse multivariée des indicateurs calculés – voir l’article de Muraco. Les études plus récentes sur la vulnérabilité (cf Lhomme, 2012) utilisent des méthodes proches dans la mesure où il s’agit de mesurer l’efficacité d’un réseau avant et après la suppression d’un sommet ou d’un lien.

1.3 Adaptations récentes

Trois tendances récentes peuvent être signalées :

  • la prise en compte du multiniveau pour calculer des accessibilités plus proches des pratiques réelles et prenant en compte l’intermodalité – utilisation de plusieurs réseaux lors des déplacements (Chapelon, 1996) ;
  • la différenciation des effets spatiaux et des effets réseaux (Gleyze, 2007) ;
  • l’utilisation des outils de modélisation et de simulation (déplacements, gestion des risques). Ce dernier aspect était déjà présent dans Kansky mais il a été grandement facilité par le développement des logiciels et des capacités informatiques.

Exemple des plate-formes Netlogo et Gama (les 2 sont gratuites et en open-source) :

  • Netlogo : modèle Traffic grid (« This is a model of traffic moving in a city grid. It allows you to control traffic lights and global variables, such as the speed limit and the number of cars, and explore traffic dynamics ») ;
  •  Projet Miro2 : modéliser les déplacements dans une ville moyenne.

Ces simulations multi-agents commencent par définir un cadre (en géographie, un espace), une population d’agents dont les règles de comportements sont fixées puis étudient les propriétés émergentes obtenues par l’agrégation de ces comportements individuels. Les propriétés d’ensemble du système obtenu ne peuvent généralement pas être déduites simplement des propriétés individuelles des agents, d’où le terme de système complexe. Comme toute modélisation, l’objectif n’est pas de reproduire la réalité mais de mieux la comprendre en partant de quelques règles simples (d’où l’injonction KISSKeep it simple, stupid – des modélisateurs).

Il faut enfin signaler l’impact des modèles développés en physique et en mathématiques à la fin des années 90 (cf cours 4 et l’article Ducruet et Beauguitte, 2013) avec deux tendances : les importations, plus ou moins maîtrisées selon les auteur-e-s, de méthodes (chercher à déterminer si tel ou tel réseau est small-world et/ou scale-free – les réseaux techniques obéissant rarement à ces modèles en raison des contraintes topographiques) et la substitution (études de réseaux techniques par les seuls physiciens, cf notamment Barthelemy, 2010).

2 L’analyse des flux

Le flux, dans le manuel devenu classique de Denise Pumain et Thérèse Saint-Julien est défini ainsi : « mesure d’interaction spatiale obtenue par l’addition de déplacements individuels ou de quantités matérielles échangées entre deux zones géographiques pour une durée donnée » (Pumain et Saint-Julien, 2001, p. 14). Contrairement à une certaine géographie classique s’intéressant d’abord aux lieux, c’est ici l’interaction entre lieux qui est au centre des réflexions. On peut distinguer trois types d’approches : les indicateurs obtenus en partant d’une matrice de flux origine – destination ; les méthodes visant à simplifier les flux et enfin les modèles cherchant à les expliquer (voir le TD2 pour un exemple d’application de ces trois approches).

2.1 Manipulation de matrices et indicateurs basiques

Soit une matrice (généralement carrée mais pas nécessairement, et le plus souvent asymétrique) origine – destination entre les lieux i et j et des cases contenant le volume émis par un lieu vers un autre. On note Fi. la capacité d’émission de i et F.j la capacité de réception de j. Le calcul des marges en lignes et en colonnes permet de calculer pour chacun des lieux les indicateurs suivants :

  • volume des échanges du lieu i : Fi. + F.i
  • solde des échanges du lieu i : F.iFi. (solde migratoire, balance commerciale etc.)
  • taux de couverture : Fi. / F.i (peut servir à mesurer l’attractivité des lieux)
  • probabilité d’envoi de i vers j : Fij / Fi.
  • probabilité de réception de j depuis i : Fij / F.j
  • intensité des échanges de i vers j : Fij / (Fi. x F.j)
  • indice de dissymétrie des flux de i : (F.i – Fi.) / (Fi. + F.i)
  • volume total des échanges : Fij + Fji
  • solde total des échanges : FijFji

2.2 Flux dominants et flux majeurs

La méthode des flux dominants a été proposée par Nystuen et Dacey en 1961 (voir ce billet). Un lieu i est dit dominant par rapport à un lieu j si :

  • le flux le plus important émis par j est à destination de i ;
  • le volume total reçu par i est supérieur au volume total reçu par j.

La méthode crée un arbre (ou une forêt) couvrant orienté (mais des lieux peuvent se retrouver isolés) et met en évidence des lieux dominés, des relais et des lieux dominants. Comme toute méthode, elle a ses limites : elle garde un seul flux pour tous les lieux or l’écart peut être important entre ces flux, et deux flux émis par un même lieu peuvent être très proches en volume.

Les méthodes de flux majeurs sont un assouplissement de la méthode des flux dominants dans la mesure où l’on prend en compte soit les x premiers flux émis par lieu ; soit les flux représentant plus de x % du volume total, soit une subtile combinaison des deux. Considérer les x premiers flux de tous les lieux peut ne pas avoir beaucoup de sens (les lieux étant généralement très fortement hiérarchisés, les flux le sont aussi), et ne considérer que les flux les plus importants en volume du total entraîne généralement un grand nombre d’isolés. Se pose ensuite le problème de la représentation qui peut définir problématique, surtout si l’on projette les liens majeurs sur un fond de carte (voir cours 6).

2.3 Modèles gravitaires

Pour cette partie, je me permets de renvoyer au cours en ligne de Claude Grasland. Seuls les principes de base et les principales formules sont rappelés ici.

La famille des modèles gravitaires – ou d’interaction spatiale – cherche généralement à valider trois hypothèses complémentaires :

  • l’interaction entre deux lieux décroît quand la distance entre eux augmente ;
  • l’interaction entre deux lieux est fonction de leurs masses : à distance égale, les échanges sont plus importants entre deux lieux de masse plus importantes ;
  • l’interaction entre les lieux est fonction de l’appartenance à une même entité (politique, culturelle, linguistique etc.).

Les cadres conceptuels peuvent être différents : modèle économique (Zipf) et loi du moindre effort ; modèle psychologique (Hägerstrand) et connaissance plus grande des espaces proches ; modèle sociologique (Stouffer) et rôle des opportunités interposées.

L’un des premiers modèles proposés est celui de Ravenstein (1885) qui vise à expliquer l’attractivité migratoire des lieux à l’aide de la formule suivante :

Fij = Pj / dij

Fij est le nombre de migrants venus de i vers j ; Pj la population de la ville j (considérée comme un proxy de son attractivité) et dij la distance entre i et j.

Reilly en 1931 (The law of retail gravitation) propose un modèle de potentiel (plus que d’interaction) visant à définir les aires d’attraction commerciale des villes.

dxj = dij / (1 + √Pi/Pj)* – je recommande de regarder plutôt les formules sur le diaporama, Hypotheses ne permet pas encore l’utilisation du LaTeX dans les billets.

avec dij distance entre i et j, dxj distance entre x (point d’équilibre) et j, Pi et Pj les populations des villes i et j. Le résultat est une partition de l’espace considéré sans zone de recouvrement. D’autres modèles (modèle de Huff notamment) raisonnent en terme de probabilité et autorisent les zones de recouvrement.

Le modèle de Stewart et Zipf (1941) vise également à définir les potentiels d’attractivité des villes et reprend explicitement le modèle de Newton. On a eu effet :

Fij = k.Pi.Pj / dij2

Fij est le flux entre i et j, k une constance exprimant le niveau global de mobilité, Pi et Pj la population des lieux i et j et dij la distance entre i et j. L’exposant de la distance est nommé frein de la distance et peut varier en fonction du type de mobilité étudié.

Différents modèles (fonction puissance de la distance et fonction exponentielle) et différentes méthodes d’ajustement (log linéaire, régression de Poisson) ont ensuite été proposés. Si les modèles diffèrent au niveau statistique, le principe reste le même : trouver le modèle le plus économique et le plus explicatif, interpréter les coefficients des variables introduites, étudier les résidus positifs et négatifs (cf TD2).

Deux articles

Muraco, 1972 : un article devenu un classique sur l’accessibilité intra-urbaine.

Drevelle, 2012 : article récent d’un jeune géographe utilisant les flux majeurs et le blockmodeling (cf cours 2) pour étudier les navettes domicile-travail.

  • Quelles sont les questions de recherche ?
  • Quelles sont les données utilisées ?
  • Quelles sont les méthodes mobilisées ?
  • Quels sont les principaux résultats
  • Quel est le statut et le type d’illustrations utilisées ?

Références

Marc Barthelemy, 2001, Spatial networks, Physics Reports, 2011, vol. 499, no 1, p. 1-101, http://arxiv.org/abs/1010.0302

Laurent Chapelon, 1996, Modélisation multi-échelles des réseaux de transport. Vers une plus grande précision de l’accessibilité, M@ppemonde

Pascale Dancoisne, 1984, Théorie des graphes et constitution du réseau ferré français, Thèse de géographie, Paris 1 (thèse passionnante et très pédagogue, malheureusement non éditée donc difficile d’accès)

César Ducruet et Laurent Beauguitte. « Spatial science and network science: Review and outcomes of a complex relationship. » Networks and Spatial Economics (2014): 1-20 (revue d’accès payant mais le texte se trouve facilement sur internet)

Jean-François Gleyze, 2007, Effets spatiaux et effets réseau dans l’évaluation d’indicateurs sur les nœuds d’un réseau d’infrastructure, Cybergeo : European Journal of Geography, http://cybergeo.revues.org/5532

Serge Lhomme, 2012, L’analyse structurelle des réseaux techniques : modélisations, propriétés, vulnérabilités, collection fmr

John D. Nystuen et Michael F. Dacey, 1961, A graph theory interpretation of nodal regions, Papers and Proceedings of the Regional Science Association, vol. 7, p. 29-42

Denise Pumain et Thérèse Saint-Julien, 2001, Les interactions spatiales, Armand Colin