2009

A Walk in Facebook: Uniform Sampling of Users in Online Social Networks

Gjoka, Minas, Kurant, Maciej, Butts, Carter T. et al.

Understand

Our goal in this paper is to develop a practical framework for obtaining a uniform sample of users in an online social network (OSN) by crawling its social graph.

Such a sample allows to estimate any user property and some topological properties as well.
To this end, first, we consider and compare several candidate crawling techniques.
Two approaches that can produce approximately uniform samples are the Metropolis-Hasting random walk (MHRW) and a re-weighted random walk (RWRW).

Built on

M. Hansen and W. Hurwitz, “On the Theory of Sampling from Finite Populations,” Annals of Mathematical Statistics , vol. 14, no. 3, 1943
1943
Earlier work this paper cites.
N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller, “Equation of state calculation by fast computing machines,” Journal of Chemical Physics , vol. 21, pp. 1087–1092, 1953
1953
Earlier work this paper cites.
D. Rubin, “Using the SIR algorithm to simulate posterior distributions,” in Bayesian Statistics , 1988, vol. 3, pp. 395–402
1988
Earlier work this paper cites.
J. Geweke, “Evaluating the accuracy of sampling-based approaches to the calculation of posterior moments,” in Bayesian Statistics , 1992, pp. 169–193
1992
Earlier work this paper cites.
A. Gelman and D. Rubin, “Inference from iterative simulation using multiple sequences,” in Statistical science , vol. 7, no. 4, 1992, pp. 457–472
1992
Earlier work this paper cites.
L. Lovász, “Random walks on graphs: A survey,” Combinatorics, Paul Erdos is Eighty , vol. 2, no. 1, pp. 1–46, 1993
1993
Earlier work this paper cites.
S. Wasserman and K. Faust, Social Network Analysis: Methods and Applications . Cambridge University Press, 1994
1994
Earlier work this paper cites.
W. R. Gilks, S. Richardson, and D. J. Spiegelhalter, Markov Chain Monte Carlo in Practice . Chapman and Hall/CRC, 1996
1996
Earlier work this paper cites.
R. Albert, H. Jeong, and A. Barabási, “Diameter of the world-wide web,” Nature , vol. 401, no. 6749, pp. 130–131, 1999
1999
Earlier work this paper cites.
M. R. Henzinger, A. Heydon, M. Mitzenmacher, and M. Najork, “On near-uniform URL sampling,” in Proc. 9th Int. Conf. on World Wide Web , Amsterdam, Netherlands, 2000
2000
Earlier work this paper cites.
M. Newman, “Assortative mixing in networks,” Physical Review Letters , vol. 89, no. 20, p. 208701, 2002
2002
Earlier work this paper cites.
O. Skare, E. Bø lviken, and L. Holden, “Improved Sampling-Importance Resampling and Reduced Bias Importance Sampling,” in Scandinavian Journal of Statistics , 2003, vol. 30, no. 4, pp. 719–737
2003
Earlier work this paper cites.
M. Salganik and D. D. Heckathorn, “Sampling and estimation in hidden populations using respondent-driven sampling,” Sociological Methodology , vol. 34, no. 1, pp. 193–240, 2004
2004
Earlier work this paper cites.
C. Gkantsidis, M. Mihail, and A. Saberi, “Random walks in peer-to-peer networks,” in Proc. IEEE INFOCOM , Hong Kong, China, 2004
2004
Earlier work this paper cites.
P. Sarkar and A. W. Moore, “Dynamic social network analysis using latent space models,” ACM SIGKDD Explorations Newsletter , vol. 7, no. 2, pp. 31–40, Dec. 2005
2005
Earlier work this paper cites.
M. Stumpf, C. Wiuf, and R. May, “Subnets of scale-free networks are not scale-free: sampling properties of networks,” Proc. of the Nat. Academy of Sciences of the United States of America , vol. 102, no. 12, p. 4221, Mar. 2005
2005
Earlier work this paper cites.
D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, and A. Tomkins, “Geographic routing in social networks,” Proc. of the Nat. Academy of Sciences of the United States of America , vol. 102, no. 33, p. 11623, 2005
2005
Earlier work this paper cites.
D. Stutzbach, R. Rejaie, N. Duffield, S. Sen, and W. Willinger, “On unbiased sampling for unstructured peer-to-peer networks,” in Proc. 6th ACM SIGCOMM Conf. on Internet measurement , Rio de Janeiro, Brazil, 2006
2006
Earlier work this paper cites.
S. H. Lee, P.-J. Kim, and H. Jeong, “Statistical properties of sampled networks,” Physical Review E , vol. 73, p. 16102, 2006
2006
Earlier work this paper cites.
L. Becchetti, C. Castillo, D. Donato, A. Fazzone, and I. Rome, “A comparison of sampling techniques for web graph characterization,” in Proc. Workshop on Link Analysis , Philadelphia, PA, 2006
2006
Earlier work this paper cites.
J. Leskovec and C. Faloutsos, “Sampling from large graphs,” in Proc. 12th ACM SIGKDD Int. Conf. on Knowledge discovery and data mining , Philadelphia, PA, 2006, pp. 631–636
2006
Earlier work this paper cites.
R. Kumar, J. Novak, and A. Tomkins, “Structure and Evolution of Online Social Networks,” in Proc. 12th ACM SIGKDD Int. Conf. on Knowledge discovery and data mining , Philadelphia, PA, 2006
2006
Earlier work this paper cites.
L. Backstrom, D. Huttenlocher, J. Kleinberg, and X. Lan, “Group Formation in Large Social Networks: Membership, Growth, and Evolution,” in Proc. 12th ACM SIGKDD Int. Conf. on Knowledge discovery and data mining , Philadelphia, PA, 2006
2006
Earlier work this paper cites.
Y. Ahn, S. Han, H. Kwak, S. Moon, and H. Jeong, “Analysis of topological characteristics of huge online social networking services,” in Proc. 16th Int. Conf. on World Wide Web , Banff, Alberta, Canada, 2007, pp. 835–844
2007
Earlier work this paper cites.

