pith. sign in

arxiv: 2604.02675 · v1 · submitted 2026-04-03 · 🧮 math.OC

Data-driven identification of critical links in transport networks using quantum annealing

Junxiang Xu , Chence Niu , Tingting Zhang , Divya Jayakumar Nair , Vinayak Dixit This is my paper

Pith reviewed 2026-05-13 19:39 UTC · model grok-4.3

classification 🧮 math.OC
keywords critical linkstransport networksquantum annealingQUBOtime-dependent analysisnetwork resiliencetraffic data
0
0 comments X p. Extension

The pith

Critical links in urban transport networks concentrate in a small number of key time windows.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper builds a framework that treats identification of critical links as a time-varying optimization task on real traffic data. It encodes the problem as a quadratic unconstrained binary optimization model and solves it with quantum annealing on D-Wave hardware. The resulting analysis shows that critical links do not affect performance steadily across the day but instead cluster inside a few short time windows. Inside those windows even modest link failures produce large increases in total network delay. This matters because static or averaged network studies overlook these concentrated vulnerability periods and therefore understate the timing of risk.

Core claim

By casting time-dependent critical-link identification as a QUBO whose objective sums the extra delay caused by removing each candidate link in each time slice, and by solving the resulting instances with quantum annealing on observed traffic counts, the study finds that the links with highest impact appear predominantly inside a limited set of key time windows rather than persisting throughout the day.

What carries the argument

A QUBO model that scores each link's removal by its contribution to total network delay in each discrete time period, solved by quantum annealing hardware.

If this is right

  • Network risk screening can be narrowed to monitoring and protecting a handful of short time periods instead of the full schedule.
  • Resilience planning gains precision by targeting interventions exactly when critical links are active.
  • Time-averaged analyses systematically underestimate the delay amplification that occurs inside the concentrated windows.
  • The quantum-annealing formulation allows the same model to be applied to city-scale networks where exhaustive classical enumeration becomes impractical.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same temporal-concentration pattern could be tested in other time-varying networks such as power grids or communication systems.
  • Demand-forecast data could be fed into the identical QUBO to predict future critical windows ahead of time.
  • Maintenance crews and emergency resources might be pre-positioned according to the recurring windows rather than uniform schedules.

Load-bearing premise

The QUBO objective function correctly encodes the true time-dependent delay impact of removing any given link.

What would settle it

A side-by-side run on the same data instances in which an exact classical solver returns link sets that lack the reported temporal concentration, or field observations showing large delay spikes from disruptions falling outside the predicted windows.

Figures

Figures reproduced from arXiv: 2604.02675 by Chence Niu, Divya Jayakumar Nair, Junxiang Xu, Tingting Zhang, Vinayak Dixit.

