Calculer des mesures de centralité avec le réseau de transport en commun parisien

Benjamin Geer
2025-08-29

English: Calculating centrality indices with the Paris public transport network

Table des matières

J’ai pensé qu’il serait intéressant d’essayer un peu d’analyse de réseau élémentaire en utilisant le réseau du métro et du RER parisiens, en commençant par des indices de centralité. Il s’agit de mesures qui classent les sommets d’un graphe en fonction de leur importance, selon une définition quelconque de l’importance. Par exemple, dans un réseau de transport, la centralité d’une station pourrait donner une indication de la probabilité que les passagers passent par cette station au cours de leur itinéraire. Un opérateur de transports en commun pourrait utiliser ces informations pour évaluer les inconvénients que causerait la fermeture de certaines stations, par exemple en raison d’inondations ou de travaux, et pour l’aider à identifier les moyens les plus efficaces d’améliorer la résilience du réseau. J’utiliserai ici Python, networkx et SQLite.

Construire le graphe #

J’ai choisi ici de faire un seul graphe qui comprend le métro et le RER. Le premier problème est de construire ce graphe en établissant la liste de liens et la liste de sommets. Les établissements qui régissent les transports en commun parisiens ne fournissent pas de tel jeu de données, mais ils fournissent un jeu de données GTFS qui représente les horaires prévus sur toutes les lignes de transport pendant les 30 prochains jours. (Je tiens à remercier Oliver Blanthorn de me l’avoir signalé.) Les données GTFS représentent les courses (les séquences d’arrêts) que les trains devraient parcourir sur les lignes de métro ou de RER. Pour construire la liste de liens du réseau, nous pouvons parcourir chaque course, en enregistrant un lien entre chaque arrêt et l’arrêt suivant. Certaines courses vont dans une direction, d’autres dans la direction inverse, et beaucoup ne comprennent pas tous les arrêts de la ligne, mais en les parcourant toutes, nous devrions accumuler un graphe orienté complet du réseau. Il faudra parcourir environ 64 000 courses, qui comprennent au total presque 1,5 million d’arrêts, et une grande partie des données sera redonante pour nous, mais cela n’a pas d’importance tant que le traitement des données ne prend pas trop de temps.

Il s’agit donc de réaliser un procédé ETL (Extract, transform, load). D’abord j’ai créé un script shell qui télécharge les données GTFS, ainsi que plusieurs fichiers d’un jeu de données qui s’appelle Référentiel des lignes de transport en commun d’île-de-France, dont nous aurons également besoin. Comme tous ces fichiers sont au format CSV et utilisent des identifiants uniques pour relier les données des différents fichiers, notre tâche sera plus facile si nous utilisons une base de données relationnelle. Dans un deuxième script shell, j’importe les fichiers pertinents dans une base de données intermédiaire gérée par SQLite et je crée quelques index pour accélérer les requêtes de l’étape de transformation. Ce script s’exécute en 21 secondes environ sur mon ordinateur portable et la taille de la base de données obtenue est de 2,1 Go.

Enfin, j’ai créé un script Python pour les étapes de transformation et de chargement. Il lit la base de données intermédiaire et construit la base de données de sortie, qui ne contient que la table de liens et la table de sommets. Comme la base de données de sortie est petite (132 Ko), le script la crée en mémore pour améliorer la performance de cette étape, puis la sauvegarde quand elle est complète. L’exécution de ce script prend environ 8 secondes.

Dans le Référentiel, les liens entre le métro et le RER sont représentés par des zones de correspondance et des pôles d’échange, qui peuvent comprendre plusieurs stations reliées par des couloirs. Pour inclure ces relations dans le graphe, j’ai choisi d’ajouter des liens entre toutes les stations faisant partie du même groupe.

La base de données de sortie représente un multigraphe orienté, puisque deux stations peuvent être reliées par plusieurs lignes. Dans un tel cas, nous pouvons considérer que les deux stations en question ont un lien plus fort que deux stations qui ne sont reliées que par une seule ligne. Toutes choses étant égales par ailleurs, plus il y a de lignes entre deux stations, plus il y aura de passagers qui voyagent entre les deux. Nous conserverons ces informations sur les liens multiples en faisant nos calculs.

