Comunidades y robustez en redes complejas reales y sintéticas

Abstract

El estudio de las redes complejas, sistemas cuya estructura está regida por una compleja red de interacciones, es un área activa de investigación multidisciplinaria. Este campo ha recibido un gran impulso en los últimos años debido a la disponibilidad de una cantidad masiva de datos y a la existencia de recursos computacionales que permiten llevar a cabo los análisis estadísticos requeridos. Redes complejas extensas pueden encontrarse en una gran cantidad de sistemas naturales y artificiales, tales como sistemas físicos, biológicos, sociales, infraestructuras tecnológicas, etc. El aporte de la física a esta temática viene de la mano de la mecánica estadística, cuyas herramientas han facilitado el estudio de la estructura, la dinámica y la evolución de las redes complejas, brindando un marco teórico adecuado para el estudio cualitativo y cuantitativo de estos sistemas. La caracterización estadística de la estructura de las redes complejas se aborda desde diversos enfoques. Entre ellos hay dos que se destacan por la información que aportan y por las implicancias prácticas que ofrecen. Por una parte, la caracterización de estructuras modulares o comunidades es importante para entender la funcionalidad de las redes. Por otra parte, el estudio de la resiliencia de las redes ante fallas o ataques dirigidos es de gran utilidad para comprender cómo pueden generarse redes con un funcionamiento robusto. Curiosamente, estos dos conceptos –la existencia de comunidades y robustez de las redes– están íntimamente relacionados, y su estudio presenta grandes desafíos, dada la complejidad de los cálculos y análisis necesarios para su abordaje. En esta tesis estudiamos la existencia de comunidades en redes de jugadores de ajedrez utilizando la base de datos de partidas más extensa disponible, en su momento, en el mundo. Realizamos una caracterización general de las mismas y observamos una fuerte correlación entre las comunidades y el nivel de juego de los jugadores. En lo que respecta a las fallas y/o ataques analizamos redes sintéticas, tales como grafos de Erdös-Rényi y redes planares de Delaunay. Caracterizamos la robustez de las mismas mediante el estudio de transiciones de percolación, utilizando las herramientas de análisis de los fenómenos críticos y extensas simulaciones numéricas. Observamos que las transiciones varían de manera cualitativa de acuerdo con el tipo de red y con la estrategia de ataque empleada. En particular, observamos que algunos ataques generan transiciones similares a las encontradas en procesos de percolación explosiva.

The study of complex networks, systems whose structure is governed by a complex interaction network, is an active multidisciplinary field of research in which physics has had a prevailing role. This field has received great impulse during the last years because of the availability of a massive amount of data and the existence of computational resources that allow to perform the required statistical analysis. Extensive complex networks can be found in a large variety of natural and artificial systems, such as physical, biological, and social systems, technological infrastructures, etc. Given the importance of these systems, investigations exploring the structure, dynamics and evolution of complex networks has raised the interest of the physics community, as tools coming from statistical mechanics, as well as from other fields of physics, are fundamental and have a direct application in the analysis and comprehension of such systems. The statistical characterization of the structure of complex networks is addressed from different approaches. Among them there are two that stand because of the information they give and because of the practical applications they allow. On one side, the characterization of modular structures or communities is important to understand the functionality of networks. On the other side, the study of the resiliency of networks against failures or targeted attacks gives relevant information on how to develop robust networks. Interestingly, these two concepts --the existence of communities and the robustness of networks-- are closely related, and their study presents big challenges, given the complexity of the calculations and analysis required to address them. In this thesis we studied the existence of communities in networks of chess players using the largest available database, at the moment, on the world. We performed a general characterization of the networks, observing a strong correlation between communities and player skill level. In terms of failures and targeted attacks, we studied synthetic random networks, such as Erdös-Rényi graphs and Delaunay triangulations. We characterized their robustness through the study of percolation transitions, using tools from critical phenomena and extensive numerical simulations. We observed that the transitions vary in a qualitative manner depending on the type of network and the attack strategy. In particular, we found that certain attacks generate transitions similar to those encountered in processes of explosive percolation.