Garcia-Pulido, Ana Lucia, Hess, Kathryn, Tan, Jane, Turner, Katharine, Wang, Bei and Yerolemou, Naya
(2021)
Graph Pseudometrics from a Topological Point of View.
Research in Computational Topology 2.
Text
top_graph_comparison.pdf - Author Accepted Manuscript Download (804kB) | Preview |
Abstract
We explore pseudometrics for directed graphs in order to better understand their topological properties. The directed flag complex associated to a directed graph provides a useful bridge between network science and topology. Indeed, it has often been observed that phenomena exhibited by real-world networks reflect the topology of their flag complexes, as measured, for example, by Betti numbers or simplex counts. As it is often computationally expensive (or even unfeasible) to determine such topological features exactly, it would be extremely valuable to have pseudometrics on the set of directed graphs that can both detect the topological differences and be computed efficiently. To facilitate work in this direction, we introduce methods to measure how well a graph pseudometric captures the topology of a directed graph. We then use these methods to evaluate some well-established pseudometrics, using test data drawn from several families of random graphs.
Item Type: | Article |
---|---|
Additional Information: | 27 pages, 7 figures |
Uncontrolled Keywords: | math.AT, math.AT, math.MG, math.ST, stat.TH |
Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
Depositing User: | Symplectic Admin |
Date Deposited: | 02 Aug 2021 10:05 |
Last Modified: | 18 Jan 2023 21:35 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3131467 |