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

Internet publication

The notion of curvature on graphs has recently gained traction in the networks com- munity, 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 aug- mentations 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. The codebase for fast and efficient computations of AFRC and the experiments in this article will be made publicly available upon publication.

Authors: Fesser, L; Serrano de Haro Iváñez, S; Devriendt, K; Weber, M; Lambiotte, R

• Publication status: Published
• Peer review status: Not peer reviewed
• Host title: arXiv
• Publication date: 2023-06-10
• DOI: 10.48550/arXiv.2306.06474
• Language: English
• Keywords: community detection; discrete curvature; network analysis