A geometric approach to the structure of complex networks

Abstract

Complex networks are mathematical representations of the interaction patterns of complex systems. During the last 20 years of Network Science, it has been recognized that networks from utterly different domains exhibit certain universal properties. In particular, real complex networks present heterogeneous, and usually scale-free, degree distributions, a large amount of triangles, or high clustering coefficient, a very short diameter, and a clear community structure. Among the vast set of models proposed to explain the structure of real networks, geometric models have proven to be particularly promising.

This thesis is developed in the framework of hidden metric spaces, in which the high level of clustering observed in real networks emerges from underlying geometric spaces encoding the similarity between nodes. Besides providing an intuitive explanation to the observed clustering coefficient, geometric models succeed at reproducing the structure of complex networks with high accuracy. Furthermore, they can be used to obtain embeddings of networks, that is, maps of real systems enabling their geometric analysis and efficient navigation.

This work introduces the main concepts in the hidden metric spaces approach and presents a thorough description of the main models and embedding procedures. We generalize these models to generate networks with soft communities, that is, with correlated positions of nodes in the underlying metric space. We also explore one of the models in higher similarity-space dimensions, and show that the maximum clustering coefficient attainable decreases with the dimension, which allows us to conclude that real-world networks must have low-dimensional similarity spaces as a consequence of their high clustering coefficient.

The thesis also includes a detailed geometric analysis of the international trade system. After reconstructing a yearly sequence of world trade networks covering 14 decades, we embed them into hyperbolic space to obtain a series of maps, which we named The World Trade Atlas 1870-2013. In these maps, the likelihood for two countries to be connected by a significant trade channel depends on the distance among them in the underlying space, which encodes the different factors influencing trade interactions. Our analysis of the networks and their maps reveals that the world is being shaped by three different forces acting simultaneously: globalization, localization and hierarchization.

The hidden metric spaces approach can be exploited beyond network metrics. We show that similarity space defines a notion of scale in real-world networks. We present a Geometric Renormalization Group transformation that unveils a previously unknown self-similarity of real networks. Remarkably, the phenomenon is explained by the congruency of real systems with our model. This renormalization transformation provides us with two immediate applications: a method to construct high-fidelity smaller-scale replicas of real networks and a multiscale navigation protocol in hyperbolic space that outperforms single-scale versions.

The geometric origin of real networks is not restricted to their binary structure, but it affects their weighted organization as well. We provide empirical evidence for this claim and propose a geometric model with the capability to reproduce the weighted features of real systems from many different domains. We also present a method to infer the level of coupling of real networks with the underlying metric space, which is generally found to be high in real systems.

Les xarxes complexes representen els patrons d’interacció dels sistemes complexos. S’ha observat repetidament que xarxes d’àmbits molt diferents comparteixen certes propietats, com l’heterogeneïtat del nombre de veïns o el clustering elevat (alta presència de triangles), entre d’altres. Tot i que s’han proposat molts models per explicar aquesta universalitat, els models geomètrics han demostrat ser particularment prometedors.

Aquesta tesi es desenvolupa en el context dels espais mètrics ocults, en el qual la natura del clustering s’explica geomètricament en termes de similitud entre nodes. Els models basats en aquesta assumpció no només poden reproduir l’estructura de les xarxes reals amb molta precisió, sinó que permeten obtenir mapes de xarxes reals.

En aquest treball, introduïm els conceptes bàsics dels espais mètrics ocults, els seus models principals i els mètodes d’obtenció de mapes. També generalitzem aquests models al règim amb correlacions geomètriques entre nodes, i explorem la qüestió de la dimensió de l’espai de similitud. La nostra anàlisi ens permet concloure que l’espai de similitud de les xarxes reals ha de tenir dimensionalitat baixa.

Incloem una anàlisi geomètrica detallada de l’evolució del sistema de comerç internacional basada en els mapes a l’espai hiperbòlic de les xarxes corresponents, al llarg de 14 dècades. En aquests mapes, la proximitat entre pa¨ısos representa la probabilitat d’interaccionar comercialment. L’anàlisi mostra que el món evoluciona d’acord amb tres forces que actuen simultàniament: la globalització, la localització i la jerarquització.

Els espais de similitud defineixen una noció d’escala en xarxes reals. Proposem una transformació de renormalització que revela una auto-similitud de sistemes reals anteriorment desconeguda. A més, proposem dues aplicacions d’aquesta transformació: un mètode per a obtenir versions reduïdes de xarxes reals i un mètode multiescalar per a navegar-les.

Finalment, mostrem que les estructures pesades dels sistemes reals també tenen un origen geomètric i proposem un model capaç de reproduir-les amb precisió. Desenvolupem un mètode per a inferir el nivell d’acoblament de les xarxes reals amb els espais mètrics subjacents i trobem que aquest és generalment elevat.