Study of dynamical properties of complex networks

Abstract

Na última década houve grandes desenvolvimentos na área de teoria de grafos e suas aplicações interdisciplinares. Teoria de grafos (ou redes) é um campo de matemática discreta, que, por abstracção dos detalhes de um problema exceptuando a ligação entre os seus elementos, é capaz de uma descrição das suas características estruturais que de outra maneira não seria possível. Muitos sistemas na natureza, e em particular na sociedade, são bem representados por, ou evoluem tendo como base, redes complexas. Neste trabalho apresentamos alguns avanços para a compreensão das características estruturais genéricas destas redes e sistemas. A tese divide-se em duas partes principais: Na primeira parte faz-se um estudo da estrutura de redes, começando com uma breve introdução histórica do desenvolvimento da teoria de redes e de conceitos básicos, continuando com um conjunto de exemplos de redes previamente estudadas bem como modelos (Capítulo 1). Seguidamente, apresentamos um estudo teórico de propriedades estruturais como a distância entre vértices e a presença de subgrafos em redes (Capítulo 2). O último capítulo desta primeira parte é dedicado a um estudo detalhado de propriedades estruturais da rede real de colaborações científicas promovida pelo V Programa Quadro da União Europeia, FP5 (Capítulo 3). Na segunda parte, dividida em três capítulos, processos dinâmicos tendo como base duas redes são investigados: primeiro, a frequência com que os números ocorrem na World-Wide Web (Capítulo 4); segundo, a estatística temporal de actividades humanas, e seus modelos baseados em teoria de filas de espera, que será aqui introduzida (Capítulo 5); e, terceiro, um modelo teórico servindo como base para o estudo de interacções em redes sociais (Capítulo 6). No Capítulo 7 apresentam-se conclusões gerais, possível trabalho futuro e a lista de publicações resultante do trabalho realizado.

In the last decade there have been great developments in graph theory, namely in its interdisciplinary applications. Graph (or network) theory is a field of discrete mathematics, which, by abstracting away the details of a problem except the connectivity between its elements, is capable of describing important structural features that would be impossible with all the details retained. Many systems in nature, and in particular in society, are either well represented by, or evolve on the framework of, so called complex networks. Here we present some advances in understanding the generic structural characteristics of these networks and systems. The thesis is divided in two main parts: In the first part, we present a study of networks' structure, beginning with a brief historical introduction and of basic concepts of network research, continuing with a set of well studied network examples and models (Chapter 1). Next, we present a theoretical investigation of structural properties such as the intervertex distance and the presence of subgraphs in networks (Chapter 2). The last chapter of this first part is devoted to a detailed study of structural properties of the real-world network of scientific collaborations promoted by the European Union's Fifth Framework Programme, FP5 (Chapter 3). In the second part, divided in three chapters, dynamical processes based on two networks are investigated: First, the frequency with which numbers occur on the World-Wide Web (Chapter 4); second, the statistics of the timing of human activities, and their models based on queueing theory, which will be introduced here (Chapter 5); and third, a theoretical queueing model serving as base for the study of interactions on social networks (Chapter 6). In Chapter 7 we present general conclusions, outlook future work and the list of publications resulting from the work developed.