Adaptive UNI64 Sampling Method On Online Social Networks

The rise of Online Social Network (OSN) brings a new revolution of the Internet. At the same time, it has influenced the real society widely and deeply with its abundant characteristics. The online social networks have attracted a large number of researchers in recent years.Since the online social networks are usually, and it is almost impossible to obtain the data of the whole natworks, the research on online social networks is usually based on sampled networks from real networks. Therefore, the quality of the sampled networks is vital to the research on online social networks. A sampled network is always hoped to reflect as many features of the real network as possible.A variety of sampling methods for network have been proposed by researchers. An unbiased uniform sample dataset is usually used as the "ground truth" to evaluate the pros and cons of these sampling methods. Some researchers put forward an unbiased uniform sampling method basing on acceptance-rejection method, which is called as-UNI. However, this method just can be used in the case that user IDs are 32-bit integers. Nowerdays, most online social networks have upgraded their user IDs to 64-bit integers.That makes UNI unavailable now.In this thesis, an adaptive UNI method for sampling online social networks is proposed basing on the observation of the non-uniform distribution of user 64-bit integer IDs.It is suitable for the 64-bit integer user ID system, and called "adaptive UNI64 method".The sampling method is examined and evaluated by the dataset of Sina Weibo. Experimental results show that the adaptive UNI64 method can be applied to sampling the 64-bit integer ID system space. The sampling rate and efficiency are higher than those of UNI method.The distribution of sampled valid IDs is realistic.