Visualiser des parties du graphe #

Visualisons d’abord une partie des données pour vérifier qu’elles sont correctes. Nous pouvons créer une fonction qui affiche le graphe d’un réseau de transport. Ici, nous nous intéressons uniquement aux sommets et aux liens, et non pas à leur position géographique. Pour repérer facilement les lignes, nous pouvons utiliser les couleurs précisées pour le plan du réseau, qui se trouvent dans le jeu de données GTFS, ainsi que le noir pour les liens que j’ai ajoutés pour les zones de correspondance et les pôles d’échange.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


%config InlineBackend.figure_formats = ['svg']
import sqlite3
import pandas as pd
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
import itertools as it


def draw_graph(G, title, height, label_x_offset):
    plt.figure(figsize=(12, height))
    plt.margins(x=0.18, y=0)
    plt.title(title)

    pos = nx.nx_agraph.graphviz_layout(G, prog="dot")

    # See https://networkx.org/documentation/stable/auto_examples/drawing/plot_multigraphs.html
    connectionstyle = [f"arc3,rad={r}" for r in it.accumulate([0.15] * 4)]

    nx.draw_networkx_nodes(G, pos, node_size=30, node_color="#000000")

    edge_colors = [
        f"#{G[source_node_id][target_node_id][edge_key]["route_color"]}"
        for source_node_id, target_node_id, edge_key in G.edges
    ]

    nx.draw_networkx_edges(
        G, pos, edge_color=edge_colors, connectionstyle=connectionstyle
    )

    label_pos = {
        node_id: (node_pos[0] + label_x_offset, node_pos[1])
        for node_id, node_pos in pos.items()
    }

    text = nx.draw_networkx_labels(
        G,
        label_pos,
        labels=nx.get_node_attributes(G, "node_name"),
        horizontalalignment="left",
        verticalalignment="bottom",
        font_size=6,
    )

    for _, t in text.items():
        t.set_rotation(15)

Essayons avec les lignes de métro 1 et 4 et le RER A:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50


DATABASE = "../../../notebook-data/paris-rail-data/paris-graph.db"

conn = sqlite3.connect(f"file:{DATABASE}?mode=ro")

nodes = pd.read_sql_query(
    """select distinct
        nodes.node_id, nodes.node_name
    from nodes
    inner join edges on
        nodes.node_id = edges.source_node_id or
        nodes.node_id = edges.target_node_id
    where
        (edges.route_type = 1 and edges.route_name = '1') or
        (edges.route_type = 1 and edges.route_name = '4') or
        (edges.route_type = 2 and edges.route_name = 'A') or
        (edges.route_type is null and
            (edges.route_name = 'PdE Châtelet - Les Halles' or
            edges.route_name = 'ZdC Gare de Lyon'))""",
    conn,
    index_col="node_id",
)

edges = pd.read_sql_query(
    """select * from edges where
        (edges.route_type = 1 and edges.route_name = '1') or
        (edges.route_type = 1 and edges.route_name = '4') or
        (edges.route_type = 2 and edges.route_name = 'A') or
        (edges.route_type is null and
            (edges.route_name = 'PdE Châtelet - Les Halles' or
            edges.route_name = 'ZdC Gare de Lyon'))""",
    conn,
).replace({np.nan: None})

G = nx.from_pandas_edgelist(
    edges,
    source="source_node_id",
    target="target_node_id",
    edge_attr=True,
    create_using=nx.MultiDiGraph(),
)

node_attributes = nodes.to_dict(orient="index")
nx.set_node_attributes(G, node_attributes)

draw_graph(
    G,
    title="Les lignes de métro 1 et 4 et le RER A",
    height=20,
    label_x_offset=6,
)

svg

Cela semble correct.

Visualiser les résultats #

Les fonctions proposées par networkx pour le calcul des mesures de centralité renvoient un dictionnaire dont les clés sont des identifiants de sommet et dont les valeurs sont des scores de centralité. Nous pouvons créer une fonction qui accepte un tel dictionnaire et affiche un diagramme à barres des 25 stations les plus importantes par ordre décroissant de centralité.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


