Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Distances and isomorphism between networks: stability and convergence of network invariants

Distances and isomorphism between networks: stability and convergence of network invariants We develop the theoretical foundations of a generalized Gromov–Hausdorff distance between functions on networks that has recently been applied to various subfields of topological data analysis and optimal transport. These functional representations of networks, or networks for short, specialize in the finite setting to (possibly asymmetric) adjacency matrices and derived representations such as distance or kernel matrices. Existing literature utilizing these constructions cannot, however, benefit from continuous formulations because the continuum limits of finite networks under this distance are not well-understood. For example, while there are currently numerous persistent homology methods on finite networks, it is unclear if these methods produce well-defined persistence diagrams in the infinite setting. We resolve this situation by introducing the collection of compact networks that arises by taking continuum limits of finite networks and developing sampling results showing that this collection admits well-defined persistence diagrams. The difference between the network setting and metric setting arises as follows. For metric spaces, the isomorphism class of the Gromov–Hausdorff distance consists of isometric spaces and is thus very simple. For networks, the isomorphism class is rather complex, and contains representatives having different cardinalities and different topologies. We provide an exact characterization of a suitable notion of isomorphism for compact networks as well as alternative, stronger characterizations under additional topological regularity assumptions. Toward data applications, we describe a unified framework for developing quantitatively stable network invariants, provide basic examples, and cast existing results on the stability of persistent homology methods in this extended framework. To illustrate our theoretical results, we introduce a model of directed circles with finite reversibility and characterize their Dowker persistence diagrams. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Journal of Applied and Computational Topology Springer Journals

Distances and isomorphism between networks: stability and convergence of network invariants

Download PDF
119 pages

Loading next page...
 
/lp/springer-journals/distances-and-isomorphism-between-networks-stability-and-convergence-y7i3i7047z

References (80)

Publisher
Springer Journals
Copyright
Copyright © The Author(s), under exclusive licence to Springer Nature Switzerland AG 2022. Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
ISSN
2367-1726
eISSN
2367-1734
DOI
10.1007/s41468-022-00105-6
Publisher site
See Article on Publisher Site

Abstract

We develop the theoretical foundations of a generalized Gromov–Hausdorff distance between functions on networks that has recently been applied to various subfields of topological data analysis and optimal transport. These functional representations of networks, or networks for short, specialize in the finite setting to (possibly asymmetric) adjacency matrices and derived representations such as distance or kernel matrices. Existing literature utilizing these constructions cannot, however, benefit from continuous formulations because the continuum limits of finite networks under this distance are not well-understood. For example, while there are currently numerous persistent homology methods on finite networks, it is unclear if these methods produce well-defined persistence diagrams in the infinite setting. We resolve this situation by introducing the collection of compact networks that arises by taking continuum limits of finite networks and developing sampling results showing that this collection admits well-defined persistence diagrams. The difference between the network setting and metric setting arises as follows. For metric spaces, the isomorphism class of the Gromov–Hausdorff distance consists of isometric spaces and is thus very simple. For networks, the isomorphism class is rather complex, and contains representatives having different cardinalities and different topologies. We provide an exact characterization of a suitable notion of isomorphism for compact networks as well as alternative, stronger characterizations under additional topological regularity assumptions. Toward data applications, we describe a unified framework for developing quantitatively stable network invariants, provide basic examples, and cast existing results on the stability of persistent homology methods in this extended framework. To illustrate our theoretical results, we introduce a model of directed circles with finite reversibility and characterize their Dowker persistence diagrams.

Journal

Journal of Applied and Computational Topology – Springer Journals

Published: Jun 1, 2023

Keywords: Network data analysis; Directed networks; Generalized metric spaces; Gromov–Hausdorff distance; Gromov–Wasserstein distance; 68T09; 55N31; 54E35

There are no references for this article.