Similar

A. Mislove, M. Marcon, K. Gummadi, P. Druschel, and B. Bhattacharjee, “Measurement and analysis of online social networks,” in Proc. 7th ACM SIGCOMM Conf. on Internet measurement , San Diego, CA, 2007, pp. 29–42
2007
Cited alongside, same era.
M. Cha, H. Kwak, P. Rodriguez, Y.-Y. Ahn, and S. Moon, “I Tube, You Tube, Everybody Tubes: Analyzing the World’s Largest User Generated Content Video System,” in Proc. 7th ACM SIGCOMM Conf. on Internet measurement , San Diego, CA, 2007
2007
Cited alongside, same era.
P. Gill, M. Arlitt, Z. Li, and A. Mahanti, “Youtube traffic characterization: a view from the edge,” in Proc. 7th ACM SIGCOMM Conf. on Internet measurement , San Diego, CA, 2007
2007
Cited alongside, same era.
J. Leskovec, J. Kleinberg, and C. Faloutsos, “Graph evolution: Densification and shrinking diameters,” ACM Transactions on Knowledge Discovery from Data , vol. 1, no. 1, p. 2, Mar. 2007
2007
Cited alongside, same era.
A. Mislove, A. Post, P. Druschel, and K. Gummadi, “Ostra: Leveraging trust to thwart unwanted communication,” in Proc. 5th USENIX Symp. on Networked Systems Design and Implementation , San Francisco, CA, 2008, pp. 15–30
2008
Cited alongside, same era.
J. Leskovec, L. Backstrom, R. Kumar, and A. Tomkins, “Microscopic evolution of social networks,” in Proc. 14th ACM SIGKDD Int. Conf. on Knowledge discovery and data mining , Las Vegas, NV, 2008
2008
Cited alongside, same era.
K. Lewis, J. Kaufman, M. Gonzalez, A. Wimmer, and N. Christakis, “Tastes, ties, and time: A new social network dataset using Facebook. com,” Social Networks, pp. 330–342, 2008
2008
Cited alongside, same era.
A. H. Rasti, M. Torkjazi, R. Rejaie, and D. Stutzbach, “Evaluating Sampling Techniques for Large Dynamic Graphs,” Univ. Oregon, Tech. Rep. CIS-TR-08-01 , Sep. 2008
2008
Cited alongside, same era.
B. Krishnamurthy, P. Gill, and M. Arlitt, “A few chirps about twitter,” in Proc. 1st workshop on Online social networks , Seattle, WA, 2008, pp. 19–24
2008
Cited alongside, same era.
A. Mislove, H. Koppula, K. Gummadi, P. Druschel, and B. Bhattacharjee, “Growth of the flickr social network,” in Proc. 1st workshop on Online social networks , Seattle, WA, 2008, pp. 25–30
2008
Cited alongside, same era.
M. Latapy and C. Magnien, “Complex network measurements: Estimating the relevance of observed properties,” in Proc. IEEE INFOCOM , Phoenix, AZ, 2008, pp. 1660–1668
2008
Cited alongside, same era.
M. A. Porter, “Facebook5 data,” http://www.insna.org/software/data.html
2008
Cited alongside, same era.

Then

