Research On Fast Dynamic Adaptive Sampling Techniques In Large Online Social Networks

With the widespread popularity of the Internet and mobile devices,the number of online social media users has proliferated,making online social networks(OSNs)have become quite complex with their characteristics and behavior patterns,attracting many researchers to analyze and study the characteristics,patterns,and rules of online social networks.However,due to the large scale of online social networks,privacy problems,and access restrictions,it is difficult for researchers to obtain and analyze the whole large online social network.Therefore,many studies of social networks are based on sampled subgraphs.The quality of the sampled subgraph plays an important role in the research results,so it poses a great challenge whether the sampled subgraph can reflect the characteristics of the original network and can represent the entire original network.Among the existing sampling methods,Uniform Sample(UNI)is usually used to evaluate the unbiasedness of sampling results due to its ability to obtain topological characteristics of the original network.However,UNI has low sampling efficiency with the acceptance-rejection sampling mechanism.In this thesis,based on the analysis of UNI and the distribution of the OSNs user IDs,a dynamic adaptive UNI sampling method(DaptUNI)is proposed.DaptUNI overcomes the low sampling efficiency of UNI by dividing user ID space evenly into intervals and dynamically adjusting their sizes during the sampling process.In addition,we proposed another method called DaptUNI+N,which is based on DaptUNI.By DaptUNI+N,neighbors of the sampled nodes are taken as sampled nodes,too.The sampling efficiency can be further improved in that way.Finally,these two methods and other classical methods are applied to Sina Weibo and the Twitter network for sampling.The experimental results prove that DaptUNI and DaptUNI+N methods proposed in this thesis have a significant improvement in sampling efficiency and sampling effect.