Hyperbolic Geometry of Complex Networks

Abstract

We develop a geometric framework to study the structure and function of complex networks. We assume that hyperbolic geometry underlies these networks, and we show that with this assumption, heterogeneous degree distributions and strong clustering in complex networks emerge naturally as simple reflections of the negative curvature and metric property of the underlying hyperbolic geometry. Conversely, we show that if a network has some metric structure, and if the network degree distribution is heterogeneous, then the network has an effective hyperbolic geometry underneath. We then establish a mapping between our geometric framework and statistical mechanics of complex networks. This mapping interprets edges in a network as non-interacting fermions whose energies are hyperbolic distances between nodes, while the auxiliary fields coupled to edges are linear functions of these energies or distances. The geometric network ensemble subsumes the standard configuration model and classical random graphs as two limiting cases with degenerate geometric structures. Finally, we show that targeted transport processes without global topology knowledge, made possible by our geometric framework, are maximally efficient, according to all efficiency measures, in networks with strongest heterogeneity and clustering, and that this efficiency is remarkably robust with respect to even catastrophic disturbances and damages to the network structure.

References in corpus (29)

• Emergence of scaling in random networks
• Community structure in social and biological networks
• Gauge Theory Correlators from Non-Critical String Theory
• The Large N Limit of Superconformal Field Theories and Supergravity
• Power laws, Pareto distributions and Zipf's law
• Hierarchical organization of modularity in metabolic networks
• Hierarchical structure and the prediction of missing links in networks
• Hierarchical Organization in Complex Networks
• How Popular is Your Paper? An Empirical Study of the Citation Distribution
• Search in Power-Law Networks
• Identity and Search in Social Networks
• The statistical mechanics of networks
• Navigability of Complex 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
• Cut-offs and finite size effects in scale-free networks
• The Simultaneous Evolution of Author and Paper Networks
• The entropy of network ensembles
• AS Relationships: Inference and Validation
• Log-Networks
• Generalized Bose-Fermi statistics and structural correlations in weighted networks
• Tuning clustering in random networks with arbitrary degree distributions
• Hierarchy Measures in Complex Networks
• Systematic Topology Analysis and Generation Using Degree Correlations
• Curvature and temperature of complex networks
• Principles of statistical mechanics of random networks
• The Invariant Set Postulate: A New Geometric Framework for the Foundations of Quantum Theory and the Role Played by Gravity

Cited by in corpus (312)