E. Baykan, M. Henzinger, S. Keller, S. De Castelberg, and M. Kinzler, “A comparison of techniques for sampling web pages,” in Proc. 26th Int. Symp. on Theoretical Aspects of Computer Science , Freiburg, Germany, 2009
2009
Closest in time.
W. Willinger, R. Rejaie, M. Torkjazi, M. Valafar, and M. Maggioni, “OSN Research: Time to face the real challenges,” in Proc. of 2nd Workshop on Hot Topics in Measurement & Modeling of Computer Systems , Seattle, WA, 2009
2009
Closest in time.
E. D. Kolaczyk, “Statistical Analysis of Network Data,” Springer Series in Statistics , vol. 69, no. 4, 2009
2009
Closest in time.
B. Krishnamurthy, “A measure of online social networks,” in Proc. 1st Int. Conf. on Communication Systems and Networks , Bangalore, India, Jan. 2009
2009
Closest in time.
J. Bonneau, J. Anderson, R. Anderson, and F. Stajano, “Eight friends are enough: Social graph approximation via public listings,” in Proc. EuroSys Workshop on Social Network Systems , Nuremberg, Germany, 2009, pp. 13–18
2009
Closest in time.
“Facebook announcement on 64 bit userIDs, May 2009,” http://developers.facebook.com/blog/post/226
2009
Closest in time.
“The facebook blog: Growing beyond regional networks, June 2009,” http://blog.facebook.com/blog.php?post=91242982130
2009
Closest in time.
“Inside facebook, July 2009,” http://www.insidefacebook.com/2009/07/02/ facebook-now-growing-by-over-700000-users-a-day-updated-engagement-stats/
2009
Closest in time.
J. Leskovec, K. Lang, A. Dasgupta, and M. Mahoney, “Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters,” Internet Mathematics , vol. 6, no. 1, pp. 29–123, 2009
2009
Closest in time.
“Nielsen statistics, June 2010,” http://blog.nielsen.com/nielsenwire/ online_mobile/social-media-accounts-for-22-percent-of-time-online/
2010
Closest in time.
“Alexa traffic statistics for Facebook, June 2010,” http://www.alexa.com/siteinfo/facebook.com
2010
Closest in time.
J. Pujol, V. Erramilli, G. Siganos, X. Yang, N. Laoutaris, P. Chhabra, and P. Rodriguez, “The little engine (s) that could: Scaling online social networks,” ACM SIGCOMM Computer Communication Review , vol. 40, no. 4, pp. 375–386, 2010
2010
Closest in time.
M. Kurant, A. Markopoulou, and P. Thiran, “On the bias of BFS (Breadth First Search),” in Proc. 22nd Int. Teletraffic Congr., also in arXiv:1004.1729 , 2010
Original
2010
Closest in time.
S. Ye, J. Lang, and F. Wu, “Crawling online social graphs,” in Proc. 12th Asia-Pacific Web Conference , Busan, Korea, 2010, pp. 236–242
2010
Closest in time.
K. Avrachenkov, B. Ribeiro, and D. Towsley, “Improving Random Walk Estimation Accuracy with Uniform Restarts,” in I7th Workshop on Algorithms and Models for the Web Graph , 2010
2010
Closest in time.
B. Ribeiro and D. Towsley, “Estimating and sampling graphs with multidimensional random walks,” in Proc. 10th ACM SIGCOMM Conf. on Internet measurement , Melbourne, Australia, 2010
2010
Closest in time.
M. Gjoka, M. Kurant, C. T. Butts, and A. Markopoulou, “Walking in Facebook: A Case Study of Unbiased Sampling of OSNs,” in Proc. IEEE INFOCOM , San Diego, CA, 2010
2010
Closest in time.
B. Ribeiro, P. Wang, and D. Towsley, “On Estimating Degree Distributions of Directed Graphs through Sampling,” UMass, Tech. Rep. UM-CS-2010-046 , 2010
2010
Closest in time.
“Facebook statistics, Dec 2010,” http://facebook.com/press/info.php?statistics
2010
Closest in time.
M. Sirivianos, X. Yang, and K. Kim, “SocialFilter: introducing social trust to collaborative spam mitigation,” in Proc. IEEE INFOCOM , Shanghai, China, 2011
2011
Closest in time.
——, “Towards Unbiased BFS Sampling,” To appear in IEEE J. Sel. Areas Commun. on Measurement of Internet Topologies , 2011
2011
Closest in time.
M. Kurant, M. Gjoka, C. T. Butts, and A. Markopoulou, “Walking on a Graph with a Magnifying Glass: Stratified Sampling via Weighted Random Walks,” in Sigmetrics , 2011
2011
Closest in time.
M. Gjoka, C. T. Butts, M. Kurant, and A. Markopoulou, “Multigraph Sampling of Online Social Networks,” To appear in IEEE J. Sel. Areas Commun. on Measurement of Internet Topologies , 2011
2011
Closest in time.
M. Kurant, M. Gjoka, Y. Wang, Z. W. Almquist, C. T. Butts, and A. Markopoulou, “Coarse-Grained Topology Estimation via Graph Sampling,” Arxiv preprint arXiv:1105.5488 , 2011
Original
2011
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…