Network Geometry
M. Ángeles Serrano and Marián Boguñá
Geometry appears as the most plausible explanation of the complex architecture we observe in real networks. Scale-free degree distributions, clustering, small-world property, communities, reciprocity and many more topological properties can be explained by the existence of a metric space controlling the network interactions.
Relevant references
The geometric nature of weights in real complex networks
Antoine Allard, M. Ángeles Serrano, Guillermo García-Pérez and Marián Boguñá
Nature Communications
(2017)
abstract
The topology of many real complex networks has been conjectured to be embedded in hidden metric spaces, where distances between nodes encode their likelihood of being connected. Besides of providing a natural geometrical interpretation of their complex topologies, this hypothesis yields the recipe for sustainable Internet’s routing protocols, sheds light on the hierarchical organization of biochemical pathways in cells, and allows for a rich characterization of the evolution of international trade. Here we present empirical evidence that this geometric interpretation also applies to the weighted organization of real complex networks. We introduce a very general and versatile model and use it to quantify the level of coupling between their topology, their weights and an underlying metric space. Our model accurately reproduces both their topology and their weights, and our results suggest that the formation of connections and the assignment of their magnitude are ruled by different processes.
Hidden geometric correlations in real multiplex networks
Kaj-Kolja Kleineberg, Marián Boguñá, M. Ángeles Serrano & Fragkiskos Papadopoulos
Nature Physics
(2016)
abstract
Real networks often form interacting parts of larger and more complex systems. Examples can be found in different domains, ranging from the Internet to structural and functional brain networks. Here, we show that these multiplex systems are not random combinations of single network layers. Instead, they are organized in specific ways dictated by hidden geometric correlations between the layers. We find that these correlations are significant in different real multiplexes, and form a key framework for answering many important questions. Specifically, we show that these geometric correlations facilitate the definition and detection of multidimensional communities, which are sets of nodes that are simultaneously similar in multiple layers. They also enable accurate trans-layer link prediction, meaning that connections in one layer can be predicted by observing the hidden geometric space of another layer. And they allow efficient targeted navigation in the multilayer system using only local knowledge, outperforming navigation in the single layers only if the geometric correlations are sufficiently strong.
Emergence of Soft Communities from Geometric Preferential Attachment
Konstantin Zuev, Marian Boguña, Ginestra Bianconi, Dmitri Krioukov,
Scientific Reports
(2015)
abstract
All real networks are different, but many have some structural properties in common. There seems to be no consensus on what the most common properties are, but scale-free degree distributions, strong clustering, and community structure are frequently mentioned without question. Surprisingly, there exists no simple generative mechanism explaining all the three properties at once in growing networks. Here we show how latent network geometry coupled with preferential attachment of nodes to this geometry fills this gap. We call this mechanism geometric preferential attachment (GPA), and validate it against the Internet. GPA gives rise to soft communities that provide a different perspective on the community structure in networks. The connections between GPA and cosmological models, including inflation, are also discussed.
Percolation in Self-Similar Networks
M. Angeles Serrano, Dmitri Krioukov, Marian Boguña,
PHYSICAL REVIEW LETTERS
(2011)
abstract
We provide a simple proof that graphs in a general class of self-similar networks have zero percolation threshold. The considered self-similar networks include random scale-free graphs with given expected node degrees and zero clustering, scale-free graphs with finite clustering and metric structure, growing scale-free networks, and many real networks. The proof and the derivation of the giant component size do not require the assumption that networks are treelike. Our results rely only on the observation that self-similar networks possess a hierarchy of nested subgraphs whose average degree grows with their depth in the hierarchy. We conjecture that this property is pivotal for percolation in networks.
Hyperbolic geometry of complex networks
Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, Marian Boguña,
PHYSICAL REVIEW E
(2010)
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 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.
Greedy Forwarding in Dynamic Scale-Free Networks Embedded in Hyperbolic Metric Spaces
Fragkiskos Papadopoulos, Dmitri Krioukov, Marián Boguñá, and Amin Vahdat
IEEE INFOCOM, San Diego, CA, March 2010
(2010)
abstract
We show that complex (scale-free) network topolo- gies naturally emerge from hyperbolic metric spaces. Hyperbolic geometry facilitates maximally efficient greedyforwarding in these networks. Greedy forwarding is topology-oblivious. Nevertheless,greedy packets find their destinations with 100% probability following almost optimal shortest paths. This remarkable efficiency sustains even in highly dynamic networks. Our findings suggest that forwarding information through complex networks, such as the Internet, is possible without the overhead of existing routing protocols, and may also find practical applications in overlay networks for tasks such as application-level routing, information sharing, and data distribution.
Curvature and temperature of complex networks
Krioukov, Fragkiskos Papadopoulos, Amin Vahdat, Marian Boguña,
PHYSICAL REVIEW E
(2009)
abstract
We show that heterogeneous degree distributions in observed scale-free topologies of complex networks can emerge as a consequence of the exponential expansion of hidden hyperbolic space. Fermi-Dirac statistics provides a physical interpretation of hyperbolic distances as energies of links. The hidden space curvature affects the heterogeneity of the degree distribution, while clustering is a function of temperature. We embed the internet into the hyperbolic plane and find a remarkable congruency between the embedding and our hyperbolic model. Besides proving our model realistic, this embedding may be used for routing with only local information, which holds significant promise for improving the performance of internet routing.
Greedy Forwarding in Scale-Free Networks Embedded in Hyperbolic Metric Spaces
Dmitri Krioukov, Fragkiskos Papadopoulos, Marián Boguñá, and Amin Vahdat
ACM SIGMETRICS Performance Evaluation Review
(2009)
abstract
Routing information is the most basic and, perhaps, the most complicated function that networks perform. Conventional wisdom states that to find paths to destinations through the complex network maze, nodes must communicate and exchange information about the status of their connections to other nodes. This communication overhead is considered one of the most serious scaling limitations of our primary communication technologies today, including the Internet and emerging wireless and sensor networks.
Self-similarity of complex networks and hidden metric spaces
M. Angeles Serrano, Dmitri Krioukov, Marian Boguña,
PHYSICAL REVIEW LETTERS
(2008)
abstract
We demonstrate that the self-similarity of some scale-free networks with respect to a simple degree-thresholding renormalization scheme finds a natural interpretation in the assumption that network nodes exist in hidden metric spaces. Clustering, i.e., cycles of length three, plays a crucial role in this framework as a topological reflection of the triangle inequality in the hidden geometry. We prove that a class of hidden variable models with underlying metric spaces are able to accurately reproduce the self-similarity properties that we measured in the real networks. Our findings indicate that hidden geometries underlying these real networks are a plausible explanation for their observed topologies and, in particular, for their self-similarity with respect to the degree-based renormalization.
Geometric correlations in real multiplex networks
Kaj-Kolja Kleineberg, Marian Boguna, M. Angeles Serrano, Fragkiskos Papadopoulos
arXiv:1601.04071
abstract
Real networks often form interacting parts of larger and more complex systems. Examples can be found in different domains, ranging from the Internet to structural and functional brain networks. Here, we show that these multiplex systems are not random combinations of single network layers. Instead, they are organized in specific ways dictated by hidden geometric correlations between the individual layers. We find that these correlations are strong in different real multiplexes, and form a key framework for answering many important questions. Specifically, we show that these geometric correlations facilitate: (i) the definition and detection of multidimensional communities, which are sets of nodes that are simultaneously similar in multiple layers; (ii) accurate trans-layer link prediction, where connections in one layer can be predicted by observing the hidden geometric space of another layer; and (iii) efficient targeted navigation in the multilayer system using only local knowledge, which outperforms navigation in the single layers only if the geometric correlations are sufficiently strong. Our findings uncover fundamental organizing principles behind real multiplexes and can have important applications in diverse domains.
