Reconstruction, mobility, and synchronization in complex networks

Abstract

[eng] During the last decades, it has become clear that systems formed by many interacting parts show emergent dynamical properties which are inherently related to the topology of the underlying pattern of connections among the constituent parts.

Such systems, usually known as complex systems, are in general suitably described through their networks of contacts, that is, in terms of nodes (representing the system's components) and edges (standing for their interactions), which allows to catch their essential features in a simple and general representation.

In recent years, increasing interest on this approach, thanks also to a favorable technological progress, led to the accumulation of an increasing amount of data. This situation has allowed the arising of new questions and, therefore, the diversification of the scientific work. Among them, we can point out three general issues that have been receiving a lot of interest: (i) is the available information always reliable and complete? (ii) how does a complex interaction pattern affect the emergence of collective behavior in complex systems? And (iii) which is the role of mobility within the framework of complex networks?

This thesis has been developed along these three lines, which are strictly interrelated. We expand on three case-studies, each one of which deals with two the above mentioned macro-issues. We consider the issue of the incompleteness of the available information both in the case of natural (Chapter 2) and artificial (Chapter 3) networks. As a paradigmatic emergent behavior, we focus on the synchronization of coupled phase oscillators (Chapter 2 and Chapter 4), deeply investigating how different patterns of connections can affect the achievement of a globally coherent state. Finally, we include moving agents in two different frameworks, using them as explorers of unknown networks (Chapter 3) and considering them as interacting units able to establish connections with their neighbors (Chapter 4).

In Chapter 2, we study the problem of the reconstruction of an unknown interaction network, whose nodes are Kuramoto oscillators. Our aim is to extract topological features of the connectivity pattern from purely dynamical measures, based on the fact that in a heterogeneous network the global dynamics is not only affected by the distribution of the natural frequencies but also by the location of the different values. The gathered topological information ranges from local features, such as the single node connectivity, to the hierarchical structure of functional clusters, and even to the entire adjacency matrix.

In Chapter 4, instead, we present a model of integrate and fire oscillators that are moving agents, freely displacing on a plane. The phase of the oscillators evolves linearly in time and when it reaches a threshold value they fire at their neighbors. In this way, the interaction network is a dynamical object by itself since it is re-created at each time step by the motion of the units. Depending on the velocity of the motion, the average number of neighbors, the coupling strength and the size of the agents population, we identify different regimes. Moving agents are employed also in Chapter 3 where they play the role of explorers of unknown artificial networks, having the mission to recover information about their structures. We propose a model in which random walkers with previously assigned home nodes navigate through the network during a fixed amount of time. We consider that the exploration is successful if the walker gets the information gathered back home, otherwise, no data is retrieved. We show that there is an optimal solution to this problem in terms of the average information retrieved and the degree of the home nodes and design an adaptive strategy based on the behavior of the random walker.

[spa] Durante las últimas décadas, se ha empezado a poner de manifiesto que sistemas formados por muchos elementos en interacción pueden mostrar propiedades dinámicas emergentes relacionadas con la topología del patrón de conexiones entre las partes constituyentes. Estos sistemas, generalmente conocidos como sistemas complejos, en muchos casos pueden ser descritos a través de sus redes de contactos, es decir, en términos de nodos (que representan los componentes del sistema) y de enlaces (sus interacciones). De esta manera es posible capturar sus características esenciales en una representación simple y general.

En esta última década, el creciente interés en este enfoque, gracias también a un progreso tecnológico favorable, ha llevado a la acumulación de una cantidad ingente de datos. Eso, a su vez, ha permitido el surgimiento de nuevas preguntas y, por lo tanto, la diversificación de la actividad científica. Entre ellas, podemos destacar tres cuestiones generales que son objeto de mucho interés: (i) ¿la información disponible es siempre fiable y completa? (ii) ¿cómo un patrón de interacción complejo puede afectar el surgimiento de comportamientos colectivos? Y (iii) ¿cual es el papel de la movilidad en el marco de las redes complejas?

Esta tesis se ha desarrollado siguiendo estas tres líneas, que están íntimamente relacionadas entre sí. Hemos profundizado en tres casos de estudio, cada uno de los cuales se ocupa de dos de los macro-temas mencionados. Consideramos la cuestión del carácter incompleto de la información disponible tanto en el caso de redes naturales (Capítulo 2) como de redes artificiales (Capítulo 3). Nos centramos en la sincronización de los osciladores de fase acoplados (Capítulos 2 y 4) en cuanto comportamiento emergente paradigmático, investigando en profundidad cómo los diferentes patrones de conexión puedan afectar la consecución de un estado coherente a nivel global. Por último, analizamos el rol de la movilidad incluyendo agentes móviles en dos marcos diferentes. En un caso, los utilizamos como exploradores de redes desconocidas (Capítulo 3), mientras que en otro los consideramos como unidades que interaccionan y son capaces de establecer conexiones con sus vecinos (Capítulo 4).