Made available in DSpace on 2014-06-12T16:26:48Z (GMT). No. of bitstreams: 2 arquivo2049_1.pdf: 8995821 bytes, checksum: d2a566dca4e7959219d7c624eee20c8a (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2009 / Esta pesquisa teve por objetivo desenvolver um sistema aplicativo, com base em Sistema de Informações Geográficas (SIG) para analisar as redes de distribuição de água e dar subsídios ao planejamento das ações para redução das perdas de água. Para isso foi criado um modelo conceitual de um Sistema de Abastecimento de Água, empregando-se a Modelagem de Dados Espaciais Orientada a Objetos, em linguagem UML. O modelo físico correspondente foi implementado e testado na forma de um projeto piloto, utilizando-se o programa ArcGIS da ESRI. A área de estudo correspondeu a um distrito operacional e um setor comercial da Companhia Pernambucana de Saneamento (COMPESA), na cidade do Recife. O resultado do teste mostrou que o objetivo da pesquisa foi atingido e que o emprego de uma estrutura topológica de redes foi fundamental para o sucesso do sistema aplicativo

Muitos sistemas complexos naturais ou construídos pelos seres humanos podem ser representados por redes complexas, uma teoria que une o estudo de grafos com a mecânica estatística. Esse tipo de representação, porém, pode ser comprometido pela maneira como os dados são obtidos. Em geral, os dados utilizados para representar tais sistemas nem sempre são precisos ou completos e correspondem a apenas amostras pequenas de redes maiores, como é o caso da teia mundial (WWW). Dessa forma, mesmo que as amostras sejam grandes, as suas propriedades são diretamente afetadas pela maneira como elas são obtidas e podem não corresponder com as de suas respectivas redes originais. Por exemplo, a amostragem mais utilizada para captura de roteadores da Internet, se empregada em redes aleatórias, tende a obter redes sem escala como resultado. Em contrapartida, amostras de redes sem escala não têm garantia de preservar essa estrutura. Por causa desses e outros problemas que possam ocorrer na amostragem das redes, é muito importante avaliar a variação das propriedades das redes a ruídos (para saber quais variam menos, sendo, portanto, mais adequadas para caracterizar redes com problemas de amostragem) e os efeitos da amostragem na caracterização, classificação e análise de redes complexas (pois redes amostradas podem não corresponder ao sistemas dos quais foram obtidas, tornando os resultados incorretos). Neste trabalho, foi investigada a influência de três tipos de perturbação (ruído): adição, remoção e troca aleatória de conexões nas propriedades de redes complexas, e as mais apropriadas para caracterizar redes amostradas foram identificadas. Além disso, foram definidas duas novas estruturas em redes complexas: árvores de borda e cadeias de vértices. A ocorrência dessas estruturas em redes mal amostradas tende a ser alta, indicando que existe uma relação com redes parcialmente amostradas. Para verificar tal hipótese, foi investigada a presença de cadeias de vértices em redes gradativamente amostradas por caminhadas aleatórias. / Several natural or human made complex systems can be represented by complex networks a theory which integrates the study of graphs with statistical mechanics. This kind of representation, however, can be biased by the way in which the data is obtained. In general, the data used to represent such systems is not always accurate, as in the case of theWorldWideWeb (WWW). Therefore, even if the sampled networks are large, their properties are directly affected by the way in which they were obtained and may not correspond to those of their respective original networks. For instance, the most used sampling methodology for capturing routers of the Internet, if performed on random networks, tends to obtain scale-free networks as results. On the other hand, sampled scale-free networks are not guaranteed to have this property. Because of these and other problems which may occur during the network sampling, it is very important to evaluate the variation of the network properties with respect to noise (in order to know which of them have less variation, being therefore more suitable for the characterization of networks with sampling problems) and the effect of sampling in the characterization, classification, and analysis of complex networks. In this work, we investigated the effect of three types of perturbations (noise), namely, edge addition, removal, and rewiring on the respectively estimated complex network properties, and the most suitable properties to characterize sampled networks were identified. Furthermore, two novel structures in complex networks were defined, namely, border trees and chains of vertices, which are possibly related to sampling. The occurrence of these structures in poorly-sampled networks was found to be high, implying a relation with partially sampled networks. In order to investigate such a hypothesis, the presence of chains of vertices was investigated in networks which were gradually sampled by random walks.

Redes complexas são utilizadas para representar sistemas complexos, compostos de elementos que interagem uns com os outros. Uma das grandes vantagens de se empregar as redes é a possibilidade de se estudar a topologia presente nos mais diversos sistemas para obtermos informações sobre eles, entendê-los e compará-los. Devido à sua importância para a compreensão de processos intracelulares, desde início do desenvolvimento da área das redes complexas estudou-se a topologia da interação entre proteínas. Entretanto nos últimos anos com o desenvolvimento de novas técnicas de detecção o número de proteínas e interações reportadas cresceu de maneira muito acentuada; além disso, também existem alguns pontos sobre a sua topologia sobre os quais ainda não existe um consenso, como por exemplo qual a distribuição de graus desse tipo de rede. Neste trabalho estudamos as propriedades topológicas de redes de interação entre proteínas, utilizando as informações do banco de dados STRING, com ênfase no comportamento de suas medidas de centralidade e do espectro da matriz Laplaciana normalizada. Tanto a análise das medidas de centralidade e de suas correlações, quanto do espectro da matriz Laplaciana mostram que existem padrões topológicos que são conservados entre as redes dos organismos e que os mesmos também podem ser empregados para sua caracterização. Nossos resultados também mostram que as funções biológicas desempenhadas pelas proteínas podem ser identificadas pelas medidas de centralidade. Especificamente para a centralidade de autovetor, nossas análises indicam que ela está localizada nos maiores K-cores das redes consideradas. Os resultados aqui obtidos ressaltam que muitas informações relevantes podem ser extraídas da topologia das interações entre proteínas, além de indicarem a existência de possíveis estruturas conservadas; entretanto devido a incompletude dessas redes mais estudos precisam ser conduzidos para a avaliação de possíveis mudanças nos resultados aqui apresentados. / Complex networks can be used to model complex systems, composed of main elements that interact with each other. The advantage of using this approach is the possibility to study the topology of a wide range of systems so that we can get more information, understand and compare them. Due to its importance on the understanding of the intracellular biological processes, since the early beginning of the development of the complex networks field protein-protein interaction topologies have been studied. However, new techniques for the detection of proteins and their interactions have been developed recently, which has significantly increased the availability and reliability of the corresponding data over the last few years; moreover, there still are some debate about the topology of protein-protein interaction networks such as the degree distribution of this type of network. Here we will study the topological properties of protein-protein interaction networks created using the information of the STRING database focusing on centrality measures of their nodes, the correlation between them, and the normalized Laplacian matrix spectrum. Our results show the existence of topological patterns conserved between the protein interaction networks of different organisms and that both the correlation of the centrality pairs and the spectrum of the Laplacian matrix can be used for network characterization. Another study indicates that the set of centrality measures of a protein can be used to identify clusters with well defined biological functions. A more detailed look at the eigenvector centrality behavior reveals that this measure is localized on the proteins of the highest k-cores for all networks. These results highlight the importance of the topology on the study of protein-protein interactions and that more studies can lead to a better a more complete understanding of such systems.

Muitos sistemas complexos naturais ou construídos pelos seres humanos podem ser representados por redes complexas, uma teoria que une o estudo de grafos com a mecânica estatística. Esse tipo de representação, porém, pode ser comprometido pela maneira como os dados são obtidos. Em geral, os dados utilizados para representar tais sistemas nem sempre são precisos ou completos e correspondem a apenas amostras pequenas de redes maiores, como é o caso da teia mundial (WWW). Dessa forma, mesmo que as amostras sejam grandes, as suas propriedades são diretamente afetadas pela maneira como elas são obtidas e podem não corresponder com as de suas respectivas redes originais. Por exemplo, a amostragem mais utilizada para captura de roteadores da Internet, se empregada em redes aleatórias, tende a obter redes sem escala como resultado. Em contrapartida, amostras de redes sem escala não têm garantia de preservar essa estrutura. Por causa desses e outros problemas que possam ocorrer na amostragem das redes, é muito importante avaliar a variação das propriedades das redes a ruídos (para saber quais variam menos, sendo, portanto, mais adequadas para caracterizar redes com problemas de amostragem) e os efeitos da amostragem na caracterização, classificação e análise de redes complexas (pois redes amostradas podem não corresponder ao sistemas dos quais foram obtidas, tornando os resultados incorretos). Neste trabalho, foi investigada a influência de três tipos de perturbação (ruído): adição, remoção e troca aleatória de conexões nas propriedades de redes complexas, e as mais apropriadas para caracterizar redes amostradas foram identificadas. Além disso, foram definidas duas novas estruturas em redes complexas: árvores de borda e cadeias de vértices. A ocorrência dessas estruturas em redes mal amostradas tende a ser alta, indicando que existe uma relação com redes parcialmente amostradas. Para verificar tal hipótese, foi investigada a presença de cadeias de vértices em redes gradativamente amostradas por caminhadas aleatórias. / Several natural or human made complex systems can be represented by complex networks a theory which integrates the study of graphs with statistical mechanics. This kind of representation, however, can be biased by the way in which the data is obtained. In general, the data used to represent such systems is not always accurate, as in the case of theWorldWideWeb (WWW). Therefore, even if the sampled networks are large, their properties are directly affected by the way in which they were obtained and may not correspond to those of their respective original networks. For instance, the most used sampling methodology for capturing routers of the Internet, if performed on random networks, tends to obtain scale-free networks as results. On the other hand, sampled scale-free networks are not guaranteed to have this property. Because of these and other problems which may occur during the network sampling, it is very important to evaluate the variation of the network properties with respect to noise (in order to know which of them have less variation, being therefore more suitable for the characterization of networks with sampling problems) and the effect of sampling in the characterization, classification, and analysis of complex networks. In this work, we investigated the effect of three types of perturbations (noise), namely, edge addition, removal, and rewiring on the respectively estimated complex network properties, and the most suitable properties to characterize sampled networks were identified. Furthermore, two novel structures in complex networks were defined, namely, border trees and chains of vertices, which are possibly related to sampling. The occurrence of these structures in poorly-sampled networks was found to be high, implying a relation with partially sampled networks. In order to investigate such a hypothesis, the presence of chains of vertices was investigated in networks which were gradually sampled by random walks.