Estimating the Size of Online Social Networks. Ye, S. Y. S. & Wu, F. W. F. In Proc. 2010 IEEE SocialCom, Minneapolis, MN, 2010.
doi  abstract   bibtex   
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.
@inproceedings{Ye2010a,
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.},
address = {Minneapolis, MN},
author = {Ye, Shaozhi Ye Shaozhi and Wu, Felix Wu Felix},
booktitle = {Proc. 2010 IEEE SocialCom},
doi = {10.1109/SocialCom.2010.32},
file = {:home/ecem/Dropbox/mendeley\_sampling\_references/Ye, Wu/2010\_Ye, Wu\_Estimating the Size of Online Social Networks.pdf:pdf},
isbn = {978-1-4244-8439-3},
keywords = {Online social networks,estimation,maximum likelihood,random walker},
title = {{Estimating the Size of Online Social Networks}},
year = {2010}
}

Downloads: 0