The DOI matches its Crossref record; 32 of the 32 references it cites were found in a registry or an index.
Walking in Facebook: A Case Study of Unbiased Sampling of OSNs
Abstract
With more than 250 million active users, Facebook (FB) is currently one of the most important online social networks. Our goal in this paper is to obtain a representative (unbiased) sample of Facebook users by crawling its social graph. In this quest, we consider and implement several candidate techniques. Two approaches that are found to perform well are the Metropolis-Hasting random walk (MHRW) and a re-weighted random walk (RWRW). Both have pros and cons, which we demonstrate through a comparison to each other as well as to the "ground-truth" (UNI - obtained through true uniform sampling of FB userIDs). In contrast, the traditional Breadth-First-Search (BFS) and Random Walk (RW) perform quite poorly, producing substantially biased results. In addition to offline performance assessment, we introduce online formal convergence diagnostics to assess sample quality during the data collection process. We show how these can be used to effectively determine when a random walk sample is of adequate size and quality for subsequent use (i.e., when it is safe to cease sampling). Using these methods, we collect the first, to the best of our knowledge, unbiased sample of Facebook. Finally, we use one of our representative datasets, collected through MHRW, to characterize several key properties of Facebook.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Equation of State Calculations by Fast Computing Machines
Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953) · The Journal of Chemical Physics · doi:10.1063/1.1699114 · Cited by 37,192
Social Network Analysis: Methods and Applications
Wasserman, S. S., & Faust, K. (1994) · Cited by 17,993
Social Network Analysis: Methods and Applications
Wasserman, S., & Faust, K. (1994) · doi:10.1017/cbo9780511815478 · Cited by 17,557
Inference from iterative simulation using multiple sequences
Gelman, A., & Rubin, D. B. (1992) · Statistical Science · doi:10.1214/ss/1177011136 · Cited by 16,627
Markov Chain Monte Carlo in Practice
(1995) · Chapman & Hall/CRC eBooks · doi:10.1201/b14835 · Cited by 7,757
Assortative Mixing in Networks
Newman, M. E. J. (2002) · Physical Review Letters · doi:10.1103/physrevlett.89.208701 · Cited by 4,988
Respondent-Driven Sampling: A New Approach to the Study of Hidden Populations
Heckathorn, D. D. (1997) · Social Problems · doi:10.1525/sp.1997.44.2.03x0221m · Cited by 4,409
Evaluating the Accuracy of Sampling-Based Approaches to the Calculation of Posterior Moments
Geweke, J. (1992) · Bayesian Statistics 4 · doi:10.1093/oso/9780198522669.003.0010 · Cited by 3,307
Measurement and analysis of online social networks
Mislove, A., Marcon, M., Gummadi, K. P., Druschel, P., & Bhattacharjee, B. (2007) · Proceedings of the 7th ACM SIGCOMM conference on Internet measurement · doi:10.1145/1298306.1298311 · Cited by 3,057
5. Sampling and Estimation in Hidden Populations Using Respondent-Driven Sampling
Salganik, M. J., & Heckathorn, D. D. (2004) · Sociological Methodology · doi:10.1111/j.0081-1750.2004.00152.x · Cited by 1,953
Random Walks on Graphs: A Survey
Lovász, L. (2001) · Cited by 1,411
Markov Chain Monte Carlo in Practice.
Kass, R. E., Gilks, W. R., Richardson, S., & Spiegelhalter, D. J. (1997) · Journal of the American Statistical Association · doi:10.2307/2965438 · Cited by 1,380
Leskovec, J., & Faloutsos, C. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150479 · Cited by 1,170
Tastes, ties, and time: a new social network dataset using Facebook.com
Lewis, K., Kaufman, J., Gonzalez, M., Wimmer, A., & Christakis, N. (2008) · Social Networks · doi:10.1016/j.socnet.2008.07.002 · Cited by 1,024
Analysis of topological characteristics of huge online social networking services
Ahn, Y.-Y., Han, S., Kwak, H., Moon, S., & Jeong, H. (2007) · Proceedings of the 16th international conference on World Wide Web · doi:10.1145/1242572.1242685 · Cited by 937
User interactions in social networks and their implications
Wilson, C., Boe, B., Sala, A., Puttaswamy, K. P. N., & Zhao, B. Y. (2009) · Proceedings of the 4th ACM European conference on Computer systems · doi:10.1145/1519065.1519089 · Cited by 879
Probability Statistics and Random Processes for Electrical Engineering
Leon‐Garcia, A. (2008) · Medical Entomology and Zoology · Cited by 752
Krishnamurthy, B., Gill, P., & Arlitt, M. (2008) · Proceedings of the first workshop on Online social networks · doi:10.1145/1397735.1397741 · Cited by 697
Probability based estimation theory for respondent driven sampling
Volz, E., & Heckathorn, D. D. (2008) · Journal of Official Statistics · Cited by 667
On the Theory of Sampling from Finite Populations
Hansen, M. H., & Hurwitz, W. N. (1943) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177731356 · Cited by 603
Random walks in peer-to-peer networks
Gkantsidis, C., Mihail, M., & Saberi, A. (2004) · IEEE INFOCOM 2004 · doi:10.1109/infcom.2004.1354487 · Cited by 525
Statistical properties of sampled networks
Lee, S. H., Kim, P.-J., & Jeong, H. (2006) · Physical Review E · doi:10.1103/physreve.73.016102 · Cited by 440
Characterizing privacy in online social networks
Krishnamurthy, B., & Wills, C. E. (2008) · Proceedings of the first workshop on Online social networks · doi:10.1145/1397735.1397744 · Cited by 295
Henzinger, M. R., Heydon, A., Mitzenmacher, M., & Najork, M. (2000) · Computer Networks · doi:10.1016/s1389-1286(00)00055-4 · Cited by 269
Poking facebook: characterization of osn applications
Gjoka, M., Sirivianos, M., Markopoulou, A. P., & Yang, X. (2008) · doi:10.1145/1397735.1397743 · Cited by 99
Self-citationOn unbiased sampling for unstructured peer-to-peer networks
Stutzbach, D., Rejaie, R., Duffield, N. G., Sen, S. B., & Willinger, W. (2006) · ACM Internet Measurement Conference (IMC) · doi:10.1145/1177080.1177084 · Cited by 97
A Walk in Facebook: Uniform Sampling of Users in Online Social NetworksPreprint
Gjoka, M., Kurant, M., Butts, C. T., & Markopoulou, A. P. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0906.0060 · Cited by 83
Self-citationImproved Sampling‐Importance Resampling and Reduced Bias Importance Sampling
Skare, Ø., Bølviken, E., & Holden, L. (2003) · Scandinavian Journal of Statistics · doi:10.1111/1467-9469.00360 · Cited by 81
Community Structure in Online Collegiate Social NetworksPreprint
Traud, A. L., Kelsic, E. D., Mucha, P. J., & Porter, M. A. (2008) · arXiv (Cornell University) · Cited by 62
A Comparison of Sampling Techniques for Web Graph Characterization
Becchetti, L., Castillo, C., & Fazzone, A. (2006) · Cited by 54
Research on online social networks
Willinger, W., Rejaie, R., Torkjazi, M., Valafar, M., & Maggioni, M. (2010) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/1710115.1710125 · Cited by 34
Evaluating Sampling Techniques for Large Dynamic Graphs
Rasti, A. H., Torkjazi, M., Rejaie, R., Duffield, N. G., Willinger, W., Stutzbach, D., & Enterprises, S. (2008) · Cited by 33
Cited by
Online Human-Bot Interactions: Detection, Estimation, and Characterization
Varol, O., Ferrara, E., Davis, C., Menczer, F., & Flammini, A. (2017) · Proceedings of the International AAAI Conference on Web and Social Media · doi:10.1609/icwsm.v11i1.14871 · Cited by 981
“This approach avoids known biases of other methods such as snowball and breadth-first sampling, which rely on the selection of an initial group of users (Gjoka et al. 2010; Morstatter et al. 2013).”
MethodThe Anatomy of the Facebook Social Graph
Ugander, J., Karrer, B., Backstrom, L., & Marlow, C. (2011) · arXiv · doi:10.48550/arxiv.1111.4503 · Cited by 819
Social structure of Facebook networks
Traud, A. L., Mucha, P. J., & Porter, M. A. (2012) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2011.12.021 · Cited by 707
Random walks and diffusion on networks
Masuda, N., Porter, M. A., & Lambiotte, R. (2017) · Physics Reports · doi:10.1016/j.physrep.2017.07.007 · Cited by 657
Detecting Automation of Twitter Accounts: Are You a Human, Bot, or Cyborg?
Chu, Z., Gianvecchio, S., Wang, H., & Jajodia, S. (2012) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2012.75 · Cited by 634
Metadata
- Authors
- Gjoka, M., Kurant, M., Butts, C. T., & Markopoulou, A.
- Venue
- 2010 Proceedings IEEE INFOCOM
- Publisher
- IEEE
- Published
- 2010-03
- Pages
- 1-9
- OpenAlex
- W2137135938
- Cited by
- 671
- References
- 32
- FWCI
- 46.77
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.