• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Master's Dissertation
DOI
10.11606/D.76.2011.tde-19042011-091118
Document
Author
Full name
André Luiz Barbieri
Institute/School/College
Knowledge Area
Date of Defense
Published
São Carlos, 2011
Supervisor
Committee
Rodrigues, Francisco Aparecido (President)
Almeida, Virgílio Augusto Fernandes
Liang, Zhao
Title in Portuguese
Análise de robustez em redes complexas
Keywords in Portuguese
Acessibilidade
Proteínas
Redes complexas
Robustez
Rodovias
Abstract in Portuguese
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.
Title in English
Analysis of Robustness in Complex Networks
Keywords in English
Accessibility
Complex networks
Proteins
Roads
Robustness
Abstract in English
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.
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Publishing Date
2011-04-20
 
WARNING: The material described below relates to works resulting from this thesis or dissertation. The contents of these works are the author's responsibility.
  • BARBIERI, André Luiz. Resilience of protein–protein interaction networks as determined by their large-scale topological features [doi:10.1039/C0MB00256A]. Molecular BioSystems [online], 2011, vol. 7, n. 4, p. 1263-1269.
All rights of the thesis/dissertation are from the authors
Centro de Informática de São Carlos
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2020. All rights reserved.