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

• Vicente M. Pinheiro UFRJ
• Daniel R. Figueiredo UFRJ
• Antonio A. de A. Rocha UFF

Resumo

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.

Referências

Avrachenkov, K., Ribeiro, B., and Towsley, D. (2010). Improving random walk estimation accuracy with uniform restarts. In Workshop on Alg. Models for Web Graph (WAW).

Barabási, A.-L. (2009). Scale-free networks: A decade and beyond. Science, 325.

Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science, 286.

Gjoka, M., Butts, C. T., Kurant, M., and Markopoulou, A. (2011). Practical recommendations on crawling online social networks. IEEE JSAC, 29(9).

Jin, L., Chen, Y., Hui, P., Ding, C., Wang, T., Vasilakos, A., Deng, B., and Li, X. (2011). Albatross sampling: Robust and effective hybrid vertex sampling for social graphs. In ACM Workshop on Hot Topics in Planet-scale Measurement (HotPlanet).

Kryczka, M., Cuevas, R., Guerrero, C., and Azcorra, A. (2011). Unrevealing the structure of live bittorrent swarms: Methodology and analysis. In IEEE P2P.

Kurant, M., Gjoka, M., Butts, C. T., and Markopoulou, A. (2011a). Walking on a graph with a magnifying glass: stratified sampling via weighted random walks. In ACM SIGMETRICS.

Kurant, M., Markopoulou, A., and Thiran, P. (2011b). Towards unbiased bfs sampling. IEEE JSAC Special Issue on Measurement of Internet Topologies, 29(9).

Mihail, M., Saberi, A., and Tetali, P. (2006). Random walks with lookahead on power law random graphs. Internet Mathematics, 3(2):147–152.

Newman, M. E. J. (2010). Networks: An Introduction. Oxford University Press.

P. Erdos, A. (1960). On the evolution of random graphs. Publications of Mathematical Institute of the Hungarian Academy of Sciences, 5:17–61.

Pedarsani, P., Figueiredo, D. R., and Grossglauser, M. (2008). Densification arising from sampling fixed graphs. In ACM SIGMETRICS.

Ribeiro, B. and Towsley, D. (2010). Estimating and sampling graphs with multidimensional random walks. In ACM SIGCOMM Internet Measurement Conference.

Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of small-world networks. Nature, 393:440–442.