Comparative Study of Sampling Methods for Online Social Networks.

摘要

The properties of online social networks are of great interests to the general public as well as IT professionals. Often the raw data are not available and the summaries released by the service providers are sketchy. Thus sampling is needed to reveal the hidden properties and structure of the underlying network. This thesis conducts comparative studies on various sampling methods, including Random Node (RN), Random Walk (RW) and Random Edge (RE) samplings. The properties to be discovered include the average degree and population size of the network. Additionally, this thesis proposes a new sampling method called STAR sampling and applies this method to an online social network Weibo. Furthermore, visualization of network structure is studied to explain the impact of network structure on the performance of sampling methods. We show that RE sampling is better than RN sampling in general. This result is supported by over 20 real-world networks.