A teoria das redes complexas é uma área relativamente nova da Ciência, inspirada por dados empíricos tais como os obtidos de interações biológicas e sociais. Esta área apresenta uma natureza altamente interdisciplinar, de modo que tem unido cientistas de diferentes áreas, tais como matemática, física, biologia, ciência computação, sociologia, epidemiologia e muitas outras. Um dos problemas fundamentais nessa área é entender como a organização de redes complexas influencia em processos dinâmicos, como sincronização, propagação de epidemias e falhas e ataques. Nessa dissertação, é apresentada uma análise da relação entre estrutura e robustez de redes complexas através da remoção de vértices. Para a aplicação deste estudo, foram adquiridas bases de dados de interações de proteínas de quatro espécies, Saccharomyces cerevisiae, Caenorhabditis elegans, Drosophila melanogaster e Homo sapiens, como também mapas das malhas de rodovias de sete países, Brasil, Portugal, Polônia, Romênia, Austrália, Índia e África do Sul. Foi estudada a robustez dessas redes através de simulação de falhas e ataques, segundo uma dinâmica de remoção de vértices. Nesse caso, a variação na estrutura das redes devido a essa remoção foi quantificada pelas medidas do tamanho da maior componente conectado, do diâmetro e da média dos comprimentos dos menores caminhos. Ademais, foram utilizadas duas medidas para quantificar a robustez, isto é, a entropia da distribuição das conexões e entropia dinâmica, baseada em cadeias de Markov. Tais medidas foram aplicadas nas redes reais onde se verificou que as espécies mais complexas, como o homem e a mosca, apresentam as redes mais robustas. Com relação aos países, Romênia, Portugal e Brasil apresentam as malhas rodoviárias mais resistentes a perturbações. A correlação entre essas medidas de entropia e as medidas topológicas permitiu identificar que a média do grau dos vizinhos e o coeficiente da lei de potência da distribuição do número de conexões são as medidas que apresentam maior correlação com as medidas de entropia. Tal resultado sugere que a presença de conexões alternativas entre os vizinhos dos vértices removidos favorece a resiliência das redes, pois tendem a minimizar as perturbações causadas pelas remoções. No caso das malhas rodoviárias, foi proposta uma nova medida de acessibilidade e esta se mostrou altamente correlacionada com a entropia dinâmica. Nesse caso, verificou-se que as cidades localizadas no litoral e nas fronteiras dos países são as que menos contribuem para robustez das redes de rodovias. Desse modo, os resultados obtidos sugerem que o planejamento do sistema de transporte de um país deve priorizar o investimento em infra-estrutura rodoviária próximo das cidades com menor acessibilidade, de forma a torná-las mais acessíveis, visando melhorar o transporte de mercadorias e pessoas. Os métodos aqui propostos permitem identificar tais cidades. Ademais, na análise de redes de proteínas, os resultados obtidos podem auxiliar no desenvolvimento de novos modelos de redes, bem como entender os mecanismos evolutivos que priorizam a robustez dos organismos. / The study of complex networks is a relatively new area of science inspired by the empirical studies of real-world networks, such as social and biological networks. This are has a highly multidisciplinary nature, which has brought together researchers from many areas including mathematics, physics, biology, computer science, sociology, epidemiology, statistics and others. One of the main problems in this area is to know how the network organization is related to dynamic process, such as synchronization, epidemic spreading and topological perturbation due to deletion of nodes and edges. In this dissertation, it is presented a study of the relationship between the structure and resilience of complex networks. This investigation was applied to the protein-protein networks of four species, namely Saccharomyces cerevisiae, Caenorhabditis elegans, Drosophila melanogaster and Homo sapiens, as well as the road networks of seven countries, i.e. Brazil, Portugal, Romania, Australia, India, and South Africa. It was studied the resilience of such networks through simulations of random fails and attacks by node deletion. The topological changes due to this simulation were quantified by measures, including the size of the largest component, the diameter and the average shortest path length. In addition, the network robustness was quantified by the entropy of the degree distribution and the dynamic entropy, related to Markov chains. This analysis in real-world networks revealed that more complex species, such as the H. sapiens and D. melanogaster are the most resilient. In addition, Romania, Brazil and Portugal have the most robust road maps. The correlation analysis between topological and dynamic measures revealed that the average neighborhood degree and the coefficient of scaling in the power law of the degree distribution quantify the proprieties that most contribute for the resilience in protein networks. Moreover, with respect to the road networks, it was introduced a new accessibility measure, which revealed to be correlated to the dynamic entropy. In fact, cities localized in the border of networks are the ones with the smallest contribution for the network resilience. Therefore, the obtained results suggest that the traffic planning should mainly connect cities near the frontiers of countries, in order to improve the resilience and accessibility. In addition, the obtained results with respect to protein networks allow improving network modeling and understanding the biological processes that reinforce the resilience of organisms.
| Identifer | oai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-19042011-091118 |
| Date | 14 February 2011 |
| Creators | Barbieri, André Luiz |
| Contributors | Rodrigues, Francisco Aparecido |
| Publisher | Biblioteca Digitais de Teses e Dissertações da USP |
| Source Sets | Universidade de São Paulo |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | Dissertação de Mestrado |
| Format | application/pdf |
| Rights | Liberar o conteúdo para acesso público. |
Page generated in 0.0032 seconds