论文部分内容阅读
在线社交网络的迅猛发展吸引了大批学者对其进行分析和研究。大多数针对在线社交网络的实证性研究都需要基于真实的网络节点和网络结构数据进行。然而全网数据通常难以获得,因此需要通过研究网络采样方法来获得具有代表性的网络样本从而保证后续研究的顺利进行。虽然人们已经提出了许多针对网络的采样方法,但对这些采样方法优劣的评价需要一个无偏均匀的样本集作为评价标准。UNI方法则是一个能够提供无偏基准值的采样方法。然而由于在线社交网络用户ID系统的升级,致使UNI方法的采样范围急剧扩大,这使得UNI方法的采样命中率几乎为零,最终导致该方法无法使用。本文对在线社交网络采样方法的研究背景和意义进行了系统性地综述。分析了在线社交网络中UNI方法实际应用时存在的问题和弊端,提出了解决UNI方法在64位整数ID系统中无法使用问题的假设。然后以新浪微博为例,采集了近一亿条用户ID数据,并对用户ID的分布情况进行了统计和分析,发现了新浪微博用户ID的分布规律,同时验证了我们对于在线社交网络用户ID非稀疏分布的假设。而后,我们提出了UNI64方法,该方法借鉴层次聚类和贪心算法的思想,通过分析一定数量的网络原始ID样本,在整个ID系统中划分出有效区间,并控制UNI方法在有效区间内按比例进行采样,提高了采样命中率,从而解决了UNI方法在64位整数系统中无法使用的问题。随后我们通过实验从采样效率和样本质量两个方面对UNI64方法进行了检验,结果表明UNI64方法在真实在线社交网络上的实际采样命中率能够达到我们设定的目标命中率,并且得到样本的分布情况也与实际情况相符。