Access graph: a novel graph representation of public transport networks for accessibility analysis

1. Problem Statement

Accessibility, defined as the travel impedance between spatially dispersed opportunities, is a critical determinant of public transport (PT) usage and urban planning. However, the field lacks a unified approach to measuring accessibility. Existing methods face several challenges:

• Operationalization Variance: Definitions of travel impedance and opportunity counts vary significantly across studies, making cross-network comparisons difficult.
• Limitations of Standard Graphs: Traditional PTN representations (L-space/infrastructure and P-space/service) are insufficient for accessibility analysis. L-space captures infrastructure but ignores transfer behavior; P-space captures non-transfer travel but abstracts spatial constraints. Neither fully captures the "generalized travel time" (in-vehicle time + waiting time + transfer penalties) required for a holistic accessibility view.
• Metric Interpretability: Centrality measures (e.g., closeness) often provide local node-level insights that do not translate well to global accessibility properties or equity analysis.
• Lack of Unified Framework: There is a need for a network-science-based framework that models access at the network structure level rather than just aggregating individual trip metrics.

2. Methodology: The Access Graph (A-space)

The authors propose a novel graph representation called the Access Graph (A-space), which models accessibility as a function of a time budget ($t_b$).

A. Construction of the Access Graph

1. Input Data: The method utilizes standard GTFS data to construct weighted L-space (infrastructure) and P-space (service) representations.
2. Generalized Travel Time Matrix ($D$): A matrix is computed where the weight $d_{ij}$ represents the generalized travel time between stops $i$ and $j$. This incorporates:
   • In-vehicle time ($t_{in-veh}$).
   • Waiting time ($t_{wait}$), derived from service frequency ($30/f_{ij}$).
   • Transfer penalties ($w_{transfer}$), weighted empirically (e.g., 5 minutes per transfer).
   • Formula: $D = D_{L}^{in-veh} + w_{wait}D_{P}^{wait} + w_{transfer}(D_{P}^{u} - J_N)$.
3. Graph Generation: For a specific time budget $t_b$, an edge exists between nodes $i$ and $j$ if and only if $d_{ij} \leq t_b$.
   • At $t_b = 0$, the graph is empty.
   • At $t_b = t_{max}$ (maximum travel time in the network), the graph becomes a complete clique.
   • The resulting graph is undirected and unweighted, where node degree ($k$) directly equals the number of reachable nodes (cumulative opportunities) within the time budget.

B. Proposed Indicators

The study analyzes the evolution of the Access Graph as $t_b$ increases, defining two categories of indicators:

1. System Performance Indicators (Dual Access):

• $t_M$ (Access Inflection Point): The time budget where the average degree growth ($\langle k \rangle'$) is maximized. This represents a "phase transition" where the network shifts from sparse to highly connected.
• $\delta t_M$: The normalized inflection point ($t_M / t_{max}$).
• $\langle k \rangle_M$: The average degree at the inflection point.
• $t_{JS}$ (Structural Change Point): The time budget where the Jensen-Shannon Divergence (JSD) between consecutive degree distributions is maximized. This captures the most significant structural reorganization of the network.

2. Passenger Perspective Indicators (Primal Access):

• $\langle k \rangle_{30}$: The average degree at a fixed $t_b = 30$ minutes (a standard commute threshold).
• $G_{30}$: The Gini coefficient of the degree distribution at $t_b = 30$ min, measuring access inequality.

3. Equity Indicators:

• $G_M$ and $G_{30}$: Gini coefficients calculated at the inflection point and 30-minute mark, respectively, to quantify disparities in access across the network.

3. Key Contributions

1. Novel Representation (A-space): Introduces a time-budget-dependent graph representation where edges represent functional reachability rather than physical or service connections.
2. Unified Framework: Provides an algorithmic, interpretable approach to accessibility that unifies network science with transport planning, allowing for direct comparison across different cities and network sizes.
3. New Indicators: Defines a set of global indicators ($t_M, \delta t_M, \langle k \rangle_{30}, G_M$, etc.) that capture both system performance (how fast the network connects) and equity (how evenly access is distributed).
4. Empirical Validation: Applies the methodology to a dataset of 51 metro networks worldwide, demonstrating the robustness and scalability of the approach.

4. Results and Analysis

The methodology was applied to 51 metro systems (ranging from small networks like Genoa, $N=8$, to large ones like New York, $N=421$).

• Network Evolution: Most networks exhibit a sigmoid (S-shaped) growth in average degree. The inflection point ($t_M$) typically occurs between 25–35 minutes for many networks, aligning with passenger time budgets.
• Case Study (Oslo vs. Vienna):
  • Vienna showed a more regular, unimodal degree distribution and earlier structural changes, indicating higher accessibility and equity.
  • Oslo exhibited a bimodal distribution and a later inflection point ($\delta t_M = 0.64$), suggesting a "core-periphery" structure where the core connects quickly but the periphery lags, resulting in lower equity.
• Correlations:
  • Network Size ($N$) vs. Accessibility: Larger networks tend to have higher maximum travel times ($t_{max}$) but show sub-linear scaling, suggesting larger networks are relatively more efficient.
  • Inequality: The Gini coefficient ($G_{30}$) generally increases with network size, indicating that larger networks tend to have higher disparities in access. However, normalized indicators like $\delta t_M$ provide size-independent measures of performance.
  • Structural Change: The largest structural reorganization (peak JSD) often occurs earlier than the inflection point of average degree, suggesting that the network topology changes significantly before the average connectivity saturates.

5. Significance and Future Directions

• Planning Utility: The Access Graph offers planners a tool to identify "access deserts" and simulate the impact of network changes (e.g., new lines or frequency adjustments) on global accessibility and equity.
• Interpretability: By reducing complex travel data to node degrees in a time-dependent graph, the method yields highly interpretable metrics that are reproducible across different PT modes (bus, rail, etc.).
• Limitations & Future Work:
  • The current model assumes a uniform number of opportunities per stop; future work should integrate land-use data to weight nodes by actual opportunity density.
  • The model uses a hard cut-off for edges; future iterations could explore probabilistic edge inclusion or fuzzy thresholds to account for passenger heterogeneity.
  • The framework is a stepping stone toward multilayer network analysis, potentially incorporating financial costs or perceived accessibility as separate layers.

In conclusion, the paper successfully bridges the gap between network science and accessibility planning by introducing a unified, graph-theoretic framework that quantifies both the efficiency and equity of public transport systems.