Hyperbolic Geometry of Complex Networks
By Dmitri V. Krioukov, Fragkiskos Papadopoulos, M. Kitsak, Amin Vahdat, Marián Boguñá. 2010
1,192 citations recorded by the source corpus.
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 noninteracting 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.
Subfields: Computational Theory and Mathematics, Mathematical Physics, Statistical and Nonlinear Physics, Graph Learning, Network Science & Complex Systems
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
- Octavian-Eugen Ganea
- Gary Bécigneul
- A. Tifrea
- Thomas Hofmann
- Christopher R'e
- Rex Ying
- Christopher De Sa
- Jure Leskovec
In Mathematical Physics
- Thomas Hofmann
- Edwin Robert Hancock
- Jure Leskovec
- Nando de Freitas
- Ivan V. Oseledets
- Christopher De Sa
- Caglar Gulcehre
- Razvan Pascanu
In Statistical and Nonlinear Physics
In Graph Learning
In Network Science & Complex Systems
Citations in the corpus
- Learning Continuous Hierarchies in the Lorentz Model of Hyperbolic Geometry (2018, background): “Krioukov et al. (2010) showed that typical properties of complex networks (e.g., heterogeneous degree distributions and strong clustering) can be explained by assuming an underlying hyperbolic geometry and, moreover, developed a framework to model networks based on these properties.”
- Hyperbolic Image Embeddings (2019, background): “It is known that hyperbolic space cannot be isomet-rically embedded into Euclidean space [13, 18], but there Point z represents the M¨obius sum of points x and y .”
- Random Graphs and Complex Networks (2016, background): “Here we consider the hyperbolic random graph where nodes are in a disk of radius R, and connected if their hyperbolic distance is at most R Krioukov et al. (2010). These graphs are very different from general inhomogeneous random graphs, because their geometry creates more clustered random graphs.”
- Hyperbolic Attention Networks (2018, background): “Complex networks [20], which connect distinguishable heterogeneous sets of elements represented as nodes, provide us with an intuitive way of understanding these structures.”
- Growing Homophilic Networks Are Natural Navigable Small Worlds (2015, neutral): “It was recently suggested that the navigation properties can rise due to various optimization schemes, such as optimization of network ’ s entropy[6], optimization of network transport[7 – 12], game theory models[13, 14] or due to internal hyperbolicity of a hidden metric space[15].”
- Hyperbolic Graph Neural Networks (2019, background): “Typical properties such as heterogeneous degree distributions and strong clustering can often be explained by assuming an underlying hierarchy which is well captured in hyperbolic space [28, 35].”
- Hyperbolic Graph Convolutional Neural Networks (2019, methodology): “For link prediction, we use the Fermi-Dirac decoder [23, 29], a generalization of sigmoid, to compute probability scores for edges: where is the hyperbolic distance and r and t are hyper-parameters.”
- Spherical and Hyperbolic Embeddings of Data (2014, methodology): “However, hierarchical data such as trees and complex networks may naturally be embedded in hyperbolic spaces [8] when the number of elements at each level of the hierarchy increases exponentially.”
- A Survey on Network Embedding (2017, background): “For example, recently some studies (Krioukov et al. 2010) assume that the underlying structure of a network is in the hyperbolic space.”
- Spatial Networks (2010, methodology): “These various results (summarized in [201]) show that many real-world networks are navigable which means that they support efficient communication without a global knowledge of the network.”
- Named data networking (2014, positive): “For example, NLSR now supports a type of hyperbolic routing [16, 6] by disseminating hyperbolic coordinates in link state advertisements.”
- Poincaré GloVe: Hyperbolic Word Embeddings (2018, background): “It is known that real-world graphs are mainly complex networks (e.g. scale-free exhibiting power-law node degree distributions) which in turn are better embedded in a tree-like space, i.e. hyperbolic (Krioukov et al., 2010).”