Skip to main content
eScholarship
Open Access Publications from the University of California

Estimating the size of online social networks

  • Author(s): Ye, Shaozhi
  • Wu, S F
  • et al.
Abstract

The huge size of online social networks (OSNs) makes it prohibitively expensive to precisely measure any properties which require the knowledge of the entire graph. To estimate the size of an OSN, i.e., the number of users an OSN has, this paper introduces two estimators using widely available OSN functionalities/services. The first estimator is a maximum likelihood estimator (MLE) based on uniform sampling. An O(logn) algorithm is developed to solve the estimator, which is 70 times faster than the naive linear probing algorithm in our experiments. The second estimator is based on random walkers and we generalize it to estimate other graph properties. In-depth evaluations are conducted on six real OSNs to show the bias and variance of these two estimators. Our analysis addresses the challenges and pitfalls when developing and implementing such estimators for OSNs.

Many UC-authored scholarly publications are freely available on this site because of the UC Academic Senate's Open Access Policy. Let us know how this access is important for you.

Main Content
Current View