Augmentations of Forman's Ricci Curvature and their Applications in Community Detection

Abstract

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.

25 pages, 14 figures

References in corpus (9)

• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Structure and tie strengths in mobile communication networks
• Unfolding the multiscale structure of networks with dynamical Ollivier-Ricci curvature
• Discrete curvature on graphs from the effective resistance
• The inherent community structure of hyperbolic networks
• Enhanced Forman curvature and its relation to Ollivier curvature
• Characterizations of Forman curvature
• Comparative analysis of Forman-Ricci curvature versions applied to the persistent homology of networks