Efficient set-theoretic algorithms for computing high-order Forman-Ricci curvature on abstract simplicial complexes
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916240938762240 |
|---|---|
| author | de Souza, Danillo Barros da Cunha, Jonatas T. S. Santos, Fernando A. N. Jost, Jürgen Rodrigues, Serafim |
| author_facet | de Souza, Danillo Barros da Cunha, Jonatas T. S. Santos, Fernando A. N. Jost, Jürgen Rodrigues, Serafim |
| contents | Forman-Ricci curvature (FRC) is a potent and powerful tool for analysing empirical networks, as the distribution of the curvature values can identify structural information that is not readily detected by other geometrical methods. Crucially, FRC captures higher-order structural information of clique complexes of a graph or Vietoris-Rips complexes, which is not readily accessible to alternative methods. However, existing FRC platforms are prohibitively computationally expensive. Therefore, herein we develop an efficient set-theoretic formulation for computing such high-order FRC in simplicial complexes. Significantly, our set theory representation reveals previous computational bottlenecks and also accelerates the computation of FRC. Finally, We provide a pseudo-code, a software implementation coined FastForman, as well as a benchmark comparison with alternative implementations. We envisage that FastForman will be used in Topological and Geometrical Data analysis for high-dimensional complex data sets. Moreover, our development paves the way for future generalisations towards efficient computations of FRC on cell complexes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_11763 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Efficient set-theoretic algorithms for computing high-order Forman-Ricci curvature on abstract simplicial complexes de Souza, Danillo Barros da Cunha, Jonatas T. S. Santos, Fernando A. N. Jost, Jürgen Rodrigues, Serafim Data Analysis, Statistics and Probability Discrete Mathematics Performance Combinatorics Forman-Ricci curvature (FRC) is a potent and powerful tool for analysing empirical networks, as the distribution of the curvature values can identify structural information that is not readily detected by other geometrical methods. Crucially, FRC captures higher-order structural information of clique complexes of a graph or Vietoris-Rips complexes, which is not readily accessible to alternative methods. However, existing FRC platforms are prohibitively computationally expensive. Therefore, herein we develop an efficient set-theoretic formulation for computing such high-order FRC in simplicial complexes. Significantly, our set theory representation reveals previous computational bottlenecks and also accelerates the computation of FRC. Finally, We provide a pseudo-code, a software implementation coined FastForman, as well as a benchmark comparison with alternative implementations. We envisage that FastForman will be used in Topological and Geometrical Data analysis for high-dimensional complex data sets. Moreover, our development paves the way for future generalisations towards efficient computations of FRC on cell complexes. |
| title | Efficient set-theoretic algorithms for computing high-order Forman-Ricci curvature on abstract simplicial complexes |
| topic | Data Analysis, Statistics and Probability Discrete Mathematics Performance Combinatorics |
| url | https://arxiv.org/abs/2308.11763 |