Modeling and Characterization of a Vertex Sampling Process in Networks

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

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.

References

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.