IEEE Transactions on Knowledge and Data Engineering
Big data, online social networks, small sample, bias, size estimation
This paper discusses the bias problem when estimating the population size of big data such as online social networks (OSN) using simple random walk. Unlike the traditional estimation problem where the sample size is not very small relative to the data size, in big data a small sample relative to the data size is already very large and costly to obtain. When small samples are used, there is a bias that is no longer negligible. This paper shows analitically that the relative bias can be approximated by the reciprocal of the number of collisions, thereby a bias correction estimator is introduced. The result is further supported by both simulation studies and the real Twitter network that contains 41.7 million nodes.
Lu, Jianguo and Li, Dingding. (2013). Bias Correction in Small Sample from Big Data. IEEE Transactions on Knowledge and Data Engineering, In Press.