Clustering implies geometry in networks
arXiv:1604.01575 · doi:10.1103/PhysRevLett.116.208302
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 (36)
- Statistical mechanics of complex networks
- Spatial Networks
- Defining and identifying communities in networks
- Hyperbolic Geometry of Complex Networks
- The statistical mechanics of networks
- Sustaining the Internet with Hyperbolic Mapping
- Class of correlated random networks with hidden variables
- Entropy measures for complex networks: Toward an information theory of complex topologies
- Self-similarity of complex networks and hidden metric spaces
- Hierarchical Block Structures and High-resolution Model Selection in Large Networks
- Parsimonious module inference in large networks
- The entropy of randomized network ensembles
- Assessing the relevance of node features for network structure
- Maximum likelihood: extracting unbiased information from complex networks
- Quantifying randomness in real networks
- Generalized Bose-Fermi statistics and structural correlations in weighted networks
- Entropy of stochastic blockmodel ensembles
- Solution for the properties of a clustered network
- Interdisciplinary and physics challenges of Network Theory
- Random geometric graphs with general connection functions
- Emergent Complex Network Geometry
- Breaking of ensemble equivalence in networks
- Emergence of Soft Communities from Geometric Preferential Attachment
- Connectivity of soft random geometric graphs
- Generalized communities in networks
- Navigable Networks as Nash Equilibria of Navigation Games
- Unbiased sampling of network ensembles
- Deciphering the global organization of clustering in real complex networks
- The Asymptotics of Large Constrained Graphs
- Beyond the locally tree-like approximation for percolation on real networks
- Entropy distribution and condensation in random networks with a given degree distribution
- Reducing Degeneracy in Maximum Entropy Models of Networks
- Clustering Phase Transitions and Hysteresis: Pitfalls in Constructing Network Ensembles
- Latent Self-Exciting Point Process Model for Spatial-Temporal Networks
- Low-temperature behaviour of social and economic networks
- Networks with arbitrary edge multiplicities
Cited by in corpus (50)
- Networks beyond pairwise interactions: structure and dynamics
- Network Geometry
- Machine learning meets network science: dimensionality reduction for fast and efficient embedding of networks in the hyperbolic space
- 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
- Embedding Graphs in Lorentzian Spacetime
- The inherent community structure of hyperbolic networks
- Self-Assembly of Geometric Space from Random Graphs
- Quantum Causal Graph Dynamics
- Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution
- Emergence of the Circle in a Statistical Model of Random Cubic Graphs
- Gender and collaboration patterns in a temporal scientific authorship network
- 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
- Combinatorial Quantum Gravity: Emergence of Geometric Space from Random Graphs
- Emergent time, cosmological constant and boundary dimension at infinity in combinatorial quantum gravity
- Geometric randomization of real networks with prescribed degree sequence
- Isolation and connectivity in random geometric graphs with self-similar intensity measures
- Corrected mean-field model for random sequential adsorption on random geometric graphs
- Regular graphs with linearly many triangles
- Topological Network Entanglement as Order Parameter for the Emergence of Geometry
- Temporal connectivity in finite networks with non-uniform measures
- 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
- Exploring the space of graphs with fixed discrete curvatures
- Dimension reduction in vertex-weighted exponential random graphs
- Connectivity of 1d random geometric graphs