Characterizing Flow Complexity in Transportation Networks using Graph Homology
<|reference_start|>Characterizing Flow Complexity in Transportation Networks using Graph Homology: 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.<|reference_end|>
@article{deshpande2024characterizing,
    title={Characterizing Flow Complexity in Transportation Networks using Graph
  Homology},
    author={Shashank A Deshpande and Hamsa Balakrishnan},
    journal={arXiv preprint arXiv:2403.05749},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.05749},
    primaryClass={eess.SY cs.DM cs.SY}
}