A Distance for Geometric Graphs via the Labeled Merge Tree Interleaving Distance
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917721108643840 |
|---|---|
| author | Chambers, Erin Wolf Munch, Elizabeth Percival, Sarah Wang, Xinyi |
| author_facet | Chambers, Erin Wolf Munch, Elizabeth Percival, Sarah Wang, Xinyi |
| contents | Geometric graphs appear in many real-world data sets, such as road networks, sensor networks, and molecules. We investigate the notion of distance between embedded graphs and present a metric to measure the distance between two geometric graphs via merge trees. In order to preserve as much useful information as possible from the original data, we introduce a way of rotating the sublevel set to obtain the merge trees via the idea of the directional transform. We represent the merge trees using a surjective multi-labeling scheme and then compute the distance between two representative matrices. We show some theoretically desirable qualities and present two methods of computation: approximation via sampling and exact distance using a kinetic data structure, both in polynomial time. We illustrate its utility by implementing it on two data sets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_09442 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Distance for Geometric Graphs via the Labeled Merge Tree Interleaving Distance Chambers, Erin Wolf Munch, Elizabeth Percival, Sarah Wang, Xinyi Data Structures and Algorithms Computational Geometry General Topology Geometric graphs appear in many real-world data sets, such as road networks, sensor networks, and molecules. We investigate the notion of distance between embedded graphs and present a metric to measure the distance between two geometric graphs via merge trees. In order to preserve as much useful information as possible from the original data, we introduce a way of rotating the sublevel set to obtain the merge trees via the idea of the directional transform. We represent the merge trees using a surjective multi-labeling scheme and then compute the distance between two representative matrices. We show some theoretically desirable qualities and present two methods of computation: approximation via sampling and exact distance using a kinetic data structure, both in polynomial time. We illustrate its utility by implementing it on two data sets. |
| title | A Distance for Geometric Graphs via the Labeled Merge Tree Interleaving Distance |
| topic | Data Structures and Algorithms Computational Geometry General Topology |
| url | https://arxiv.org/abs/2407.09442 |