Forman-Ricci Curvature for Complex Networks

Abstract

With the rapid rise of data science since the late 1990s, networks have emerged as a powerful tool to represent complex systems. We present geometric tools for characterizing such complex networks through the analysis of so far widely neglected network properties to provide novel insights into their structure and evolution. For this, we introduce a discrete Forman-Ricci curvature and its corresponding geometric flows as characteristics for complex networks, thus extending the common approach of node-based network analysis with edge-based characteristics. We apply the proposed network-analytic methods to static and dynamic complex networks and compare the results with established node- based characteristics. Our work suggests a number of applications for data mining including denoising and clustering of experimental data, as well as extrapolation of network evolution. In addition, we extend the introduced formalism to higher dimensions in an attempt to study the shape of networks. While there exists a body of knowledge concerned with local network characteristics, the systematic study of global network structure is a largely untouched field. Here, we introduce theoretical tools to classify the shape of a given network based on Forman’s Ricci curvature for graphs and its associated Ricci flow. Our setting allows for a network- theoretic formulation of a Gauß-Bonnet style theorem and the computation of Euler characteristics. Attempting to describe the long-term behavior of networks qualitatively, we introduce prototype networks that give rise to a global classification scheme based on Ricci- curvature. Besides highlighting theoretical aspects, we discuss real-world examples focusing on areas that are currently of vital interest for computational research. This includes examples from life sciences as well as social networks. (Joint work with Emil Saucan and Jürgen Jost at the Max Planck Institute for Mathematics in the Sciences in Leipzig, Germany.)

Date
Location
Princeton, USA
Links