Modelagem e Caracterização de um Processo de Amostragem de Vértices em Redes

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.