Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2603.13535 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918445115768832 |
|---|---|
| author | Micaletto, Giorgio Nigrelli, Tebe |
| author_facet | Micaletto, Giorgio Nigrelli, Tebe |
| contents | Evaluating Ollivier-Ricci (OR) curvature on large-scale graphs is computationally prohibitive due to the necessity of solving an optimal transport problem for every edge. We bypass this computational bottleneck by deriving explicit, two-sided, piecewise-affine transfer moduli between the transport-based OR curvature and the combinatorial Balanced Forman (BF) curvature introduced by Topping et al. By constructing a lazy transport envelope and augmenting the Jost and Liu bound with a cross-edge matching statistic, we establish deterministic bounds for $\mathfrak{c}_{OR}(i,j)$ parameterized by 2-hop local graph combinatorics. This formulation reduces the edgewise evaluation complexity from an optimal transport linear program to a worst-case $\mathcal{O}(\max_{v \in V} \operatorname{deg}(v)^{1.5})$ time, entirely eliminating the reliance on global solvers. We validate these bounds via distributional analyses on canonical random graphs and empirical networks; the derived analytical bands enclose the empirical distributions independent of degree heterogeneity, geometry, or clustering, providing a scalable, computationally efficient framework for statistical network analysis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_13535 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Edgewise Envelopes Between Balanced Forman and Ollivier-Ricci Curvature Micaletto, Giorgio Nigrelli, Tebe Computation Combinatorics Differential Geometry 05C82 (Primary) 49Q22, 05C21 (Secondary) G.2.1; G.2.2 Evaluating Ollivier-Ricci (OR) curvature on large-scale graphs is computationally prohibitive due to the necessity of solving an optimal transport problem for every edge. We bypass this computational bottleneck by deriving explicit, two-sided, piecewise-affine transfer moduli between the transport-based OR curvature and the combinatorial Balanced Forman (BF) curvature introduced by Topping et al. By constructing a lazy transport envelope and augmenting the Jost and Liu bound with a cross-edge matching statistic, we establish deterministic bounds for $\mathfrak{c}_{OR}(i,j)$ parameterized by 2-hop local graph combinatorics. This formulation reduces the edgewise evaluation complexity from an optimal transport linear program to a worst-case $\mathcal{O}(\max_{v \in V} \operatorname{deg}(v)^{1.5})$ time, entirely eliminating the reliance on global solvers. We validate these bounds via distributional analyses on canonical random graphs and empirical networks; the derived analytical bands enclose the empirical distributions independent of degree heterogeneity, geometry, or clustering, providing a scalable, computationally efficient framework for statistical network analysis. |
| title | Edgewise Envelopes Between Balanced Forman and Ollivier-Ricci Curvature |
| topic | Computation Combinatorics Differential Geometry 05C82 (Primary) 49Q22, 05C21 (Secondary) G.2.1; G.2.2 |
| url | https://arxiv.org/abs/2603.13535 |