Tuned communicability metrics in networks. The case of alternative routes for urban traffic. (English) Zbl 1442.90042
Summary: We generalize here the communicability metric on graphs/networks to include a tuning parameter that accounts for the level of edge “deterioration”. This generalized metric covers a wide range of realistic scenarios in networks, which includes shortest-path metric as a particular case. We study the communicability metric on an urban street network, and show that communicability shortest paths in this city accounts for most of the traffic between series of origin-destination points. Particularly, we show that the traffic flow and congestion in the shortest communicability paths is much bigger than in the corresponding shortest paths. This indicates that under certain conditions drivers in a city avoid long paths but also avoid the most interconnected street intersections, which typically may be the most congested ones. We develop here a diffusion-like model on the network based on a particle-hopping scheme inspired by “tight-binding” quantum mechanical Hamiltonian, which offers a solid explanation on why traffic is diverted through the shortest communicability routes instead of the shortest-paths.
MSC:
| 90B20 | Traffic problems in operations research |
| 90B15 | Stochastic network models in operations research |
| 05C90 | Applications of graph theory |
| 05C80 | Random graphs (graph-theoretic aspects) |
References:
| [1] | Estrada, E., The structure of complex networks: theory and applications (2012), Oxford University Press · Zbl 1267.05001 |
| [2] | Latora, V.; Nicosia, V.; Russo, G., Complex networks: principles, methods and applications (2017), Cambridge University Press · Zbl 1387.68003 |
| [3] | Newman, M. E., The structure and function of complex networks, SIAM Rev, 45, 2, 167-256 (2003) · Zbl 1029.68010 |
| [4] | Boccaletti, S.; Latora, V.; Moreno, Y.; Chavez, M.; Hwang, D. U., Complex networks: structure and dynamics, Phys Rep, 424, 4-5, 175-308 (2006) · Zbl 1371.82002 |
| [5] | Buckley, F.; Harary, F., Distance in graphs (1990), Addison-Wesley · Zbl 0688.05017 |
| [6] | Deza, M. M.; Deza, E., Encyclopedia of distances (2012), Springer Science & Business Media |
| [7] | Sharpe, G. E., Solution of the (m+ 1)-terminal resistive network problem by means of metric geometry, Proceedings of the First Asilomar Conference on Circuits and Systems. Pacific Grove, CA Nov, 319-328 (1967) |
| [8] | Gvishiani, A. D.; Gurvich, V. A., Metric and ultrametric spaces of resistances, Russ Math Surv, 42, 6, 235-236 (1987) · Zbl 0708.90028 |
| [9] | Klein, D. J.; Randić, M., Resistance distance, J Math Chem, 12, 1, 81-95 (1993) |
| [10] | Chandra, A. K.; Raghavan, P.; Ruzzo, W. L.; Smolensky, R.; Tiwari, P., The electrical resistance of a graph captures its commute and cover times, Proc. 21st Annual ACM Symp. on Theory of Computing, 574-586 (1989), ACM Press: ACM Press Seattle |
| [11] | Göbel, F.; Jagers, A. A., Random walks on graphs, Stoch Process Their Appl, 2, 4, 311-336 (1974) · Zbl 0296.60046 |
| [12] | Nash-Williams, C. S., Random walk and electric currents in networks, Mathematical Proceedings of the Cambridge Philosophical Society, Apr, 55, 181-194 (1959), Cambridge University Press · Zbl 0100.13602 |
| [13] | Krioukov, D.; Papadopoulos, F.; Kitsak, M.; Vahdat, A.; Boguná, M., Hyperbolic geometry of complex networks, Phys Rev E, 82, 3, 036106 (2010) |
| [14] | Chebotarev, P.; Shamis, E., The forest metrics for graph vertices, Electron Notes Discrete Math, 11, 98-107 (2002) · Zbl 1075.05522 |
| [15] | Chebotarev, P., A class of graph-geodetic distances generalizing the shortest-path and the resistance distances, Discrete Appl Math, 159, 5, 295-302 (2011) · Zbl 1209.05068 |
| [16] | Estrada, E., The communicability distance in graphs, Linear Algebra Appl, 436, 4317-4328 (2012) · Zbl 1243.05071 |
| [17] | Estrada, E., Complex networks in the euclidean space of communicability distances, Physical Review E, 85, 066122 (2012) |
| [18] | Estrada, E.; Hatano, N., Communicability in complex networks, Physical Review E, 77, 036111 (2008) |
| [19] | Estrada, E.; Higham, D. J., Network properties revealed through matrix functions, SIAM Rev, 52, 696-714 (2010) · Zbl 1214.05077 |
| [20] | Estrada, E.; Hatano, N.; Benzi, M., The physics of communicability in complex networks, Phys Rep, 514, 89-119 (2012) |
| [21] | Estrada, E.; Rodríguez-Velázquez, J. A., Subgraph centrality in complex networks, Phys Rev E, 71, 056103 (2005) |
| [22] | Estrada, E.; Sanchez-Lirola, M. G.; de la Peña, J. A., Hyperspherical embedding of graphs and networks in communicability spaces, Discrete Appl Math, 176, 53-77 (2014) · Zbl 1297.05072 |
| [23] | Estrada, E.; Hatano, N., Communicability angle and the spatial efficiency of networks, SIAM Rev, 58, 692-715 (2016) · Zbl 1348.05199 |
| [24] | Luxburg, U. V.; Radl, A.; Hein, M., Getting lost in space: large sample analysis of the resistance distance, In Advances in Neural Information Processing Systems, 2622-2630 (2010) |
| [25] | Estrada, E.; Higham, D. J.; Hatano, N., Communicability and multipartite structures in complex networks at negative absolute temperatures, Phys Rev E, 78, 2, 026102 (2008) |
| [26] | Estrada, E., Generalized walks-based centrality measures for complex biological networks, J Theor Biol, 263, 4, 556-565 (2010) · Zbl 1406.92239 |
| [27] | Estrada, E.; Silver, G., Accounting for the role of long walks on networks via a new matrix function, J Math Anal Appl, 449, 2, 1581-1600 (2017) · Zbl 1355.05233 |
| [28] | Estrada, E.; Rodríguez-Velázquez, J. A., Spectral measures of bipartivity in complex networks, Phys Rev E, 72, 4, 046105 (2005) |
| [29] | Estrada, E.; Gómez-Gardeñes, J., Network bipartivity and the transportation efficiency of european passenger airlines, Physica D, 323, 57-63 (2016) · Zbl 1364.90041 |
| [30] | Toussaint, G. T., The relative neighbourhood graph of a finite planar set, Pattern Recognit, 12, 4, 261-268 (1980) · Zbl 0437.05050 |
| [31] | Jaromczyk, J. W.; Toussaint, G. T., Relative neighborhood graphs and their relatives, Proc IEEE, 80, 9, 1502-1517 (1992) |
| [32] | Gabriel, K. R.; Sokal, R. R., A new statistical approach to geographic variation analysis, Syst Zool, 18, 3, 259-278 (1969) |
| [33] | Geroliminis, N.; Daganzo, C. F., Macroscopic modeling of traffic in cities, 86th Annual Meeting of the Transportation Research Board (2007) |
| [34] | Chowdhury, D.; Santen, L.; Schadschneider, A., Statistical physics of vehicular traffic and some related systems, Phys Rep, 329, 199-329 (2000) |
| [35] | Helbing, D., Traffic and related self-driven many-particle systems, Rev Mod Phys, 73, 1067-1141 (2001) |
| [36] | Li, T., Modelling traffic flow with a time-dependent fundamental diagram, Math Methods Appl Sci, 27, 5, 583-601 (2004) · Zbl 1041.35035 |
| [37] | Bellomo, N.; Bellouquid, A.; Nieto, J.; Solerz, J., On the multiscale modeling of vehicular traffic: from kinetic to hydrodynamics, Discrete Continuous Dyn Syst Ser B, 19, 7, 1869-1888 (2014) · Zbl 1302.35372 |
| [38] | Ren, Y.; Ercsey-Ravasz, M.; Wang, P.; González, M. C.; Toroczkai, Z., Predicting commuter flows in spatial networks using a radiation model based on temporal ranges, Nat Commun, 5, 5347 (2014) |
| [39] | Darwish, T.; Abu Bakar, K., Traffic density estimation in vehicular ad hoc networks: a review, Ad Hoc Netw, 19, 337-351 (2015) |
| [40] | Louf, R.; Barthelemy, M., How congestion shapes cities: from mobility patterns to scaling, Sci Rep, 4, 5561 (2014) |
| [41] | Noulas, A.; Scellato, S.; Lambiotte, R.; Pontil, M.; Mascolo, C., A tale of many cities: universal patterns in human urban mobility, PLoS ONE, 7, 5, e37027 (2012) |
| [42] | Colombo, R. M.; Marcellini, F., A mixed ODE-PDE model for vehicular traffic, Math Methods Appl Sci, 38, 7, 1292-1302 (2015) · Zbl 1320.35209 |
| [43] | Akbarzadeh, M.; Estrada, E., Communicability geometry captures traffic flows in cities, Nat Hum Behav, 2, 645-652 (2018) |
| [44] | Rosvall, M.; Trusina, A.; Minnhagen, P.; Sneppen, K., Networks and cities: an information perspective, Phys Rev Lett, 94, 2, 028701 (2005) |
| [45] | Çolak, S.; Lima, A.; González, M. C., Understanding congested travel in urban areas, Nat Commun, 7, 10793 (2016) |
| [46] | Sainct, R.; Louis, X.; Forestier, A., Application of averaging techniques to traffic flow theory, Math Methods Appl Sci, 40, 3, 600-625 (2017) · Zbl 1362.35179 |
| [47] | Jiménez-Casas, A.; Rodríguez-Bernal, A., Some general models of traffic flow in an isolated network, Math Methods Appl Sci, 40, 11, 3982-4000 (2017) · Zbl 1370.90041 |
| [48] | Barthélemy, M., Spatial networks, Phys Rep, 449, 1-101 (2011) |
| [49] | Barthélemy, M., The structure and dynamics of cities (2016), Cambridge University Press · Zbl 1376.91005 |
| [50] | de Dios, O. J.; Willumsen, L. G., Modelling transport (2011), John Wiley & Sons |
| [51] | Wardrop, J. G., Some theoretical aspects of road traffic research, Proceedings of the Institution of Civil Engineers, Part II, 1, 325-362 (1952) |
| [52] | Golledge, R. G.; Gärling, T., Cognitive maps and urban travel, In Handbook of transport geography and spatial systems, Aug 24, 501-512 (2004), Emerald Group Publishing Limited |
| [53] | Nagel, K., Particle hopping models and traffic flow theory, Phys Rev E, 53, 5, 4655 (1996) |
| [54] | Baker, R. G., On the kinematics and quantum dynamics of traffic flow, Transp Res Part B: Methodol,, 17, 1, 55-66 (1983) |
| [55] | Woesler, R.; Thiessenhusen, K. U.; Kühne, R. D., Approximating traffic flow by a schrödinger equation-introduction of non-reflecting boundary conditions, In Traffic and Granular Flow’ 03, 223-228 (2005), Springer: Springer Berlin, Heidelberg |
| [56] | Lerman, K.; Ghosh, R., Network structure, topology, and dynamics in generalized models of synchronization, Phys Rev E, 86, 2, 026108 (2012) |
| [57] | Kadanoff, L. P., Quantum statistical mechanics (2018), CRC Press |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
