Structure and Traffic on Complex Networks

Author

Duch i Gavaldà, Jordi

Director

Arenas, Àlex

Date of defense

2008-04-18

ISBN

978-84-694-3630-1

Legal Deposit

B.21928-2011

Pages

187 p.



Department/Institute

Universitat de Barcelona. Departament de Física Fonamental

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.

Subjects

530.1 - General principles of physics

Documents

JDG_THESIS.pdf

4.796Mb

 

Rights

ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.

This item appears in the following Collection(s)