Exploring the space of graphs with fixed discrete curvatures

Abstract

Discrete curvatures are quantities associated to the nodes and edges of a graph that reflect the local geometry around them. These curvatures have a rich mathematical theory and they have recently found success as a tool to analyze networks across a wide range of domains. In this work, we consider the problem of constructing graphs with a prescribed set of discrete edge curvatures, and explore the space of such graphs. We address this problem in two ways: first, we develop an evolutionary algorithm to sample graphs with discrete curvatures close to a given set. We use this algorithm to explore how other network statistics vary when constrained by the discrete curvatures in the network. Second, we solve the exact reconstruction problem for the specific case of Forman-Ricci curvature. By leveraging the theory of Markov bases, we obtain a finite set of rewiring moves that connects the space of all graphs with a fixed discrete curvature.

Second version. 24 pages, 10 figures

References in corpus (23)

• Emergence of scaling in random networks
• The large-scale organization of metabolic networks
• Epidemic processes in complex networks
• Networks beyond pairwise interactions: structure and dynamics
• Community detection in complex networks using Extremal Optimization
• Scale-free networks are rare
• What are higher-order networks?
• Network Geometry
• Scale-free Networks Well Done
• Ricci curvature of finite Markov chains via convexity of the entropy
• Comparative analysis of two discretizations of Ricci curvature for complex networks
• Evolutionary reconstruction of networks
• Emergent Complex Network Geometry
• Clustering implies geometry in networks
• Bakry-Emery curvature and diameter bounds on graphs
• Combinatorial Quantum Gravity: Geometry from Random Bits
• Unfolding the multiscale structure of networks with dynamical Ollivier-Ricci curvature
• Ricci curvature on polyhedral surfaces via optimal transportation
• Thresholding normally distributed data creates complex networks
• Discrete curvature on graphs from the effective resistance
• Enhanced Forman curvature and its relation to Ollivier curvature
• Edge-based analysis of networks: Curvatures of graphs and hypergraphs
• Irreducible Markov Chains on spaces of graphs with fixed degree-color sequences