Clustering implies geometry in networks

Abstract

Network models with latent geometry have been used successfully in many applications in network science and other disciplines, yet it is usually impossible to tell if a given real network is geometric, meaning if it is a typical element in an ensemble of random geometric graphs. Here we identify structural properties of networks that guarantee that random graphs having these properties are geometric. Specifically we show that random graphs in which expected degree and clustering of every node are fixed to some constants are equivalent to random geometric graphs on the real line, if clustering is sufficiently strong. Large numbers of triangles, homogeneously distributed across all nodes as in real networks, are thus a consequence of network geometricity. The methods we use to prove this are quite general and applicable to other network ensembles, geometric or not, and to certain problems in quantum gravity.

References in corpus (11)

• Hyperbolic Geometry of Complex Networks
• Sustaining the Internet with Hyperbolic Mapping
• Self-similarity of complex networks and hidden metric spaces
• Parsimonious module inference in large networks
• The entropy of randomized network ensembles
• Maximum likelihood: extracting unbiased information from complex networks
• Generalized Bose-Fermi statistics and structural correlations in weighted networks
• Solution for the properties of a clustered network
• Emergent Complex Network Geometry
• Emergence of Soft Communities from Geometric Preferential Attachment
• Unbiased sampling of network ensembles

Cited by in corpus (48)

• Networks beyond pairwise interactions: structure and dynamics
• Network Geometry
• Eigenvalue tunnelling and decay of quenched random networks
• Statistical properties of the quantum internet
• Metric clusters in evolutionary games on scale-free networks
• Complex network view of evolving manifolds
• Link prediction with hyperbolic geometry
• Combinatorial Quantum Gravity: Geometry from Random Bits
• Systematic evaluation of a new combinatorial curvature for complex networks
• Small worlds and clustering in spatial networks
• Ollivier-Ricci curvature convergence in random geometric graphs
• Homophily as a Process Generating Social Networks: Insights from Social Distance Attachment Model
• Local clustering in scale-free networks with hidden variables
• The inherent community structure of hyperbolic networks
• Quantum Causal Graph Dynamics
• Self-Assembly of Geometric Space from Random Graphs
• Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution
• Gender and collaboration patterns in a temporal scientific authorship network
• Emergence of the Circle in a Statistical Model of Random Cubic Graphs
• Enhanced Forman curvature and its relation to Ollivier curvature
• Finding shortest and nearly shortest path nodes in large substantially incomplete networks
• Detecting hyperbolic geometry in networks: why triangles are not enough
• Structural measures of similarity and complementarity in complex networks
• Model-independent methods for embedding directed networks into Euclidean and hyperbolic spaces
• Local-ring network automata and the impact of hyperbolic geometry in complex network link-prediction
• Optimisation of the coalescent hyperbolic embedding of complex networks
• Spatial networks with wireless applications
• The birth of geometry in exponential random graphs
• EM-Based Smooth Graphon Estimation Using Bayesian and Spline-Based Approaches
• Mixing Time of Vertex-Weighted Exponential Random Graphs
• Ollivier curvature of random geometric graphs converges to Ricci curvature of their Riemannian manifolds
• Random graphs and real networks with weak geometric coupling
• Geometric evolution of complex networks
• Emergent time, cosmological constant and boundary dimension at infinity in combinatorial quantum gravity
• Combinatorial Quantum Gravity: Emergence of Geometric Space from Random Graphs
• Isolation and connectivity in random geometric graphs with self-similar intensity measures
• Geometric randomization of real networks with prescribed degree sequence
• Corrected mean-field model for random sequential adsorption on random geometric graphs
• Regular graphs with linearly many triangles
• Temporal connectivity in finite networks with non-uniform measures
• Topological Network Entanglement as Order Parameter for the Emergence of Geometry
• Critical scaling limits of the random intersection graph
• Symmetry-driven embedding of networks in hyperbolic space
• Real-World Networks are Low-Dimensional: Theoretical and Practical Assessment
• Hidden space reconstruction inspires link prediction in complex networks
• Connectivity of 1d random geometric graphs
• Dimension reduction in vertex-weighted exponential random graphs
• Exploring the space of graphs with fixed discrete curvatures