def centrality_chart(centrality_dict, title):
    names_and_scores = [
        (node_attributes[item[0]]["node_name"], item[1])
        for item in centrality_dict.items()
    ]

    top_25 = sorted(names_and_scores, key=lambda t: t[1], reverse=True)[:25]

    top_25_df = pd.DataFrame(
        top_25,
        columns=["Station", "Score de centralité"],
    ).set_index("Station")

    ax = top_25_df.plot.barh(title=title)
    ax.invert_yaxis()

La centralité de degré #

Lisons d’abord l’intégralité du graphe :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


nodes = pd.read_sql_query(
    "select * from nodes",
    conn,
    index_col="node_id",
)

edges = pd.read_sql_query(
    "select * from edges",
    conn,
).replace({np.nan: None})

conn.close()

G = nx.from_pandas_edgelist(
    edges,
    source="source_node_id",
    target="target_node_id",
    edge_attr=True,
    create_using=nx.MultiDiGraph(),
)

node_attributes = nodes.to_dict(orient="index")
nx.set_node_attributes(G, node_attributes)
print(f"{len(G.nodes)} sommets et {len(G.edges)} liens chargés.")

563 sommets et 1363 liens chargés.

La mesure de centralité la plus simple est la centralité de degré : pour chaque sommet, nous pouvons compter ses liens entrants ou sortants et normaliser le résultat en le divisant par $n - 1$, où $n$ est le nombre de sommets. Dans ce cas présent, les resultats sont les mêmes pour la centralité de degré entrant et la centralité de degré sortant.

1
2


in_degree_centrality_dict = nx.in_degree_centrality(G)
centrality_chart(in_degree_centrality_dict, "Centralité de degré entrant")

svg

On voit tout de suite que les stations ayant les scores le plus élevés sont surtout des stations de métro plutôt que des stations RER. Une explication possible serait la structure apparemment plus radiale du réseau RER par rapport au métro. En plus d’être situées sur plusieurs lignes, plusieurs de ces stations (telles que Havre-Caumartin) font partie d’un pôle d’échange.

La centralité de vecteur propre #

Avec la centralité de vecteur propre, chaque sommet reçoit un score proportionnel à la somme des scores de ses voisins. Un sommet peut ainsi obtenir un score élevé en ayant beaucoup de voisins et/ou en ayant des voisins dont le score est élevé. Dans un graphe non orienté à $n$ sommets, la centralité de vecteur propre $x_i$ d’un sommet $i$, dont l’ensemble des voisins est $M(i)$, est définie par :

$$ x_i = \frac{1}{\lambda} \sum_{j \in M(i)} x_j $$

où $\lambda$ est une constante. Nous pouvons écrire cette équation en utilisant la matrice d’adjacence $A$ du réseau, dans laquelle $a_{ij}$ est égal à 1 s’il y a un lien entre les sommets $i$ et $j$ et à 0 s’il n’y en a pas :

$$ x_i = \frac{1}{\lambda} \sum_{j = 1}^n a_{ij} x_j $$

Cela équivaut à :

$$ \mathbf{x} = \frac{1}{\lambda} A\mathbf{x} $$

où $\mathbf{x}$ est un vecteur dont les éléments sont les scores de centralité. On peut donc écrire :

$$ A\mathbf{x} = \lambda\mathbf{x} $$

Il s’ensuit que $\lambda$ est une valeur propre de $A$ et que $\mathbf{x}$ est le vecteur propre correspondant. Étant donné les valeurs propres et les vecteurs propres de la matrice, il est simple de choisir le vecteur propre pertinent, car (selon le théorème de Perron-Frobenius), pour une matrice (comme la matrice d’adjacence) qui n’a pas d’éléments négatifs, seul le vecteur propre associé à la plus grande valeur propre peut être choisi de façon à ce qu’il n’ait pas d’éléments négatifs. Avec un graphe orienté comme notre réseau de transport, on peut choisir un vecteur propre à gauche ou un vecteur propre à droite. On préfère d’habitude le vecteur propre à gauche (et c’est ce que fait networkx), de sorte que le score d’un sommet dépend de ses liens entrants plutôt que de ses liens sortants. Cela ne change pas grand-chose dans le cas présent, car presque tous les liens entrants de notre réseau ont un lien sortant correspondant.

