在线社交网络的自适应UNI64采样方法研究

发布时间：2018-06-03 17:12

本文选题：在线社交网络 + 采样方法　；参考：《北京化工大学》2016年硕士论文

【摘要】：在线社交网络(Online Social Network, OSN)的兴起给网络带来了新的革命,同时它自身的很多特性也对现实社会产生了广泛而深入的影响。近些年来已吸引了很多研究学者对在线社交网络进行分析和研究。由于在线社交网络属于大规模网络,其自身特性和行为模式较为复杂,无法准确的获得真实网络的全部数据,所以大部分研究都是基于真实网络的样本网络进行的。对于在线社交网络的研究,样本网络质量对研究结果是极为重要的。因此,通过研究网络的采样方法获得一个能够反映真实网络某一方面或某些方面特征的网络样本是在线社交网络研究的前提保障。通过大量的研究,学者们已经提出了多种对于网络的采样方法,但是需要一个无偏均匀的样本集来对这些采样方法和结果的优劣进行评价。而UNI方法采样获得的样本网络恰好符合要求,它以拒绝-接受采样为依据进行无偏均匀的采样。但该方法也有局限性,仅适用于采集用户ID系统为32位整数的网络,现在大多数在线社交网络的用户ID系统都已经升级为64位整数系统,这就使得表现良好的UNI方法对64位整数系统的采样命中率几乎为零,导致该方法无法继续使用。本文采用统计学方法对在线社交网络用户64位ID系统的分布情况进行了详细分析,其结果表明,在线社交网络用户ID的分布呈非均匀非随机分布。根据此分析结果并结合自适应的思想对UNI方法进行了改进,设计实现一种适用于64位整数用户ID系统的高效无偏均匀的自适应采样方法,称为“自适应UNI64方法”。最后在新浪微博数据集上对该方法的采样效果进行了实验验证,实验结果表明,自适应UNI64方法能在64位整数ID系统空间进行采样,且采样命中率和采样效率较UNI方法有很大提高,得到的样本网络有效ID的分布符合实际。
[Abstract]:The rise of online Social Network, OSN) has brought a new revolution to the network, and many of its own characteristics have had a wide and deep impact on the real society. In recent years, many researchers have been attracted to analyze and study online social networks. Because the online social network belongs to the large-scale network, its own characteristic and the behavior pattern is more complex, cannot accurately obtain the real network all data, so most of the research is based on the real network sample network. For the research of online social network, the quality of sample network is very important to the research results. Therefore, it is the premise of online social network research to obtain a network sample which can reflect the characteristics of some aspect or some aspect of the real network by studying the sampling method of the network. Through a lot of research, scholars have proposed a variety of sampling methods for the network, but an unbiased uniform sample set is needed to evaluate the merits and demerits of these sampling methods and results. The sample network obtained by UNI method meets the requirements, and it is unbiased and uniform sampling based on rejection-accept sampling. However, this method has its limitations. It is only suitable for the network where the user ID system is a 32-bit integer. Nowadays, most online social network user ID systems have been upgraded to 64-bit integer systems. This makes the good performance of the UNI method to 64-bit integer system sampling hit rate is almost zero, resulting in the method can not continue to use. In this paper, the distribution of 64 bit ID system for online social network users is analyzed in detail by statistical method. The results show that the distribution of online social network user ID is non-uniform and non-random. According to the analysis results and the adaptive idea, the UNI method is improved, and an efficient and unbiased adaptive sampling method for 64-bit integer user ID system is designed and implemented, which is called "adaptive UNI64 method". Finally, the sampling effect of this method is verified on Sina Weibo dataset. The experimental results show that the adaptive UNI64 method can be sampled in 64-bit integer ID system space. The sample hit rate and sampling efficiency are much higher than that of the UNI method, and the distribution of the effective ID of the sample network is in line with the actual situation.
【学位授予单位】：北京化工大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP393.09

【参考文献】