Modelagem e Caracterização de um Processo de Amostragem de Vértices em Redes - Pinheiro, Vicente M.; Figueiredo, Daniel R.; Rocha, Antonio A. de A. (Anais do Workshop em Desempenho de Sistemas Computacionais e de Comunicação (WPerformance), 2012)
A explosão pelo interesse em estudar como as “coisas” se conectam vem sendo alavancada pela crescente abundância de enormes massas de dados sobre as mais diferentes redes. Neste contexto, um aspecto importante diz respeito à coleta desses dados, pois na maioria dos casos informações sobre vértices e arestas das redes não estão disponíveis publicamente de forma centralizada ou organizada (ex. Web, rede P2P, Facebook). Desta forma, é necessário descobrir estas redes através de algum processo de amostragem, que fundamentalmente irá influenciar o que será descoberto. Neste trabalho estudamos o processo de amostragem de vértices que revela informação local a vértices escolhidos aleatoriamente. Em particular, desenvolvemos modelos analíticos para calcular o número de vértices e arestas descobertos pelo processo em função do número de amostras e de outras características da rede (ex. grau médio). A avaliação dos modelos propostos com resultados obtidos através de simulações em diferentes modelos de rede confirmam nosso modelo exato e mostram quando nosso modelo aproximado é preciso.