Structure and Traffic on Complex Networks

Abstract

In a time when large amounts of data about social, economical, technological, and biological systems are produced in a daily bases, complex networks have become a powerful tool to represent the structure of complex systems. The advances in complex networks research have been geared towards the study of two main questions: what can we understand from a complex system by looking at its structure, and more importantly, what is the interplay between the topological and dynamical properties of complex systems. The aim of this dissertation is to review and introduce new tools and methods to measure topological and dynamical properties of complex networks. In particular, it covers two specific problems related with the two previously presented questions: the study of the community structure of complex networks, and the analysis of the dynamical properties of a communication process. The first part of the thesis is focused on the study of the community structure of complex networks, that is, how and why the nodes of the network tend to form groups in which they are highly interconnected. The understanding of this problem is key to characterize the internal organization of complex systems, obtaining better insights about the dynamical behavior of their components. In this part we present an exhaustive review of the community structure identification problem, explaining the limitations of the current existing methods, and we introduce a new method to extract the community structure based on the extremal optimization algorithm. We also present several improvements that increase the efficiency and accuracy of current community identification methods and an exhaustive benchmark of the results obtained when applying this new method to the standard network metrics. These results show that the extremal optimization method and its modifications are one of the fastest and most accurate options to identify the community structure of a network. The second part of the thesis is devoted to the study of some dynamical properties of communication processes over complex networks. Using a simple traffic model we analyze the changes observed on some properties when we introduce congestion in the network: the scaling of the fluctuations and the dynamical robustness. First, we present the scaling of the fluctuations in order to provide a large-scale dynamical characterization of the traffic flow. The idea is that there are a large number of real complex systems that show a scaling relation between the average flux and the variability of this flux. The understanding of the scaling relation presented in the dissertation will help us design better traffic models. And second, we study the dynamical robustness of the traffic, defined as the capability of maintaining the efficiency of the communication when we remove a fraction of nodes of the network. We show that there is a dynamical percolation threshold that splits the network due to the congestion before the topological percolation threshold.