• 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
 
 
Thèse de Doctorat
DOI
10.11606/T.76.2008.tde-20052011-140835
Document
Auteur
Nom complet
Paulino Ribeiro Villas Boas
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Carlos, 2008
Directeur
Jury
Costa, Luciano da Fontoura (Président)
Andrade, Roberto Fernandes Silva
Martinez, Alexandre Souto
Mascarenhas, Nelson Delfino D'Ávila
Ruggiero, Carlos Antonio
Titre en portugais
Efeito da amostragem nas propriedades topológicas de redes complexas
Mots-clés en portugais
Amostragem
Estrutura topológica
Grafos
Incompleteza
Medidas
Redes complexas
Resumé en portugais
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.
Titre en anglais
Sampling effect on the topological properties of complex networks
Mots-clés en anglais
Complex networks
Graph
Incompletness
Measurements
Sampling
Topological structure
Resumé en anglais
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.
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
Date de Publication
2011-05-24
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
Centro de Informática de São Carlos
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2019. Tous droits réservés.