1
|
Lonardi A, De Bacco C. Bilevel Optimization for Traffic Mitigation in Optimal Transport Networks. PHYSICAL REVIEW LETTERS 2023; 131:267401. [PMID: 38215368 DOI: 10.1103/physrevlett.131.267401] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/28/2023] [Revised: 09/21/2023] [Accepted: 11/22/2023] [Indexed: 01/14/2024]
Abstract
Global infrastructure robustness and local transport efficiency are critical requirements for transportation networks. However, since passengers often travel greedily to maximize their own benefit and trigger traffic jams, overall transportation performance can be heavily disrupted. We develop adaptation rules that leverage optimal transport theory to effectively route passengers along their shortest paths while also strategically tuning edge weights to optimize traffic. As a result, we enforce both global and local optimality of transport. We prove the efficacy of our approach on synthetic networks and on real data. Our findings on the international European highways suggest that thoughtfully devised routing schemes might help to lower car-produced carbon emissions.
Collapse
Affiliation(s)
- Alessandro Lonardi
- Max Planck Institute for Intelligent Systems, Cyber Valley, Tübingen 72076, Germany
| | - Caterina De Bacco
- Max Planck Institute for Intelligent Systems, Cyber Valley, Tübingen 72076, Germany
| |
Collapse
|
2
|
Lonardi A, Facca E, Putti M, De Bacco C. Infrastructure adaptation and emergence of loops in network routing with time-dependent loads. Phys Rev E 2023; 107:024302. [PMID: 36932530 DOI: 10.1103/physreve.107.024302] [Citation(s) in RCA: 1] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/27/2022] [Accepted: 01/24/2023] [Indexed: 02/05/2023]
Abstract
Network routing approaches are widely used to study the evolution in time of self-adapting systems. However, few advances have been made for problems where adaptation is governed by time-dependent inputs. In this work we study a dynamical systems where the edge conductivities of a network are regulated by time-varying mass loads injected on nodes. Motivated by empirical observations, we assume that conductivities adapt slowly with respect to the characteristic time of the loads. Furthermore, assuming the loads to be periodic, we derive a dynamics where the evolution of the system is controlled by a matrix obtained with the Fourier coefficients of the input loads. Remarkably, we find a sufficient condition on these coefficients that determines when the resulting network topologies are trees. We show an example of this on the Bordeaux bus network where we tune the input loads to interpolate between loopy and tree topologies. We validate our model on several synthetic networks and provide an expression for long-time solutions of the original conductivities.
Collapse
Affiliation(s)
- Alessandro Lonardi
- Max Planck Institute for Intelligent Systems, Cyber Valley, 72076 Tübingen, Germany
| | - Enrico Facca
- Laboratoire Paul Painlevé, UMR No. 8524, CNRS, Inria, Université Lille, 59000 Lille, France
| | - Mario Putti
- Department of Mathematics "Tullio Levi-Civita," University of Padua, Via Trieste 63, 35131 Padua, Italy
| | - Caterina De Bacco
- Max Planck Institute for Intelligent Systems, Cyber Valley, 72076 Tübingen, Germany
| |
Collapse
|
3
|
Bhattacharyya K, Zwicker D, Alim K. Memory Formation in Adaptive Networks. PHYSICAL REVIEW LETTERS 2022; 129:028101. [PMID: 35867448 DOI: 10.1103/physrevlett.129.028101] [Citation(s) in RCA: 2] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/27/2021] [Revised: 06/14/2022] [Accepted: 06/15/2022] [Indexed: 06/15/2023]
Abstract
The continuous adaptation of networks like our vasculature ensures optimal network performance when challenged with changing loads. Here, we show that adaptation dynamics allow a network to memorize the position of an applied load within its network morphology. We identify that the irreversible dynamics of vanishing network links encode memory. Our analytical theory successfully predicts the role of all system parameters during memory formation, including parameter values which prevent memory formation. We thus provide analytical insight on the theory of memory formation in disordered systems.
Collapse
Affiliation(s)
- Komal Bhattacharyya
- Max Planck Institute for Dynamics and Self-Organisation, Göttingen 37077, Germany
| | - David Zwicker
- Max Planck Institute for Dynamics and Self-Organisation, Göttingen 37077, Germany
| | - Karen Alim
- Max Planck Institute for Dynamics and Self-Organisation, Göttingen 37077, Germany
- Center for Protein Assemblies (CPA), Physik-Department, Technische Universität München, Garching 85748, Germany
| |
Collapse
|
4
|
Martineau S, Saffold T, Chang TT, Ronellenfitsch H. Enhancing Synchronization by Optimal Correlated Noise. PHYSICAL REVIEW LETTERS 2022; 128:098301. [PMID: 35302804 DOI: 10.1103/physrevlett.128.098301] [Citation(s) in RCA: 7] [Impact Index Per Article: 3.5] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 07/13/2021] [Revised: 01/11/2022] [Accepted: 02/09/2022] [Indexed: 06/14/2023]
Abstract
From the flashes of fireflies to Josephson junctions and power infrastructure, networks of coupled phase oscillators provide a powerful framework to describe synchronization phenomena in many natural and engineered systems. Most real-world networks are under the influence of noisy, random inputs, potentially inhibiting synchronization. While noise is unavoidable, here we show that there exist optimal noise patterns which minimize desynchronizing effects and even enhance order. Specifically, using analytical arguments we show that in the case of a two-oscillator model, there exists a sharp transition from a regime where the optimal synchrony-enhancing noise is perfectly anticorrelated, to one where the optimal noise is correlated. More generally, we then use numerical optimization methods to demonstrate that there exist anticorrelated noise patterns that optimally enhance synchronization in large complex oscillator networks. Our results may have implications in networks such as power grids and neuronal networks, which are subject to significant amounts of correlated input noise.
Collapse
Affiliation(s)
- Sherwood Martineau
- Physics Department, Williams College, 33 Lab Campus Drive, Williamstown, Massachusetts 01267, USA
| | - Tim Saffold
- Physics Department, Williams College, 33 Lab Campus Drive, Williamstown, Massachusetts 01267, USA
| | - Timothy T Chang
- Physics Department, Williams College, 33 Lab Campus Drive, Williamstown, Massachusetts 01267, USA
| | - Henrik Ronellenfitsch
- Physics Department, Williams College, 33 Lab Campus Drive, Williamstown, Massachusetts 01267, USA
| |
Collapse
|
5
|
Deepa Maheshvare M, Raha S, Pal D. A Graph-Based Framework for Multiscale Modeling of Physiological Transport. FRONTIERS IN NETWORK PHYSIOLOGY 2022; 1:802881. [PMID: 36925576 PMCID: PMC10013063 DOI: 10.3389/fnetp.2021.802881] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Subscribe] [Scholar Register] [Received: 10/27/2021] [Accepted: 11/30/2021] [Indexed: 11/13/2022]
Abstract
Trillions of chemical reactions occur in the human body every second, where the generated products are not only consumed locally but also transported to various locations in a systematic manner to sustain homeostasis. Current solutions to model these biological phenomena are restricted in computability and scalability due to the use of continuum approaches in which it is practically impossible to encapsulate the complexity of the physiological processes occurring at diverse scales. Here, we present a discrete modeling framework defined on an interacting graph that offers the flexibility to model multiscale systems by translating the physical space into a metamodel. We discretize the graph-based metamodel into functional units composed of well-mixed volumes with vascular and cellular subdomains; the operators defined over these volumes define the transport dynamics. We predict glucose drift governed by advective-dispersive transport in the vascular subdomains of an islet vasculature and cross-validate the flow and concentration fields with finite-element-based COMSOL simulations. Vascular and cellular subdomains are coupled to model the nutrient exchange occurring in response to the gradient arising out of reaction and perfusion dynamics. The application of our framework for modeling biologically relevant test systems shows how our approach can assimilate both multi-omics data from in vitro-in vivo studies and vascular topology from imaging studies for examining the structure-function relationship of complex vasculatures. The framework can advance simulation of whole-body networks at user-defined levels and is expected to find major use in personalized medicine and drug discovery.
Collapse
Affiliation(s)
| | | | - Debnath Pal
- Department of Computational and Data Sciences, Indian Institute of Science, Bangalore, India
| |
Collapse
|
6
|
Abstract
Modeling traffic distribution and extracting optimal flows in multilayer networks is of the utmost importance to design efficient, multi-modal network infrastructures. Recent results based on optimal transport theory provide powerful and computationally efficient methods to address this problem, but they are mainly focused on modeling single-layer networks. Here, we adapt these results to study how optimal flows distribute on multilayer networks. We propose a model where optimal flows on different layers contribute differently to the total cost to be minimized. This is done by means of a parameter that varies with layers, which allows to flexibly tune the sensitivity to the traffic congestion of the various layers. As an application, we consider transportation networks, where each layer is associated to a different transportation system, and show how the traffic distribution varies as we tune this parameter across layers. We show an example of this result on the real, 2-layer network of the city of Bordeaux with a bus and tram, where we find that in certain regimes, the presence of the tram network significantly unburdens the traffic on the road network. Our model paves the way for further analysis of optimal flows and navigability strategies in real, multilayer networks.
Collapse
|
7
|
Ronellenfitsch H. Optimal Elasticity of Biological Networks. PHYSICAL REVIEW LETTERS 2021; 126:038101. [PMID: 33543959 DOI: 10.1103/physrevlett.126.038101] [Citation(s) in RCA: 3] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 08/04/2020] [Accepted: 12/24/2020] [Indexed: 06/12/2023]
Abstract
Reinforced elastic sheets surround us in daily life, from concrete shell buildings to biological structures such as the arthropod exoskeleton or the venation network of dicotyledonous plant leaves. Natural structures are often highly optimized through evolution and natural selection, leading to the biologically and practically relevant problem of understanding and applying the principles of their design. Inspired by the hierarchically organized scaffolding networks found in plant leaves, here we model networks of bending beams that capture the discrete and nonuniform nature of natural materials. Using the principle of maximal rigidity under natural resource constraints, we show that optimal discrete beam networks reproduce the structural features of real leaf venation. Thus, in addition to its ability to efficiently transport water and nutrients, the venation network also optimizes leaf rigidity using the same hierarchical reticulated network topology. We study the phase space of optimal mechanical networks, providing concrete guidelines for the construction of elastic structures. We implement these natural design rules by fabricating efficient, biologically inspired metamaterials.
Collapse
Affiliation(s)
- Henrik Ronellenfitsch
- Department of Mathematics, Massachusetts Institute of Technology, 77 Massachusetts Ave, Cambridge, Massachusetts 02139, USA
- Physics Department, Williams College, 33 Lab Campus Drive, Williamstown, Massachusetts 01267, USA
| |
Collapse
|
8
|
Kaiser F, Ronellenfitsch H, Witthaut D. Discontinuous transition to loop formation in optimal supply networks. Nat Commun 2020; 11:5796. [PMID: 33199688 PMCID: PMC7670464 DOI: 10.1038/s41467-020-19567-2] [Citation(s) in RCA: 9] [Impact Index Per Article: 2.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/23/2020] [Accepted: 10/19/2020] [Indexed: 11/09/2022] Open
Abstract
The structure and design of optimal supply networks is an important topic in complex networks research. A fundamental trait of natural and man-made networks is the emergence of loops and the trade-off governing their formation: adding redundant edges to supply networks is costly, yet beneficial for resilience. Loops typically form when costs for new edges are small or inputs uncertain. Here, we shed further light on the transition to loop formation. We demonstrate that loops emerge discontinuously when decreasing the costs for new edges for both an edge-damage model and a fluctuating sink model. Mathematically, new loops are shown to form through a saddle-node bifurcation. Our analysis allows to heuristically predict the location and cost where the first loop emerges. Finally, we unveil an intimate relationship among betweenness measures and optimal tree networks. Our results can be used to understand the evolution of loop formation in real-world biological networks. Supply networks with optimal structure do not contain loops but these can arise as a result of damages or fluctuations. Here Kaiser et al. uncover the mechanisms of loop formation, predict their location and draw analogies with loop formation in biological networks such as plants and animal vasculature.
Collapse
Affiliation(s)
- Franz Kaiser
- Forschungszentrum Jülich, Institute for Energy and Climate Research (IEK-STE), 52428, Jülich, Germany. .,Institute for Theoretical Physics, University of Cologne, 50937, Köln, Germany.
| | - Henrik Ronellenfitsch
- Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, 02139, USA.,Physics Department, Williams College, 33 Lab Campus Drive, Williamstown, MA, 01267, USA
| | - Dirk Witthaut
- Forschungszentrum Jülich, Institute for Energy and Climate Research (IEK-STE), 52428, Jülich, Germany. .,Institute for Theoretical Physics, University of Cologne, 50937, Köln, Germany.
| |
Collapse
|