Shape and Performance of Fastest Paths over Networks with Interacting Selfish Agents
Marco Cogoni, Giovanni Busonera, Enrico Gobbetti · 2024
Read Shape and Performance of Fastest Paths over Networks with Interacting Selfish Agents by Marco Cogoni, Giovanni Busonera, Enrico Gobbetti (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-17665.txt.
Introduction
Marco Cogoni, Giovanni Busonera, and Enrico Gobbetti tracked the fastest paths through city streets as traffic builds in a 2024 paper. They study eight big cities at the morning peak. Streets start empty and fill car by car, and each driver picks the fastest route for the flow at that moment, so routes bend as the crowd grows.
They score each route by its length, its stray from a straight line, and its lean toward the center. A new mark grades how fast and how far it heads to its goal. Near a set crowd level, route shapes in all cities swelled in stray and lean at once, and the pain of slow downs spread less fairly. Light traffic drew routes toward the center, then the pull flipped.
Catalog record
| CREATOR | Marco Cogoni, Giovanni Busonera, Enrico Gobbetti |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 47 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-17665
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Shape and Performance of Fastest Paths over Networks with Interacting Selfish Agents Marco Cogoni, Giovanni Busonera, Enrico Gobbetti Abstract We study the evolution of the fastest paths (FP) in transportation networks under increasing congestion. Moving from the common edge-based to a path-based analysis, we examine the directed FPs connecting random origin-destination pairs as traffic grows. We describe their shape through effective length, detour (maximum distance of FP from a straight line), inness (signed area between FP and straight line), and their performance through a novel metric measuring how fast and how far an agent travels toward its destination. The entire network is characterized by analyzing the distribution of the performance metric (and its Gini coefficient) across uniformly sampled paths. The study focuses on the traffic loading phenomenon that takes place during the morning peak hour for eight major cities: Networks start with empty edges that are progressively populated by the FPs of single vehicles. As vehicle density grows, the interactions among selfish agents becomes stronger at edge level, and travel speed linearly decreases, thus optimal paths dynamically change with traffic. We fully characterize the transition to congestion and discuss the common aspects among the cities (and some peculiarities), in particular we were able to pinpoint a critical traffic level (or a sequence) for which path shape, rejection ratio, and inequality of the performance degradation, show a concurrent qualitative change. For all cities we observe large peaks for both detour and inness (and their variance) in the proximity of the critical traffic level. Inness shows that paths are slightly attracted by city centers with light traffic, but switch to a strong repulsion immediately beyond the transition. Finally, our path performance metric highlighted a strongly asymmetric behavior when the city neighborhoods act as origins or destinations. I Introduction Network transport performance and robustness are usually estimated using static measures depending on topological and geometrical factors that characterize the network in its idle state, but cannot grasp the complex structural modifications that happen when the network is subject to growing levels of traffic helbing_traffic_2001 ; zeng_switch_2019 ; zhang2022complex . Network robustness is often studied by removing random elements such as nodes and edges or varying their capacity to highlight weak points and bottlenecks within the system Magnien:2021:IRF . While very useful for evaluating abstract network geometries, this approach does not consider any specific process happening over the network. It turns out, however, that details of the transport process may greatly impact how the system reacts to perturbations. In particular, real processes typically produce non-random, spatially correlated, perturbations, thus knowledge about them allows the development of better testing procedures oehlers2021graph ; schwarze2024structural . In this context, percolation theory is sometimes used to model transport disruption zeng_switch_2019 ; zeng_multiple_2020 , and it can be used to estimate the fraction of malfunctioning edges (or nodes) sufficient to break up the network into several disconnected clusters cogoni2021stability . This approach has been recently applied to traffic in urban networks by using the vehicle speed on each road (edge) as a predictor of transport collapse to find the threshold speed above which fragmentation appears for different traffic regimes cogoni2024predicting . Percolation, however, ignores the details of the transport process altogether, modeling only its effects. Estimating whole-network performance using the distribution of edge efficiencies may give a biased picture depending on the specific transport process. For example, when Origins and Destinations (OD) are connected via shortest (or fastest) paths, the impacted edges are spatially correlated and generally produce a strongly inhomogeneous load profile. Different requirements on path routing and OD spatial distribution may lead to entirely different network usage patterns, thus translating to different expected performances. Transport processes are found everywhere in natural and artificial systems, for instance in urban networks, whose traffic patterns have been strongly influenced by the emergence of personal navigation tools that provide the fastest paths (FPs) in real time serok_unveiling_2019 . A non-local measure widely employed to estimate network performance at the edge level is the Betweenness Centrality (BC). Centrality measures have long been used to predict which edges (and nodes) are typically subject to the highest traffic, but the correlation with real traffic is known to suffer in the medium and high-density regimes holme2003congestion ; guimera2005worldwide . Edge usage obtained from BC, in fact, typically mimics a low-density state of the network that usually happens with very small (compared to network geometry) or very fast (with respect to congestion buildup timescales) agents kazerani2009can . Recently, standard BC has been improved by introducing a model to simulate urban networks with different traffic levels and considering the strong interaction effects observed in different conditions to obtain a better measure of edge congestion cogoni2024predicting . While the theoretical foundations of that approach are transferable to other contexts yeung2012competition ; hamedmoghadam_percolation_2021 ; olmos_macroscopic_2018 ; colak_understanding_2016 , urban networks have specific connectivity characteristics that have led to the emergence of specific theoretical models and studies. In particular, they belong to the special class of (almost) planar graphs diet_towards_2018 ; helbing_traffic_2001 whose topology is constrained by the geographical embedding. This severely hinders their long-range connectivity and limits their maximum node degree aldous2013true . The specificity of urban networks has been widely studied colak_understanding_2016 ; li_percolation_2015 ; kirkley_betweenness_2018 ; serok_unveiling_2019 , both in terms of their growth over time and of their complex dynamics under different traffic levels. In this work we propose a shift in the performance measuring process departing from an edge-based in favor of a path-based network metric. The basic idea relies on the fact that having the majority of network components that are still efficient is not enough to guarantee functional transports if the assigned task often implies the use of a minority of saturated links. This is especially crucial for transport processes such as the ones occurring over urban networks, where the congestion patterns are shaped by interacting traveling agents that dynamically react to the growing traffic by selfishly adapting their routing: A behavior that is rapidly becoming dominant within our cities. Our main goal in this work is to study the evolution of the shape and the performance distribution of the FPs while increasing the traffic level from an empty to a deeply congested network. To this aim, we focus on the scaling behavior of FP effective path length (defined in II.1 ) and detour (maximum distance of FP from a straight line) for a set of large, densely-populated, metropolitan areas. Critical exponents are computed for growing network congestion and plotted on a plane to better understand how they evolve. To better characterize the relation of the FP morphology with its embeddings over a broad range of traffic, we also analyze inness lee_morphology_2017 (signed area between FP and straight line) and we discover that the slightly attractive force exerted by city centers (when empty) switches to strong repulsion beyond a well-defined traffic level. Moving beyond path morphology, we discuss the evolution of the path performance distribution: Path performance turns out to be useful not only in better evaluating whole-network efficiency, but in uncovering a strong asymmetry of different parts of the cities when acting as sources or destinations of traffic. Finally, we resort to the Gini coefficient of the performance distribution to estimate the