|
|||||
 |
|
|
|
|
|
|
|
Comparing
embedded graphs using average branching distance
Levent Batakci, Abigail Branson, Bryan Castillo, Candace Todd, Erin Wolf Chambers and Elizabeth Munch |
|
Vol. 16 (2023), No. 3, 365–388
|
Abstract |
|
Graphs drawn in the plane are ubiquitous, arising from data sets through a variety of methods ranging from GIS analysis to image classification to shape analysis. A fundamental problem in this type of data is comparison: given a set of such graphs, can we rank how similar they are in such a way that we capture their geometric “shape” in the plane? We explore a method to compare two such embedded graphs, via a simplified combinatorial representation called a tail-less merge tree which encodes the structure based on a fixed direction. First, we examine the properties of a distance designed to compare merge trees called the branching distance, and show that the distance as defined in previous work fails to satisfy some of the requirements of a metric. We incorporate this into a new distance function called average branching distance to compare graphs by looking at the branching distance for merge trees defined over many directions. Despite the theoretical issues, we show that the definition is still quite useful in practice by using our open-source code to cluster data sets of embedded graphs. |
Keywords
topological data analysis, merge tree, embedded graph
|
Mathematical Subject Classification
Primary: 55N31, 62R40, 68R10, 68R12, 68T09
|
Milestones
Received: 31 August 2020
Revised: 3 December 2021
Accepted: 21 June 2022
Published: 10 August 2023
Communicated by Kenneth S. Berenhaut
|
Authors |
| Levent Batakci | |
| Case Western Reserve
University Hummelstown, PA United States |
|
| Abigail Branson | |
| Union University Jackson, TN United States |
|
| Bryan Castillo | |
| Department of Mathematics The University of Arizona Tucson, AZ United States |
|
| Candace Todd | |
| Department of Statistics The Pennsylvania State University University Park, PA United States |
|
| Erin Wolf Chambers | |
| Department of Computer Science Saint Louis University St. Louis, MO United States |
|
| Elizabeth Munch | |
| Department of Computational
Mathematics, Science and Engineering Department of Mathematics Michigan State University East Lansing, MI United States |
|
| © 2023 MSP (Mathematical Sciences Publishers). |