Figure 1
Figure 1. Figure 1: Spatial distribution of node latitude and longitude in the dataset used in this study. Further, this study examines network connectivity to determine whether isolated sub networks or disconnected structures exist. The results show that the network is fully connected, meaning that all nodes [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: , all nodes in the network fall within one giant connected component. This connectivity ensures the validity of the subsequent critical link identification analysis and avoids structural bias caused by data fragmentation [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Data-driven mapping from observed traffic data to the QUBO model (This Figure was produced with assistance from Gemini Pro). On this basis, the network delay index is evaluated under different disruption combinations to obtain single link impact coefficients and inter link interaction coefficients. These coefficients are then incorporated into the QUBO energy function at each corresponding time step, toget… view at source ↗
Figure 5
Figure 5. Figure 5: Occurrence frequency distribution of critical links over the full observation period [PITH_FULL_IMAGE:figures/full_fig_p015_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Spatial evolution of the network critical link identification structure. 4.3.3 Time-dependent network delay index As shown in [PITH_FULL_IMAGE:figures/full_fig_p018_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Time-dependent network delay index under different disruption scales. Further inspection reveals that the NDI u t ( , ) curves associated with different disruption scales exhibit clear differences in the timing of peak values, the magnitude of fluctuations, and local variation patterns over time. This suggests that disruption scale not only affects the absolute level of network delay index but also alters … view at source ↗
Figure 8
Figure 8. Figure 8: Identification of high-risk time windows based on NDI u t ( , ) ( k = 20 ). (2) Analysis of change rate in network delay index As shown in [PITH_FULL_IMAGE:figures/full_fig_p020_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Temporal variation of changes in the worst-case Network Delay Index ( k = 20 ) [PITH_FULL_IMAGE:figures/full_fig_p020_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Solving time per time step using the hybrid CQM solver ( k = 20 ). (2) Interpretation of worst-case network delay index results The vertical axes in Figures 7 to 9 represent the worst-case network delay index, which directly corresponds to the objective value of the QUBO formulation, namely the minimum energy state. The results indicate that within high-risk time windows, even a limited scale of link fail… view at source ↗
Figure 11
Figure 11. Figure 11: Solving time per time step for different disruption scales. (4) Scope and limitations of the worst-case analysis It should be noted that the worst-case network delay index examined in this study represents an upper-bound performance measure under constrained link disruption scenarios, rather than an estimate of expected or average network conditions. The results are therefore not intended to predict typic… view at source ↗
read the original abstract

In urban transport systems, time-varying demand and network conditions cause the importance of infrastructure elements to evolve, requiring the identification of period-specific critical links to support systemlevel risk and resilience analysis. However, static or time-averaged network analyses struggle to capture the temporal variation of infrastructure importance at the city scale. To address this gap, this study proposes a time-dependent critical link identification framework for large-scale urban transport networks. The problem is formulated as a Quadratic Unconstrained Binary Optimisation (QUBO) model and solved using quantum annealing on D-Wave hardware. Empirical analysis using real-world traffic data reveals a strong temporal concentration of critical links. Rather than persistently influencing system performance, critical links emerge mainly within a small number of key time windows, during which even limited disruptions can lead to substantial network delay amplification. These findings demonstrate the value of time-dependent analysis for risk screening, stress testing, and resilience-oriented transport management.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The manuscript proposes a time-dependent framework for identifying critical links in large-scale urban transport networks. The problem is cast as a QUBO whose objective proxies the marginal delay impact of link removal in each time window; the QUBO is solved on D-Wave quantum annealing hardware. Empirical application to real-world traffic data yields the central claim that critical links exhibit strong temporal concentration, appearing predominantly in a small number of key time windows rather than persistently across the day.

Significance. If the QUBO encoding and annealer solutions are shown to be faithful, the work would supply a scalable, data-driven method for time-varying resilience screening that static or averaged analyses cannot provide. The reported concentration result, if robust, would directly inform targeted risk management and stress-testing protocols. The manuscript does not yet supply the validation steps (exact comparisons, penalty sensitivity, solution quality metrics) needed to establish this utility.

major comments (3)
  1. [§3] Abstract and §3 (QUBO formulation): the linear and quadratic coefficients are stated to encode time-dependent delay amplification, yet no verification is provided that the chosen penalty scaling reproduces the true equilibrium delay difference (pre- vs. post-removal) even on small sub-networks where exact MIP solutions are feasible.
  2. [§4] §4 (computational results): the reported set of critical links is obtained from D-Wave samples, but the manuscript contains no comparison of these samples against classical exact solvers or exhaustive enumeration on modest instances, nor any metric (e.g., energy gap, solution stability across runs) quantifying how close the returned bit strings are to the global QUBO minimum.
  3. [§5] §5 (empirical findings): the claim of strong temporal concentration rests on the argmin sets produced by the annealer; without the validation steps above, it remains possible that the observed clustering into a few time windows is an artifact of the QUBO encoding or hardware bias rather than a genuine network property.
minor comments (2)
  1. [§2] Notation for the time-window index and the delay-impact function should be introduced once and used consistently; several symbols appear without prior definition in the results section.
  2. [Figures 3-5] Figure captions should explicitly state the number of D-Wave runs, the embedding chain length, and the annealing schedule parameters used to generate each panel.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the constructive comments that identify key validation gaps in our QUBO formulation and empirical claims. We will revise the manuscript to incorporate the requested comparisons on small instances and solution-quality metrics, which will allow us to confirm that the observed temporal concentration reflects genuine network properties.

read point-by-point responses

  1. Referee: [§3] Abstract and §3 (QUBO formulation): the linear and quadratic coefficients are stated to encode time-dependent delay amplification, yet no verification is provided that the chosen penalty scaling reproduces the true equilibrium delay difference (pre- vs. post-removal) even on small sub-networks where exact MIP solutions are feasible.

    Authors: We agree that explicit verification against exact solutions is required. In the revised manuscript we will add a new validation subsection to §3. We will extract small sub-networks (10–20 links) from the real traffic data for which the full marginal-delay MIP is tractable. For each such instance we will compute the true pre- and post-removal equilibrium delays via traffic assignment and compare them directly to the QUBO objective value obtained with our chosen penalty scaling. Correlation coefficients and absolute-error statistics will be reported to demonstrate that the encoding faithfully reproduces the delay impact. revision: yes

  2. Referee: [§4] §4 (computational results): the reported set of critical links is obtained from D-Wave samples, but the manuscript contains no comparison of these samples against classical exact solvers or exhaustive enumeration on modest instances, nor any metric (e.g., energy gap, solution stability across runs) quantifying how close the returned bit strings are to the global QUBO minimum.

    Authors: We acknowledge the lack of these benchmarks. The revised §4 will include a dedicated validation subsection. On modest QUBO instances (up to 50 variables) that can be solved to optimality with Gurobi, we will compare D-Wave samples against the exact global minimum in terms of achieved energy, Hamming distance to the optimal bit-string, and success probability. We will also report the average energy gap to the second-best solution and the frequency with which the best bit-string appears across 100 independent annealing runs to quantify solution quality and stability. revision: yes

  3. Referee: [§5] §5 (empirical findings): the claim of strong temporal concentration rests on the argmin sets produced by the annealer; without the validation steps above, it remains possible that the observed clustering into a few time windows is an artifact of the QUBO encoding or hardware bias rather than a genuine network property.

    Authors: With the validations added in response to the first two comments, we will re-evaluate the temporal-concentration claim in the revised §5. On the full network we will retain the D-Wave results but will also present the same concentration analysis performed on representative small sub-networks using exact QUBO solutions. We will compare the critical-link sets and their time-window distributions obtained from exact versus sampled solutions to show that the clustering pattern is preserved. Sensitivity to penalty parameters and any residual hardware bias will be discussed explicitly; if the concentration remains robust under these checks, the claim will be retained with the supporting evidence; otherwise the findings will be appropriately qualified. revision: partial

Circularity Check

0 steps flagged

No significant circularity; empirical pattern derived from external data

full rationale

The paper formulates a QUBO objective from traffic data inputs, solves it via quantum annealing, and reports an observed temporal concentration of critical links in the resulting solutions. No derivation step reduces by construction to a fitted parameter, self-citation chain, or tautological definition; the concentration finding is an output of processing independent real-world data rather than an algebraic identity or renamed input. The QUBO encoding itself is an external modeling choice, not a self-referential loop.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

Only the abstract is available, so the ledger is necessarily incomplete. The QUBO model almost certainly contains tunable penalty weights or scaling factors chosen to balance the objective terms; the graph representation of the network and the definition of link importance are standard domain assumptions.

free parameters (1)
  • QUBO penalty coefficients
    Weights that enforce the binary constraints and balance the delay-amplification term; their specific values are not reported in the abstract.
axioms (1)
  • domain assumption The transport network can be represented as a time-varying directed graph whose link costs are derived from observed traffic counts.
    Standard modeling choice in network flow and resilience studies; invoked implicitly when the problem is cast as QUBO.

pith-pipeline@v0.9.0 · 5465 in / 1417 out tokens · 37538 ms · 2026-05-13T19:39:27.061704+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

  1. [1]

    & You, F

    Ajagekar, A. & You, F. 2019. Quantum computing for energy systems optimization: Challenges and opportunities. Energy, 179, 76-89

    work page 2019

  2. [2]

    & Dodge, S

    Alizadeh, D. & Dodge, S. 2025. Disaster vulnerability in road networks: a data -driven approach through analyzing network topology and movement activity. International Journal of Geographical Information Science, 39, 1035-1056

    work page 2025

  3. [3]

    & Yazici, A

    Almotahari, A. & Yazici, A. 2020. Impact of topology and congestion on link criticality rankings in transportation networks. Transportation Research Part D: Transport and Environment, 87, 102529

    work page 2020

  4. [4]

    & Yazici, A

    Almotahari, A. & Yazici, A. 2021. A computationally efficient metric for identification of critical links in large transportation networks. Reliability Engineering & System Safety, 209, 107458

    work page 2021

  5. [5]

    E., Gao, S., Wei, Z

    Ben-Akiva, M. E., Gao, S., Wei, Z. & Wen, Y. 2012. A dynamic traffic assignment model for highly congested urban networks. Transportation research part C: emerging technologies, 24, 62-82

    work page 2012

  6. [6]

    & Pfeffer, K

    Bodenstein, C.-P. & Pfeffer, K. 2026. Mapping the field of urban infrastructuring—A scoping review. Cities, 169, 106529

    work page 2026

  7. [7]

    & Jenelius, E

    Cats, O. & Jenelius, E. 2014. Dynamic vulnerability analysis of public transport networks: mitigation effects of real-time information. Networks and Spatial Economics, 14, 435-463. de Moraes Ramos, G., Mai, T., Daamen, W., Frejinger, E. & Hoogendoorn, S. 2020. Route choice behaviour and travel information in a congested network: Static and dynamic recursi...

    work page 2014

  8. [8]

    Dixit, V. V. & Niu, C. 2023. Quantum computing for transport network design problems. Scientific Reports, 13, 12267

    work page 2023

  9. [9]

    V., Niu, C., Rey, D., Waller, S

    Dixit, V. V., Niu, C., Rey, D., Waller, S. T. & Levin, M. W. 2024. Quantum computing to solve scenario - based stochastic time-dependent shortest path routing. Transportation Letters, 16, 793-803

    work page 2024

  10. [10]

    Glover, F., Kochenberger, G., Hennig, R. & Du, Y. 2022. Quantum bridge analytics I: a tutorial on formulating and using QUBO models. Annals of Operations Research, 314, 141-183

    work page 2022

  11. [11]

    Gu, Y., Chen, A. & Xu, X. 2023. Measurement and ranking of important link combinations in the analysis of transportation network vulnerability envelope buffers under multiple-link disruptions. Transportation Research Part B: Methodological, 167, 118-144. Page 27 of 28

    work page 2023

  12. [12]

    Huang, X., Hu, S., Wang, W., Kaparias, I., Zhong, S., Na, X., Bell, M. G. & Lee, D. -H. 2023. Identifying critical links in urban transportation networks based on spatio -temporal dependency learning. IEEE Transactions on Intelligent Transportation Systems, 25, 5583-5597

    work page 2023

  13. [13]

    & Zhang, Y

    Li, M., Zhang, K. & Zhang, Y. 2025. Resilience assessment for road network under rainstorm events using crowdsourced data. Transportation Research Part D: Transport and Environment, 149, 105030

    work page 2025

  14. [14]

    & Ban, Y

    Lin, J. & Ban, Y. 2013. Complex network topology of transportation systems. Transport reviews, 33, 658-685

    work page 2013

  15. [15]

    Little, R. G. 2002. Controlling cascading failure: Understanding the vulnerabilities of interconnected infrastructures. Journal of Urban Technology, 9, 109-123

    work page 2002

  16. [16]

    & Lee, C

    Liu, J.-B., Zheng, Y.-Q. & Lee, C. -C. 2024. Statistical analysis of the regional air quality index of Yangtze River Delta based on complex network theory. Applied Energy, 357, 122529

    work page 2024

  17. [17]

    & Szeto, W

    Long, J. & Szeto, W. Y. 2019. Link -based system optimum dynamic traffic assignment problems in general networks. Operations Research, 67, 167-182

    work page 2019

  18. [18]

    & Schmidt, M

    Monstadt, J. & Schmidt, M. 2019. Urban resilience in the making? The governance of critical infrastructures in German cities. Urban studies, 56, 2353-2371

    work page 2019

  19. [19]

    & Natarajan, B

    Munikoti, S., Das, L. & Natarajan, B. 2022. Scalable graph neural network -based framework for identifying critical nodes and links in complex networks. Neurocomputing, 468, 211-221

    work page 2022

  20. [20]

    & Bhavathrathan, B

    Nitheesh, K. & Bhavathrathan, B. 2025. Risk-averse critical link identification considering evacuation demand and transport network topology. Transportation Research Part D: Transport and Environment , 104849

    work page 2025

  21. [21]

    Transportmetrica A: Transport Science, 1-31

    Niu, C., Irannezhad, E., Myers, C. & Dixit, V. 2025a. Quantum Computing in Transport Science: A Review. arXiv preprint arXiv:2503.21302

    work page arXiv

  22. [22]

    -H., Hu, J., Wang, Z

    Pei, S.-S., Zhai, C. -H., Hu, J., Wang, Z. -Q. & Xie, L. -L. 2024. Resilience assessment and enhancement of interdependent transportation -healthcare system: a spatial accessibility approach. Transportation Research Part D: Transport and Environment, 128, 104090

    work page 2024

  23. [23]

    & Waller, S

    Gardner, L. & Waller, S. T. 2020. A simple contagion process describes spreading of traffic jams in Page 28 of 28 urban networks. Nature communications, 11, 1616

    work page 2020

  24. [24]

    & Saberi, M

    Shafiei, S., Gu, Z. & Saberi, M. 2018. Calibration and validation of a simulation -based dynamic traffic assignment model for a large-scale congested network. Simulation Modelling Practice and Theory, 86, 169-186

    work page 2018

  25. [25]

    Shen, Z., Ji, C. & Lu, S. 2024. Transportation network resilience response to the spatial feature of hazards. Transportation Research Part D: Transport and Environment, 128, 104121

    work page 2024

  26. [26]

    & Kurauchi, F

    Sugiura, S. & Kurauchi, F. 2023. Isolation vulnerability analysis in road network: Edge connectivity and critical link sets. Transportation Research Part D: Transport and Environment, 119, 103768

    work page 2023

  27. [27]

    & Gong, G

    Wang, C., Gu, J. & Gong, G. 2025. Criticality -vulnerability assessment of regional pavement infrastructure network to future heat stress. Transportation Research Part D: Transport and Environment, 145, 104828

    work page 2025

  28. [28]

    & Yue, Q

    Wang, W., Wan, Y., Liu, Q., Liu, H., Li, C., Yang, S., Lai, X., Liu, Y. & Yue, Q. 2026. Urban road network resilience under emergencies: a microscopic simulation framework. Transportation Research Part D: Transport and Environment, 151, 105158

    work page 2026

  29. [29]

    Yang, Y., Wang, X., Chen, Y. & Hu, M. 2020. Identifying key nodes in complex networks based on global structure. IEEE access, 8, 32904-32913

    work page 2020

  30. [30]

    Yu, H., Cao, X., Liu, Z. & Li, Y. 2017. Identifying key nodes based on improved structural holes in complex networks. Physica A: Statistical Mechanics and its Applications, 486, 318-327

    work page 2017

  31. [31]

    & Wang, J

    Zhou, Y. & Wang, J. 2017. Critical link analysis for urban transportation systems. IEEE Transactions on Intelligent Transportation Systems, 19, 402-415

    work page 2017

  32. [32]

    Zimmerman, R. 2001. Social implications of infrastructure network interactions. Journal of urban technology, 8, 97-119

    work page 2001