Journal of Physics: Complexity (Jan 2024)

Augmentations of Forman’s Ricci curvature and their applications in community detection

  • Lukas Fesser,
  • Sergio Serrano de Haro Iváñez,
  • Karel Devriendt,
  • Melanie Weber,
  • Renaud Lambiotte

DOI
https://doi.org/10.1088/2632-072X/ad64a3
Journal volume & issue
Vol. 5, no. 3
p. 035010

Abstract

Read online

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.

Keywords