论文部分内容阅读
由于互联网的兴起和通信技术的发展,人们使用在线社交网络进行社会活动已成为日常生活的一部分。在线社交网络已经渗透到人们生活的方方面面,是时下最重要的移动互联网应用。许多组织对在线社交网络感兴趣,社会学家会收集相关数据用以研究在线用户行为。市场调查员根据在线社交网络挖掘信息,用以指定市场推荐。社交网络的提供商通过了解社交图和用户行为,优化数据存储设计和云服务或提供个性化服务的方式来改善用户体验。社交网络如此庞大的数据量给研究带来了许多困难。首先,企业基于商业机密以及用户隐私的考虑,并不愿意分享他们的商业数据,即使数据是以匿名的形式。其次,从大规模在线社交网络中获取所有数据也不现实,因为要获取数以亿计的用户是极其耗时的。于此同时,即使利用高性能计算机集群处理如此庞大的数据也非常困难。最后,在线社交网络上用户数量增加迅速,用户间的关系也会频繁的发生改变。因此对社交网络设计有效的采样算法非常重要。广度优先搜索算法(BFS)是常用的图遍历方法,但是BFS会过度的采集高度节点同时这种偏移很难被纠正。随机游走(RW)是一种经典的网络节点游走方法,但同样偏向于采集高度的节点且采样效率低。Metropolis-Hastings随机游走(MHRW)是一种典型的无偏采样算法,但是该算法在高聚类子网中会过度的重复采集低度节点。本文的主要研究成果如下:(1)本文基于MHRW算法提出了一种改进,称之为无偏延迟采样(UD),这个算法在MHRW的采样过程中加入了延迟接收函数,使得采样的网络更加可靠。通过大量的实验,证明UD算法可以适应不同连通程度的网络。一方面,当采样数据集没有重复节点时UD算法有更好的网络度分布属性。另一方面,UD算法可以减少重复节点被采样的概率并改善网络探测能力。(2)在真实社交网络微博中实现了我们所设计的UD采样算法,并与其它常用的采样算法BFS、RW、MHRW一起在微博中各采集了10万条数据,实验发现,UD采样算法在真实环境下可以减少采样重复率。(3)实际运用采样算法时,并不知道何时停止采样,停止较早会使采样数据不充分。我们提出了一种在采样过程中判断数据是否充足的算法,该算法基于Geweke收敛判定准则。通过实验证明,我们的数据收敛判定方法可以指导采样过程安全的终止。判断采样数据是否充分对实际数据的抓取至关重要。