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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Finding the Homology of Decision Boundaries with Active Learning
Accurately and efficiently characterizing the decision boundary of classifiers is important for problems related to model selection and meta-learning. Inspired by topological data analysis, the characterization of decisi…
Active LearningMeta-LearningModel SelectionTopological Data AnalysisMixup Barcodes: Quantifying Geometric-Topological Interactions between Point Clouds
We combine standard persistent homology with image persistent homology to define a novel way of characterizing shapes and interactions between them. In particular, we introduce: (1) a mixup barcode, which captures geomet…
DisentanglementTime Series Analysis of Spiking Neural Systems via Transfer Entropy and Directed Persistent Homology
We present a topological framework for analysing neural time series that integrates Transfer Entropy (TE) with directed Persistent Homology (PH) to characterize information flow in spiking neural systems. TE quantifies d…
Time Series AnalysisCharacterizing and Measuring the Similarity of Neural Networks with Persistent Homology
Characterizing the structural properties of neural networks is crucial yet poorly understood, and there are no well-established similarity measures between networks. In this work, we observe that neural networks can be r…
Topological Data AnalysisInterpretable Phase Detection and Classification with Persistent Homology
We apply persistent homology to the task of discovering and characterizing phase transitions, using lattice spin models from statistical physics for working examples. Persistence images provide a useful representation of…
ClassificationGeneral Classificationregression