Exploring the space of graphs with fixed discrete curvatures
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910549837611008 |
|---|---|
| author | Roost, Michelle Devriendt, Karel Zucal, Giulio Jost, Jürgen |
| author_facet | Roost, Michelle Devriendt, Karel Zucal, Giulio Jost, Jürgen |
| contents | Discrete curvatures are quantities associated to the nodes and edges of a graph that reflect the local geometry around them. These curvatures have a rich mathematical theory and they have recently found success as a tool to analyze networks across a wide range of domains. In this work, we consider the problem of constructing graphs with a prescribed set of discrete edge curvatures, and explore the space of such graphs. We address this problem in two ways: first, we develop an evolutionary algorithm to sample graphs with discrete curvatures close to a given set. We use this algorithm to explore how other network statistics vary when constrained by the discrete curvatures in the network. Second, we solve the exact reconstruction problem for the specific case of Forman-Ricci curvature. By leveraging the theory of Markov bases, we obtain a finite set of rewiring moves that connects the space of all graphs with a fixed discrete curvature. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_18203 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Exploring the space of graphs with fixed discrete curvatures Roost, Michelle Devriendt, Karel Zucal, Giulio Jost, Jürgen Physics and Society Discrete Mathematics Combinatorics 05C30, 05C50, 05C82, 05C85, 68W50 Discrete curvatures are quantities associated to the nodes and edges of a graph that reflect the local geometry around them. These curvatures have a rich mathematical theory and they have recently found success as a tool to analyze networks across a wide range of domains. In this work, we consider the problem of constructing graphs with a prescribed set of discrete edge curvatures, and explore the space of such graphs. We address this problem in two ways: first, we develop an evolutionary algorithm to sample graphs with discrete curvatures close to a given set. We use this algorithm to explore how other network statistics vary when constrained by the discrete curvatures in the network. Second, we solve the exact reconstruction problem for the specific case of Forman-Ricci curvature. By leveraging the theory of Markov bases, we obtain a finite set of rewiring moves that connects the space of all graphs with a fixed discrete curvature. |
| title | Exploring the space of graphs with fixed discrete curvatures |
| topic | Physics and Society Discrete Mathematics Combinatorics 05C30, 05C50, 05C82, 05C85, 68W50 |
| url | https://arxiv.org/abs/2402.18203 |