Augmentations of Forman's Ricci Curvature and their Applications in Community Detection
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914919748730880 |
|---|---|
| author | Fesser, Lukas Iváñez, Sergio Serrano de Haro Devriendt, Karel Weber, Melanie Lambiotte, Renaud |
| author_facet | Fesser, Lukas Iváñez, Sergio Serrano de Haro Devriendt, Karel Weber, Melanie Lambiotte, Renaud |
| contents | The notion of curvature on graphs has recently gained traction in the networks community, with the Ollivier-Ricci curvature (ORC) in particular being used for several tasks in network analysis, such as community detection. In this work, we choose a different approach and study augmentations of the discretization of the Ricci curvature proposed by Forman (AFRC). We empirically and theoretically investigate its relation to the ORC and the un-augmented Forman-Ricci curvature. In particular, we provide evidence that the AFRC frequently gives sufficient insight into the structure of a network to be used for community detection, and therefore provides a computationally cheaper alternative to previous ORC-based methods. Our novel AFRC-based community detection algorithm is competitive with an ORC-based approach. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_06474 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Augmentations of Forman's Ricci Curvature and their Applications in Community Detection Fesser, Lukas Iváñez, Sergio Serrano de Haro Devriendt, Karel Weber, Melanie Lambiotte, Renaud Combinatorics Discrete Mathematics Metric Geometry 05C82, 05C10 (Primary) 53C21, 68R10, 05C75 (Secondary) The notion of curvature on graphs has recently gained traction in the networks community, with the Ollivier-Ricci curvature (ORC) in particular being used for several tasks in network analysis, such as community detection. In this work, we choose a different approach and study augmentations of the discretization of the Ricci curvature proposed by Forman (AFRC). We empirically and theoretically investigate its relation to the ORC and the un-augmented Forman-Ricci curvature. In particular, we provide evidence that the AFRC frequently gives sufficient insight into the structure of a network to be used for community detection, and therefore provides a computationally cheaper alternative to previous ORC-based methods. Our novel AFRC-based community detection algorithm is competitive with an ORC-based approach. |
| title | Augmentations of Forman's Ricci Curvature and their Applications in Community Detection |
| topic | Combinatorics Discrete Mathematics Metric Geometry 05C82, 05C10 (Primary) 53C21, 68R10, 05C75 (Secondary) |
| url | https://arxiv.org/abs/2306.06474 |