• Spatial Networks
• The physics of spreading processes in multilayer networks
• Popularity versus Similarity in Growing Networks
• Hyperbolic Lattices in Circuit Quantum Electrodynamics
• Community structure and scale-free collections of Erdös-Rényi graphs
• A Survey of Graph Neural Networks for Social Recommender Systems
• Network Geometry
• Network Analysis of Particles and Grains
• Machine learning meets network science: dimensionality reduction for fast and efficient embedding of networks in the hyperbolic space
• Identifying optimal targets of network attack by belief propagation
• Scale-free Networks Well Done
• Emergent Hyperbolic Network Geometry
• Simplicial complexes and complex systems
• Network Mapping by Replaying Hyperbolic Growth
• Engineering Parallel Algorithms for Community Detection in Massive Networks
• The Large Scale Curvature of Networks
• Network geometry with flavor: from complexity to quantum geometry
• Hidden geometric correlations in real multiplex networks
• Progresses and Challenges in Link Prediction
• Differentiable Graph Module (DGM) for Graph Convolutional Networks
• Comparative analysis of two discretizations of Ricci curvature for complex networks
• A Survey on Centrality Metrics and Their Implications in Network Resilience
• Multiscale unfolding of real networks by geometric renormalization
• Network Cosmology
• Interdisciplinary and physics challenges of Network Theory
• Quantum Simulation of Hyperbolic Space with Circuit Quantum Electrodynamics: From Graphs to Geometry
• Discrete-time Temporal Network Embedding via Implicit Hierarchical Learning in Hyperbolic Space
• Ordinary Percolation with Discontinuous Transitions
• Emergence of overlap in ensembles of spatial multiplexes and statistical mechanics of spatial interacting networks ensembles
• Emergent Complex Network Geometry
• A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communities
• The hidden geometry of weighted complex networks
• Network Geometry Inference using Common Neighbors
• Clustering implies geometry in networks
• An Experimental Investigation of Hyperbolic Routing with a Smart Forwarding Plane in NDN
• Navigable Networks as Nash Equilibria of Navigation Games
• Generalized communities in networks
• Synchronization in Network Geometries with Finite Spectral Dimension
• Circuit Quantum Electrodynamics in Hyperbolic Space: From Photon Bound States to Frustrated Spin Models
• Deciphering the global organization of clustering in real complex networks
• Navigable maps of structural brain networks across species
• Principled approach to the selection of the embedding dimension of networks
• Complex Quantum Network Geometries: Evolution and Phase Transitions
• Geometric correlations mitigate the extreme vulnerability of multiplex networks against targeted attacks
• Topological Percolation on Hyperbolic Simplicial Complexes
• Random Graph Modeling: A survey of the concepts
• Scale-free networks with exponent one
• Metric clusters in evolutionary games on scale-free networks
• Superlinear and sublinear urban scaling in geographical network model of the city
• Hyperbolic Graph Generator
• Network Geometry and Complexity
• Characterizing the analogy between hyperbolic embedding and community structure of complex networks
• Hyperbolic Band Theory under Magnetic Field and Dirac Cones on a Higher Genus Surface
• A Survey on Network Embedding
• Artificial Benchmark for Community Detection (ABCD): Fast Random Graph Model with Community Structure
• Link prediction with hyperbolic geometry
• Hyperbolic Entailment Cones for Learning Hierarchical Embeddings
• Does the brain behave like a (complex) network? I. Dynamics
• GLEE: Geometric Laplacian Eigenmap Embedding
• Explosion in weighted Hyperbolic Random Graphs and Geometric Inhomogeneous Random Graphs
• Small worlds and clustering in spatial networks
• ACE-HGNN: Adaptive Curvature Exploration Hyperbolic Graph Neural Network
• Soft communities in similarity space
• Entropy distribution and condensation in random networks with a given degree distribution
• Detecting the ultra low dimensionality of real networks
• Constant Curvature Graph Convolutional Networks
• Hyperbolicity Measures "Democracy" in Real-World Networks
• The Simplex Geometry of Graphs
• Latent geometry of bipartite networks
• Exploring complex networks via topological embedding on surfaces
• Reconstructing networks
• Where are we in embedding spaces? A Comprehensive Analysis on Network Embedding Approaches for Recommender Systems
• Complex Quantum Network Manifolds in Dimension $d>2$ are Scale-Free
• Universal mean-field framework for SIS epidemics on networks, based on graph partitioning and the isoperimetric inequality
• A class of models for random hypergraphs
• Geohyperbolic Routing and Addressing Schemes
• Dimensionality of social networks using motifs and eigenvalues
• Supersymmetric multiplex networks described by coupled Bose and Fermi statistics
• HGWaveNet: A Hyperbolic Graph Neural Network for Temporal Link Prediction
• Anderson Localization on the Bethe Lattice using Cages and the Wegner Flow
• A simple, distance-dependent formulation of the Watts-Strogatz model for directed and undirected small-world networks
• Performance of Hyperbolic Geometry Models on Top-N Recommendation Tasks
• The inherent community structure of hyperbolic networks
• Embedding Graphs in Lorentzian Spacetime
• What is the dimension of citation space?
• Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution
• Practical Minimum Cut Algorithms
• The diameter of KPKVB random graphs
• Hidden Variables in Bipartite Networks
• Skip-gram word embeddings in hyperbolic space
• Persistent homology of unweighted complex networks via discrete Morse theory
• Bridging the gap between graphs and networks
• Diffusion geometry of multiplex and interdependent systems
• Average Distance in a General Class of Scale-Free Networks with Underlying Geometry
• Emergence of the Circle in a Statistical Model of Random Cubic Graphs
• A Self-supervised Riemannian GNN with Time Varying Curvature for Temporal Graph Learning
• Poincaré Wasserstein Autoencoder
• Non-Euclidean Universal Approximation
• HyperML: A Boosting Metric Learning Approach in Hyperbolic Space for Recommender Systems
• Quantum-Classical Transitions in Complex Networks
• Scalable Hyperbolic Recommender Systems
• Finding shortest and nearly shortest path nodes in large substantially incomplete networks
• Analysis of English free association network reveals mechanisms of efficient solution of Remote Association Tests
• Hyperbolic Geometric Graph Representation Learning for Hierarchy-imbalance Node Classification
• Classical Information Theory of Networks
• HyperKG: Hyperbolic Knowledge Graph Embeddings for Knowledge Base Completion
• Continuous-time quantum walk spatial search on the Bollobás scale-free network
• Emergence of geometric Turing patterns in complex networks
• Scaling theory of fractal complex networks
• Detecting hyperbolic geometry in networks: why triangles are not enough
• Geometric explanation of the rich-club phenomenon in complex networks
• Scale-free networks embedded in fractal space
• Similarity forces and recurrent components in human face-to-face interaction networks
• Crossing on hyperbolic lattices
• Long-range quantum energy teleportation and distribution on a hyperbolic quantum network
• Duality between equilibrium and growing networks
• New Phenomena in Large-Scale Internet Traffic
• Scaling of Clusters near Discontinuous Percolation Transitions in Hyperbolic Networks
• Low-temperature behaviour of social and economic networks
• A geometry-induced topological phase transition in random graphs
• An Unsupervised Framework for Comparing Graph Embeddings
• Collective navigation of complex networks: Participatory greedy routing
• Model-independent methods for embedding directed networks into Euclidean and hyperbolic spaces
• Random hyperbolic graphs in $d+1$ dimensions
• Hyperbolic Graph Attention Network
• Hidden geometry and dynamics of complex networks: Spin reversal in nanoassemblies with pairwise and triangle-based interactions
• Spatial effects in real networks: measures, null models, and applications
• Link persistence and conditional distances in multiplex networks
• k-core structure of real multiplex networks
• Hyperbolic Node Embedding for Signed Networks
• Scale-invariant geometric random graphs
• Percolation Thresholds in Hyperbolic Lattices
• Local-ring network automata and the impact of hyperbolic geometry in complex network link-prediction
• Weighted hypersoft configuration model
• Embedding Node Structural Role Identity into Hyperbolic Space
• Growing hyperbolic networks beyond two dimensions: the generalised popularity-similarity optimisation model
• Limit theory of isolated and extreme points in hyperbolic random geometric graphs
• Simplicial cascades are orchestrated by the multidimensional geometry of neuronal complexes
• Optimisation of the coalescent hyperbolic embedding of complex networks
• Network Renormalization
• Dynamic Hidden-Variable Network Models
• Multiscale network renormalization: scale-invariance without geometry
• Dulmage-Mendelsohn percolation: Geometry of maximally-packed dimer models and topologically-protected zero modes on site-diluted bipartite lattices
• Latent geometry and dynamics of proximity networks
• Unitary Entanglement Construction in Hierarchical Networks
• Exploration of Large Networks with Covariates via Fast and Universal Latent Space Model Fitting
• The sum of edge lengths in random linear arrangements
• Hyperbolic Deep Neural Networks: A Survey
• Subgraphs in preferential attachment models
• Statistical mechanics of random geometric graphs: Geometry-induced first order phase transition
• Benchmarks for Graph Embedding Evaluation
• Finite-size scaling of geometric renormalization flows in complex networks
• Scale-free network clustering in hyperbolic and other random graphs
• Knowledge Association with Hyperbolic Knowledge Graph Embeddings
• Maximally modular structure of growing hyperbolic networks
• Mean-field universality class induced by weak hyperbolic curvatures
• Detecting local perturbations of networks in a latent hyperbolic embedding space
• Link prediction for egocentrically sampled networks
• Growing homophilic networks are natural navigable small worlds
• Grand canonical ensembles of sparse networks and Bayesian inference
• Cliques in geometric inhomogeneous random graph
• Zoo Guide to Network Embedding
• Complex systems: features, similarity and connectivity
• On the diameter of hyperbolic random graphs
• Free Energy Analysis of Spin Models on Hyperbolic Lattice Geometries
• Spatial search by continuous-time quantum walks on renormalized Internet networks
• Spectral clustering on spherical coordinates under the degree-corrected stochastic blockmodel
• Ollivier curvature of random geometric graphs converges to Ricci curvature of their Riemannian manifolds
• Duality between predictability and reconstructability in complex systems
• Hamiltonian Dynamics of Preferential Attachment
• Querying Probabilistic Neighborhoods in Spatial Data Sets Efficiently
• Fortran code for generating random probability vectors, unitaries, and quantum states
• Fundamental dynamics of popularity-similarity trajectories in real networks
• Duality between preferential attachment and static random networks on hyperbolic spaces
• Linear embeddings of graphs and graph limits
• Levy geometric graphs
• Multi-layer network approach in modeling epidemics in an urban town
• Effect of clustering on Turing instability in complex networks
• Interplay between tie strength and neighbourhood topology in complex networks: Granovetter's theory and beyond
• Understanding and Mitigating Hyperbolic Dimensional Collapse in Graph Contrastive Learning
• On the External Validity of Average-Case Analyses of Graph Algorithms
• The contact process on random hyperbolic graphs: metastability and critical exponents
• Random graphs and real networks with weak geometric coupling
• Hyperbolic Variational Graph Neural Network for Modeling Dynamic Graphs
• Scaling of the clustering function in spatial inhomogeneous random graphs
• Forman-Ricci curvature and Persistent homology of unweighted complex networks
• Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT
• Topological estimation of the latent geometry of a complex network
• Iterative embedding and reweighting of complex networks reveals community structure
• Privacy-Preserving Representation Learning on Graphs: A Mutual Information Perspective
• From Node Embedding To Community Embedding : A Hyperbolic Approach
• Linear Work Generation of R-MAT Graphs
• Statistical physics of exchangeable sparse simple networks, multiplex networks and simplicial complexes
• The Fitness-Corrected Block Model, or how to create maximum-entropy data-driven spatial social networks
• Learning the mechanisms of network growth
• Geometric evolution of complex networks
• Multi-Manifold Learning for Large-scale Targeted Advertising System
• Navigability of Random Geometric Graphs in the Universe and Other Spacetimes
• Model-free hidden geometry of complex networks
• Hyperbolic Mapping of Human Proximity Networks
• Degree correlations in scale-free null models
• Modeling spatial social complex networks for dynamical processes
• A Hyperbolic-to-Hyperbolic Graph Convolutional Network
• Greedy Routing and the Algorithmic Small-World Phenomenom
• Greedy routing optimisation in hyperbolic networks
• Strange Attractors in Complex Networks
• Tree! I am no Tree! I am a Low Dimensional Hyperbolic Embedding
• Symmetric Spaces for Graph Embeddings: A Finsler-Riemannian Approach
• Generalised thresholding of hidden variable network models with scale-free property
• Bounds of percolation thresholds on hyperbolic lattices
• Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs
• Cluster-size decay in supercritical long-range percolation
• Geometric randomization of real networks with prescribed degree sequence
• Graph Distance from the Topological View of Non-backtracking Cycles
• Hyperbolic embedding of brain networks detects regions disrupted by neurodegeneration in Alzheimer's disease
• Isolation and connectivity in random geometric graphs with self-similar intensity measures
• Hyperbolic Deep Learning for Foundation Models: A Survey
• A unified Fourier slice method to derive ridgelet transform for a variety of depth-2 neural networks
• Boundary-field-driven control of discontinuous phase transitions on hyperbolic lattices
• Geometric detection of hierarchical backbones in real networks
• Random Regular Graphs are not Asymptotically Gromov Hyperbolic
• Hyperbolicity, degeneracy, and expansion of random intersection graphs
• Complex Networks in the Framework of Nonassociative Geometry
• Directed Graph Embeddings in Pseudo-Riemannian Manifolds
• DeepHGCN: Toward Deeper Hyperbolic Graph Convolutional Networks
• Fast generation of complex networks with underlying hyperbolic geometry
• Can our spacetime emerge from anti -- de Sitter space?
• Hyperbolic Neural Collaborative Recommender
• Hyperbolic Generative Adversarial Network
• Community detection in hypergraphs through hyperedge percolation
• Beyond traditional box-covering: Determining the fractal dimension of complex networks using a fixed number of boxes of flexible diameter
• Emergence of metastability in frustrated oscillatory networks: the key role of hierarchical modularity
• The sharp threshold for jigsaw percolation in random graphs
• Exact rank-reduction of network models
• Topology and Geometry of the Third-Party Domains Ecosystem: Measurement and Applications
• On the duration of face-to-face contacts
• Stopping explosion by penalising transmission to hubs in scale-free spatial random graphs
• Unit Ball Model for Embedding Hierarchical Structures in the Complex Hyperbolic Space
• Manifold structure in graph embeddings
• Neighborhood Growth Determines Geometric Priors for Relational Representation Learning
• Critical scaling limits of the random intersection graph
• Degree-penalized contact processes
• Finite-size effects in exponential random graphs and cluster evaporation
• Competition and evolution in restricted space
• Gaussian Networks Generated by Random Walks
• Greed is Good for Deterministic Scale-Free Networks
• Dynamics of hot random hyperbolic graphs
• Systematic comparison of graph embedding methods in practical tasks
• Latent Geometry Inspired Graph Dissimilarities Enhance Affinity Propagation Community Detection in Complex Networks
• Policy Gradient Approach to Compilation of Variational Quantum Circuits
• Uncovering Exceptional Contours in non-Hermitian Hyperbolic Matter
• Geometric representations of brain networks can predict the surgery outcome in temporal lobe epilepsy
• Applications of information geometry to spiking neural network behavior
• ${\text{H}}^2\text{TNE}$: Temporal Heterogeneous Information Network Embedding in Hyperbolic Spaces
• Structure and Dynamic of Global Population Migration Network
• Random walk with hyperbolic probabilities
• Lorentzian Graph Convolutional Networks
• Gromov hyperbolicity of minor graphs
• High Performance Algorithms for Quantum Gravity and Cosmology
• Large algebraic connectivity fluctuations in spatial network ensembles imply a predictive advantage from node location information
• Characterization and space embedding of directed graphs and social networks through magnetic Laplacians
• HSR: Hyperbolic Social Recommender
• On the distances within cliques in a soft random geometric graph
• Wireless Node Cooperation with Resource Availability Constraints
• SPARK: Adaptive Low-Rank Knowledge Graph Modeling in Hybrid Geometric Spaces for Recommendation
• Sharpest possible clustering bounds using robust random graph analysis
• HEAT: Hyperbolic Embedding of Attributed Networks
• Nearest-neighbour directed random hyperbolic graphs
• Generalized chordality, vertex separators and hyperbolicity on graphs
• Dynamics of cold random hyperbolic graphs with link persistence
• Chordality properties and hyperbolicity on graphs
• A Game Theoretic Model for the Formation of Navigable Small-World Networks --- the Tradeoff between Distance and Reciprocity
• Navigating Higher Dimensional Spaces using Hyperbolic Geometry
• Symmetry-driven embedding of networks in hyperbolic space
• Deductive Way of Reasoning about the Internet AS Level Topology
• Localized geometry detection in scale-free random graphs
• Flexible model of network embedding
• Mapping bipartite networks into multidimensional hyperbolic spaces
• Volume entropy and information flow in a brain graph
• Hyperbolic embedding of multilayer networks
• Hyperbolic recurrent neural network as the first type of non-Euclidean neural quantum state ansatz
• Computing distances on Riemann surfaces
• $({\omega }_1,{\omega }_2)$-temporal random hyperbolic graphs
• Latent geometry emerging from network-driven processes
• Spatiotemporal Activity-Driven Networks
• Robustness and size-dependence of circadian rhythms in multiscale suprachiasmatic-nucleus networks
• Non-Euclidean Self-Organizing Maps
• Maximal Cliques in Scale-Free Random Graphs
• Generalization Error Bound for Hyperbolic Ordinal Embedding
• THG: Transformer with Hyperbolic Geometry
• Multi-modal Entity Alignment in Hyperbolic Space
• Arbitrary degree distribution and high clustering in networks of locally interacting agents
• Algorithm Engineering for Cut Problems
• Random Rank-Based, Hierarchical or Trivial: Which Dynamic Graph Algorithm Performs Best in Practice?
• Negatively Curved Graphs
• Hidden multiscale organization and robustness of real multiplex networks
• Hyperbolic Multiplex Network Embedding with Maps of Random Walk
• Stable Geodesic Update on Hyperbolic Space and its Application to Poincare Embeddings
• Several extremal problems on graphs involving the circumference, girth, and hyperbolicity constant
• On the hyperbolicity constant of circular-arc graphs
• Solving a conjecture about tessellation graphs of ${\mathbb{R}}^2$
• Hyperbolicity in the corona and join of graphs
• One-Shot Learning for Language Modelling
• Metric Learning for Dynamic Text Classification
• On the largest component of subcritical random hyperbolic graphs
• Cover and Hitting Times of Hyperbolic Random Graphs
• Generating realistic scaled complex networks
• HyperText: Endowing FastText with Hyperbolic Geometry
• Modularity of Erdős-Rényi random graphs
• Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry
• Curvature of an Arbitrary Surface for Discrete Gravity and for $d=2$ Pure Simplicial Complexes
• Siamese networks for Poincaré embeddings and the reconstruction of evolutionary trees