Efficient estimation of the modified Gromov-Hausdorff distance between unweighted graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2019
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910473305194496 |
|---|---|
| author | Oles, Vladyslav Lemons, Nathan Panchenko, Alexander |
| author_facet | Oles, Vladyslav Lemons, Nathan Panchenko, Alexander |
| contents | Gromov-Hausdorff distances measure shape difference between the objects representable as compact metric spaces, e.g. point clouds, manifolds, or graphs. Computing any Gromov-Hausdorff distance is equivalent to solving an NP-Hard optimization problem, deeming the notion impractical for applications. In this paper we propose polynomial algorithm for estimating the so-called modified Gromov-Hausdorff (mGH) distance, whose topological equivalence with the standard Gromov-Hausdorff (GH) distance was established in Mémoli F, 2012. We implement the algorithm for the case of compact metric spaces induced by unweighted graphs as part of Python library $\verb|scikit-tda|$, and demonstrate its performance on real-world and synthetic networks. The algorithm finds the mGH distances exactly on most graphs with the scale-free property. We use the computed mGH distances to successfully detect outliers in real-world social and computer networks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1909_09772 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Efficient estimation of the modified Gromov-Hausdorff distance between unweighted graphs Oles, Vladyslav Lemons, Nathan Panchenko, Alexander Computational Geometry Geometric Topology Metric Geometry Gromov-Hausdorff distances measure shape difference between the objects representable as compact metric spaces, e.g. point clouds, manifolds, or graphs. Computing any Gromov-Hausdorff distance is equivalent to solving an NP-Hard optimization problem, deeming the notion impractical for applications. In this paper we propose polynomial algorithm for estimating the so-called modified Gromov-Hausdorff (mGH) distance, whose topological equivalence with the standard Gromov-Hausdorff (GH) distance was established in Mémoli F, 2012. We implement the algorithm for the case of compact metric spaces induced by unweighted graphs as part of Python library $\verb|scikit-tda|$, and demonstrate its performance on real-world and synthetic networks. The algorithm finds the mGH distances exactly on most graphs with the scale-free property. We use the computed mGH distances to successfully detect outliers in real-world social and computer networks. |
| title | Efficient estimation of the modified Gromov-Hausdorff distance between unweighted graphs |
| topic | Computational Geometry Geometric Topology Metric Geometry |
| url | https://arxiv.org/abs/1909.09772 |