Cayley–Menger curvature: a geometric approach to discrete curvature on graphs via local simplex embedding
Journal of Complex Networks · 29.06.2026 · 14 (4)
DOI: 10.1093/comnet/cnag028 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Complex Networks, online erschienen am 24.07.2026. Verfasst von David Sierra Porta. Die Arbeit nennt 27 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
We introduce a discrete curvature measure for graphs based on the Cayley–Menger determinant, which we term Cayley–Menger curvature ($ \symbf{\kappa_{\textbf{CM}}} $). For each node, we construct local tetrahedra from its nearest neighbors under the effective resistance metric, compute the Cayley–Menger determinant to embed them in Euclidean space, and extract the circumradius as a proxy for local curvature. Unlike $ \symbf{\kappa_{\textbf{FR}}} $ and $ \symbf{\kappa_{\textbf{OR}}} $, which assign signed curvature values, $ \symbf{\kappa_{\textbf{CM}}} $ is strictly positive by construction and is best interpreted as a measure of local geometric compactness with curvature-like behavior, complementary to—rather than a replacement for—signed discrete curvatures. We validate $ \symbf{\kappa_{\textbf{CM}}} $ on graphs with analytically known geometric properties—lattices, trees, complete graphs, and cycles—and demonstrate that it produces curvature values consistent with expected flat, hyperbolic, and spherical geometries. Comparison with Forman-Ricci ($ \symbf{\kappa_{\textbf{FR}}} $) and Ollivier-Ricci ($ \symbf{\kappa_{\textbf{OR}}} $) curvatures across a battery of benchmark networks reveals that $ \symbf{\kappa_{\textbf{CM}}} $ captures geometric information that is largely independent of these established measures (Spearman $ \symbf{|\rho|\leq 0.47} $ in most cases, while $ \symbf{\kappa_{\textbf{FR}}} $ and $ \symbf{\kappa_{\textbf{OR}}} $ correlate at $ \symbf{\rho \gt 0.7} $). As a demonstration of practical utility, we show that $ \symbf{\kappa_{\textbf{CM}}} $ alone outperforms both $ \symbf{\kappa_{\textbf{FR}}} $ and $ \symbf{\kappa_{\textbf{OR}}} $ as a feature for community detection in stochastic block models, achieving an order-of-magnitude improvement in Adjusted Rand Index over $ \symbf{\kappa_{\textbf{FR}}} $ and $ \symbf{\kappa_{\textbf{OR}}} $ used alone, though we note that absolute ARI values remain moderate and the baseline clustering method (Ward linkage) was chosen for simplicity rather than performance; the result demonstrates discriminative power of the $ \symbf{\kappa_{\textbf{CM}}} $ feature, not a claim about state-of-the-art community detection. Scalability benchmarks confirm that $ \symbf{\kappa_{\textbf{CM}}} $ computes faster than $ \symbf{\kappa_{\textbf{OR}}} $ for graphs up to $ \symbf{n\,=\,5000} $ nodes. These results establish the Cayley–Menger curvature as a complementary tool in the discrete curvature toolkit, offering direct geometric interpretability grounded in distance geometry.
Zitieren
APA
Porta, D. S. (2026). Cayley–Menger curvature: a geometric approach to discrete curvature on graphs via local simplex embedding. Journal of Complex Networks, 14(4). https://doi.org/10.1093/comnet/cnag028
Vancouver
Porta DS. Cayley–Menger curvature: a geometric approach to discrete curvature on graphs via local simplex embedding. Journal of Complex Networks. 2026;14(4). doi:10.1093/comnet/cnag028
BibTeX
@article{Porta2026,
author = {Porta, David Sierra},
title = {Cayley–Menger curvature: a geometric approach to discrete curvature on graphs via local simplex embedding},
journal = {Journal of Complex Networks},
year = {2026},
volume = {14},
number = {4},
doi = {10.1093/comnet/cnag028}
}
EUVIMED