Coarse Geometry of Evolving Networks

Melanie Weber, Emil Saucan, and Jürgen Jost

Contact the author: Please use for correspondence this email.
Submission date: 12. Oct. 2016 (revised version: May 2018)
Pages: 28
published in: Journal of complex networks, 6 (2018) 5, p. 706-732 
DOI number (of the published article): 10.1093/comnet/cnx049
Bibtex
MSC-Numbers: 53C44, 05C82
Download full preprint: PDF (2938 kB)

Abstract:
Traditionally, network analysis is based on local properties of vertices, like their degree or clustering, and their statistical behavior across the network in question. This paper develops an approach which is different in two respects. We investigate edge-based properties, and we define global characteristics of networks directly. More concretely, we start with Forman’s notion of the Ricci curvature of a graph, or more generally, a polyhedral complex. This will allow us to pass from a graph as representing a network to a polyhedral complex for instance by filling in triangles into connected triples of edges and to investigate the resulting effect on the curvature. This is insightful for two reasons: First, we can define a curvature flow in order to asymptotically simplify a network and reduce it to its essentials. Second, using a construction of Bloch, which yields a discrete Gauss-Bonnet theorem, we have the Euler characteristic of a network as a global characteristic. These two aspects beautifully merge in the sense that the asymptotic properties of the curvature flow are indicated by that Euler characteristic.