Lorsque la centralité de vecteur propre est utilisée avec un graphe orienté, celui-ci doit être fortement connexe. C’est le cas de notre réseau de transport, car chaque station est accessible depuis toutes les autres :

1

nx.is_strongly_connected(G)

True

Nous utiliserons ici la fonction networkx.eigenvector_centrality_numpy, qui construit d’abord la matrice d’adjacence. Dans un multigraphe orienté comme le nôtre, s’il y a $n$ liens allant dans le même sens entre deux sommets, networkx les représente par la valeur $n$ dans la matrice, ce qui équivaut à un seul lien d’intensité $n$. Ensuite il obtient le vecteur propre pertinent et renvoie un dictionnaire qui contient chaque identifiant de sommet et l’élément correspondant du vecteur propre.

1
2


eigenvector_centrality_dict = nx.eigenvector_centrality_numpy(G)
centrality_chart(eigenvector_centrality_dict, "Centralité de vecteur propre")

svg

Si on compare ces résultats à ceux obtenus pour la centralité de degré, on peut constater que la station Havre-Caumartin, qui se trouve au milieu du pôle d’échange Paris Saint-Lazare - Opéra (qui comprend six stations), obtient un score plus élevé parce qu’elle est adjacente à deux stations, Saint-Lazare et Opéra, qui ont des scores élevés. Plusieurs autres stations, dont Saint-Augustin, Auber et and Haussmann Saint-Lazare, obtiennent des scores plus élevés pour la même raison.

La centralité d’intermédiarité #

La centralité d’intermédiarité compte le nombre de fois où un sommet se trouve sur un des plus courts chemins (c’est-à-dire qui traversent le moins de sommets possible) entre chaque paire d’autres sommets. Pour un sommet $v$, elle est définie par :

$$ c_B(v) =\sum_{s \neq v \neq t} \frac{\sigma(s, t|v)}{\sigma(s, t)} $$

où $s$ et $t$ sont n’importe quels autres sommets du réseau, $\sigma(s, t)$ est le nombre de plus courts chemins de $s$ à $t$ et $\sigma(s, t|v)$ est le nombre de ces chemins qui passent par $v$. Dans un réseau de transport, un station dont $c_B(v)$ a une valeur élevée est une station par laquelle beaucoup de passagers passeront probablement s’ils choissisent un des plus courts chemins menant à leur destination.

1
2


betweenness_centrality_dict = nx.betweenness_centrality(G)
centrality_chart(betweenness_centrality_dict, "Centralité d’intermédiarité")

svg

La plupart des stations figurant sur cette liste sont des stations RER plutôt que des stations de métro, ce qui est logique, car le RER couvre une plus grande distance entre les arrêts. Ainsi, si le même trajet peut être effectué en métro ou en RER, le trajet le plus court sera généralement celui en RER. Il n’est pas surprenant de voir Châtelet les Halles en tête de liste, compte tenu de sa situation géographique centrale et du grand nombre de lignes qui passent par son pôle d’échange. Il semble qu’il y ait aussi d’autres configurations qui peuvent donner un score élevé à une station. Par exemple, Juvisy se trouve sur un long tronçon du RER C où il y a peu de correspondances, et elle est reliée à un tronçon semblable du RER D. Il semble donc probable que beaucoup de plus courts chemins doivent passer par cette station.

Conclusion #

Ceci n’est qu’une brève exploration de quelques mesures de centralité pour ce réseau, avec quelques exemples illustrant comment différentes définitions de l’importance d’un sommet peuvent donner lieu à des scores différents. Tous les scripts utilisés ici se trouvent dans le dépôt Git de ce blog, ainsi que le calepin Jupyter à partir duquel j’ai généré cette page. N’hésitez pas à me contacter pour toute question ou suggestion.

Catégories :

Tutoriels

Sujets :