论文部分内容阅读
在线社交网络(Online Social Network, OSN)的兴起给网络带来了新的革命,同时它自身的很多特性也对现实社会产生了广泛而深入的影响。近些年来已吸引了很多研究学者对在线社交网络进行分析和研究。由于在线社交网络属于大规模网络,其自身特性和行为模式较为复杂,无法准确的获得真实网络的全部数据,所以大部分研究都是基于真实网络的样本网络进行的。对于在线社交网络的研究,样本网络质量对研究结果是极为重要的。因此,通过研究网络的采样方法获得一个能够反映真实网络某一方面或某些方面特征的网络样本是在线社交网络研究的前提保障。通过大量的研究,学者们已经提出了多种对于网络的采样方法,但是需要一个无偏均匀的样本集来对这些采样方法和结果的优劣进行评价。而UNI方法采样获得的样本网络恰好符合要求,它以拒绝-接受采样为依据进行无偏均匀的采样。但该方法也有局限性,仅适用于采集用户ID系统为32位整数的网络,现在大多数在线社交网络的用户ID系统都已经升级为64位整数系统,这就使得表现良好的UNI方法对64位整数系统的采样命中率几乎为零,导致该方法无法继续使用。本文采用统计学方法对在线社交网络用户64位ID系统的分布情况进行了详细分析,其结果表明,在线社交网络用户ID的分布呈非均匀非随机分布。根据此分析结果并结合自适应的思想对UNI方法进行了改进,设计实现一种适用于64位整数用户ID系统的高效无偏均匀的自适应采样方法,称为“自适应UNI64方法”。最后在新浪微博数据集上对该方法的采样效果进行了实验验证,实验结果表明,自适应UNI64方法能在64位整数ID系统空间进行采样,且采样命中率和采样效率较UNI方法有很大提高,得到的样本网络有效ID的分布符合实际。