Efficient Algorithms for Optimal Homology Problems and their Applications

Kostiantyn Lyman

doi:10.7273/000006500

The multiscale simplicial flat norm (MSFN) of a (non-bounding) d-cycle z is a family of optimal homology problems indexed by a scale parameter λ ≥ 0. Each instance optimizes a weighted combination of positive integer weights ("volumes") of the homologous d-cycle and the bounded (d+1)-chain, with the scale factor λ applied to either component. Additionally, one may seek the optimal flat norm decomposition of the input d-cycle into corresponding d- and (d + 1)-components. Notably, the classical optimal homologous cycle problem (OHCP) represents a special case of mSFN when λ = 0. We propose a min-cost flow formulation for solving an instance of MSFN for the case of (d+1)-dimensional simplicial complexes embedded in Rd+1. Furthermore, we establish both weak and strong duality results for mSFN defined over Z and Z+ coefficients. Additionally, we introduce stronger optimality conditions for directed min-cost flow solutions of OHCP and offer a topological characterization of these conditions. Next, we propose an approach based on the multiscale flat norm, a notion of distance between objects defined in the field of geometric measure theory, to compute the distance between a pair of planar geometric networks. Using a triangulation of the domain containing the input networks, the flat norm distance between two networks at a given scale can be computed by solving a linear program. In addition, this computation automatically identifies the 2D regions (patches) that capture where the two networks are different. We demonstrate through 2D examples that the flat norm distance can capture the variations of inputs more accurately than the commonly used Hausdorff distance. As a notion of stability, we also derive upper bounds on the flat norm distance between a simple 1D curve and its perturbed version as a function of the radius of perturbation for a restricted class of perturbations. We demonstrate our approach on a set of actual power networks from a county in the USA. Our approach can be extended to validate synthetic networks created for multiple infrastructures such as transportation, communication, water, and gas networks. Finally, we present a new framework that employs persistent homology (PH) to characterize significant cycle structures in dynamic sequences of directed bipartite graphs with the same set of nodes and edges but with the edge weights varying across the sequence. The motivation comes from atmospheric chemistry where species-reaction graphs with bipartitioned nodes of chemicals and reactions are tracked for levels of atmospheric pollutants such as oxides of nitrogen (NOx), ozone (O3), etc. We first create an undirected graph termed a path graph using one bipartition of the vertices, i.e., only chemicals or only reactions, where two nodes are connected if there is a directed path between them in the original graph. We then generate the 1D persistence diagram (PD) of the path graph using edge weight as the filtration parameter. We compare two input graphs using the (bottleneck or Wasserstein) distance between the corresponding path graph PDs. We prove that this bottleneck distance is stable under small changes to the input edge weights. We applied our framework to a set of 13104 species-reaction graphs ordered by increasing levels of NOx and O3. We show that the distance between adjacent PDs in the sequence is highly correlated with the levels of the gas in both cases. More importantly, our PH framework identifies groups of chemicals or reactions that generate the persistent cycles. Changes in distributions of these cycle groups were consistent with the scientific expectations on how reaction pathways vary by chemical conditions. Finally, we studied cycle threads as robust groups of chemicals that form the most persistent cycles across multiple graphs in the sequences. Representatives of the cycle threads and their distributions were consistent with different regimes in the chemical reactions for the two gases.

Efficient Algorithms for Optimal Homology Problems and their Applications

Files and links (1)

Abstract

Metrics

Details