Autores

5534
Vicente de Melo Pinheiro
2538,753
5535
2538,753

Informações:

Publicações do PESC

Título
Modelagem e Caracterização de um Processo de Amostragem de Vértices em Redes
Linha de pesquisa
Redes de Computadores
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
5/12/2013
Resumo
O crescente interesse em estudar como as "coisas" se conectam vem sendo alavancado pela crescente abundância de grandes quantidades de dados relativos as mais diversas redes. Neste contexto, um importante aspecto é a forma como esses dados são coletados, pois na maioria das vezes as informações sobre vértices e arestas não estão disponíveis publicamente de forma centralizada ou mesmo de maneira organizada (por exemplo, Web, P2P, Facebook).
Com isso, se torna necessário descobrir essas redes através de um processo de amostragem onde este processo influencia fundamentalmente na forma que a rede é descoberta. Neste trabalho, nós estudamos o processo de amostragem de vértices que revelam informações locais de vértices escolhidos aleatoriamente na rede. Particularmente, desenvolvemos modelos analíticos para determinar o número de vértices e  arestas descobertos pelo processo de amostragem de acordo com o número de amostras e outras características da rede (por exemplo, grau médio). A avaliação dos modelos propostos comparada aos resultados obtidos através de simulação para diferentes modelos de redes indicam as condições sobre as quais nosso modelo captura bem a realidade.

Abstract
The increased interest in studying how "things" connect has being leveraged by the growing abundance of a huge amount of data concerning many different networks. In this context, an important aspect is the collection of such data, because in most cases information on network vertices and edges is not publicly available in a centralized or organized repository (eg., Web, P2P, Facebook).
Thus, it is necessary to discover these networks through a sampling process in which the process itself fundamentally influences what is discovered about the network. In this work, we study the process of sampling vertices that reveals local information around randomly chosen vertices. Particularly, we develop analytical models to determine the number of vertices and edges discovered by the sampling process according to the number of samples and other network characteristics (eg., average degree). The evaluation of the proposed models against results obtained through simulations for different network models indicates the conditions under which our model is accurate. 

Topo