New formula connects average hyperbolicity to tree approximation error
A quantitative tree-likeness bound from average hyperbolicity
Data Structures and Algorithms
Summary
Sometimes, complex networks can be simplified by representing them as trees, which makes analysis easier. The authors studied how a certain math property called average hyperbolicity affects how well these networks can be approximated by trees. They found a clear formula that shows when this approximation will be good based on the value of average hyperbolicity. Their method is simpler and provides actual numbers, improving on previous results that were more abstract. This work helps understand the limits and accuracy of using tree-like models for similarity data.
What this means in practice
- •For network architects: Predict how well complex network similarities can be approximated by tree structures to guide network design choices.
- •For machine learning engineers: Improve clustering algorithms by understanding bounds on error when approximating similarity data as trees.
A theory result. No direct application yet.
Authors
Joon-Hyeok Yim
Abstract
Chatterjee and Sloman proved that a bounded measurable similarity function with sufficiently small average Gromov hyperbolicity admits a tree representation with small mean approximation error. Their argument uses a weighted version of Szemerédi's regularity lemma and does not yield useful quantitative bounds. Here, we establish an explicit relation between average hyperbolicity and mean tree approximation error. For a similarity function $s:S\times S\to[0,b]$, we prove that \[ \Tree(s) \leq (63/e)^{1/3} \sqrt[3]{b^2 \Hyp(s)} \leq 2.8512 \sqrt[3]{b^2 \Hyp(s)}.\] The proof uses a simple pivoting construction inspired by \textsc{KwikCluster}. We also discuss the optimal dependence on average hyperbolicity, including a square-root lower bound, and connections with ultrametric fitting.