Mapping complexity through network geometry: from structure to dynamics of real-world networks

Abstract

[eng] Complex systems, which involve a massive ammount of components interacting in nontrivial ways and exhibiting properties such as emergence, feedback-loops and self-organization, permeate our world to an unthinkable extent. In order to understand such pervasive systems in nature, science, technology and business one has to abandon unsuitable reductionist approches and develop a deep understanding of the networks of interactions that sustain them. In this respect, this thesis exploits a key discovery provided by network science: the architecture of networks arising in completely different domains are in fact remarkably similar to each other, and thus can be modeled using the same set of mathematical tools.

This thesis presents a geometric approach to the study of connectivity patterns and dynamical phenomena in real-world complex networks. The main hypothesis of network geometry states that the architecture of real complex networks has a geometric nature. This has been confirmed during the last decade, with a great number of networks from different domains being successfully mapped into a (hidden) metric space with hyperbolic geometry. Maps have served throughout history as a precise and relevant source of information, at the center of political, economic, and geostrategic decisions. In this thesis, geometric maps of networks play a central role and constitute the underlying thread that weaves the various chapters together. In particular, the work presented in this thesis exploits the current explosion in computing power and the ability of geometric maps to abstract complex topologies in order to unravel fundamental principles underlying the organization and function of real networks.

This thesis starts by introducing complex systems and their mathematical description in terms of networks. In the Preliminary Methods section, we review the S1 and H2 models, which provide a geometric explanation of networks, and discuss the embedding methods used to produce geometric maps. The next four chapters contain the results of our investigations about the structure of and the dynamics on real complex networks. These are organized so that each chapter covers a different topic, while the focus shifts from structure to dynamics traversing through the combination of both.

First, we concentrate on structure and devote to the diagnosis of communities through the development of a specialized geometric configuration model, which provides an alternative to the S1 model for generating random versions of geometric networks. Second, we advance our knowledge on structure by providing a thorough analysis of the hierarchical organization of networks while uncovering mechanisms that favor cooperation in social dilemmas susceptible to stratified order. In chapter three, we further enmesh structure and function by coupling opinion dynamics on a network with its metric structure in order to unravel the multiscale anatomy of opinion formation processes in real systems. In chapter four we fully shift our attention to the dynamics of networks and explore the navigability of time-evolving graphs in hyperbolic space. Finally, we present our conclusions followed by a list of publications related to this thesis.

Along the several chapters of this thesis we discover and develop a range of applications of the S1 / H2 formalism which inform different important and still obscure structural and dynamical features of real networks. Taken together, our findings have important implications for the design and evaluation of efficient routing protocols, for the predictability of opinion formation dynamics, and even for the control and detection of hierarchical power structures. This thesis demonstrates that the future of the geometric approach to network science remains full of opportunities, and the many insights yet to uncover are only bounded by the imagination of those who venture to exploit the geometric paradigm.

[cat] Els sistemes complexos són aquells que involucren un nombre elevat de components que interaccionen de manera no trivial. Aquesta tesis comença introduïnt els sistemes complexos i la seva descripció matemàtica en termes de xarxes complexes. Concretament, s’introdueix el paradigma geomètric, que esdevé el punt de referència des del qual es tracten diversos punts importants de l’estructura i la dinàmica de les xarxes complexes reals. A la secció de mètodes es discuteixen els models geomètrics S(1) i H(2), que descriuen les xarxes en termes d’espais mètric subjacents. També s’expliquen les tècniques utilitzades per a crear mapes geomètrics en l’espai hiperbòlic que representen les xarxes reals. Els següents quatre capítols inclouen els resultats de les nostres investigacions. Cada capítol tracta un tema concret que lliga amb el següent de manera que el centre d’atenció passa de l’estructura a la dinàmica. Primerament ens centrem en el diagnòstic de l’estructura de comunitats en xarxes heterogènies. Ho fem mitjançant el desenvolupament d’un model especialitzat de configuració que permet generar rèpliques fidedignes de les xarxes complexes descomptant exclusivament les comunitats de manera geomètrica. Posteriorment, avancem en el coneixement de l’estructura de les xarxes analitzant la seva organització jeràrquica a través d’una nova mesura geomètrica de jerarquia. Aquesta mesura permet descobrir l’ordre jeràrquic de xarxes no direccionals. També revela un mecanisme de filtrat que permet descobrir els grafs que promouen la cooperació entre individus quan apliquen dinàmiques de dilemes socials a les xarxes. Al tercer capítol, estructura i dinàmica es barregen completament per donar lloc a un model de formació d’opinió multiescala que ens permet estudiar com les diferents granularitats a nivell social influencien el procés de consens en sistemes connexos. Finalment, el darrer capítol es focalitza en la dinàmica per complet i s’investiga la navegació efficient de xarxes temporals utilitzant l’espai hiperbòlic.