Characterizing Flow Complexity in Transportation Networks using Graph Homology
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914709028995072 |
|---|---|
| author | Deshpande, Shashank A Balakrishnan, Hamsa |
| author_facet | Deshpande, Shashank A Balakrishnan, Hamsa |
| contents | Series-parallel network topologies generally exhibit simplified dynamical behavior and avoid high combinatorial complexity. A comprehensive analysis of how flow complexity emerges with a graph's deviation from series-parallel topology is therefore of fundamental interest. We introduce the notion of a robust $k$-path on a directed acycylic graph, with increasing values of the length $k$ reflecting increasing deviations. We propose a graph homology with robust $k$-paths as the bases of its chain spaces. In this framework, the topological simplicity of series-parallel graphs translates into a triviality of higher-order chain spaces. We discuss a correspondence between the space of order-three chains and sites within the network that are susceptible to the Braess paradox, a well-known phenomenon in transportation networks. In this manner, we illustrate the utility of the proposed graph homology in sytematically studying the complexity of flow networks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_05749 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Characterizing Flow Complexity in Transportation Networks using Graph Homology Deshpande, Shashank A Balakrishnan, Hamsa Systems and Control Discrete Mathematics Series-parallel network topologies generally exhibit simplified dynamical behavior and avoid high combinatorial complexity. A comprehensive analysis of how flow complexity emerges with a graph's deviation from series-parallel topology is therefore of fundamental interest. We introduce the notion of a robust $k$-path on a directed acycylic graph, with increasing values of the length $k$ reflecting increasing deviations. We propose a graph homology with robust $k$-paths as the bases of its chain spaces. In this framework, the topological simplicity of series-parallel graphs translates into a triviality of higher-order chain spaces. We discuss a correspondence between the space of order-three chains and sites within the network that are susceptible to the Braess paradox, a well-known phenomenon in transportation networks. In this manner, we illustrate the utility of the proposed graph homology in sytematically studying the complexity of flow networks. |
| title | Characterizing Flow Complexity in Transportation Networks using Graph Homology |
| topic | Systems and Control Discrete Mathematics |
| url | https://arxiv.org/abs/2403.05749 |