论文部分内容阅读
近年来,随着互联网的飞速发展,社交网络正在影响和改变着人们的生活。基于大量复杂数据的网络结构研究日益受到人们的欢迎。由于现有的在线社交网络中,用户交互信息的数据量庞大,且存在隐私问题,如果直接对整个网络数据进行分析耗时严重,几乎不可能完成。因此,一种可靠而有效的网络采样算法对于在线社交网络(OSNs)特征的实际估计非常重要。现有的网络采样算法可以从Facebook等大规模复杂社交网络中获得无偏的样本集,并描述原始网络的关键特征。经典的Metropolis-Hasting随机行走法(Metropolis-Hasting Random Walk,MHRW)通过使用分布函数进行抽样控制,较好的满足了社交网络采样的需求。但是,MHRW算法的采样过程中存在陷入局部区域中过度采样的缺陷。针对在线社交网络数据的上述特性以及MHRW采样算法存在的缺陷,以网络数据采样问题为核心,对网络数据的在线采样、样本评估等方面开展了一系列研究。主要研究内容和创新点如下:1.为解决MHRW采样算法存在的局部区域过度采样问题,引入了随机跳转策略进行改进,得到一种新的混合跳转采样算法(Hybrid Jump sample,HJ)。本文分别在Facebook和Twitter两个数据集上进行了大量实验,通过对比不同算法采样所得到的样本集的收敛性、网络的度分布、采样节点分布和传递性等网络特征,证实HJ算法的采样性能更强且适用范围比较广。并且本文中通过调整HJ算法中跳转概率值的大小进行实验,观察实验结果发现:不同跳转概率对HJ采样算法收敛性的影响微小,可以忽略不计。2.以知乎在线网络为研究实例,运用本文所提出的HJ算法,设计了分布式社交网络采样系统。本文中详细的介绍了系统的构成和资源优化方案。基于HJ算法采集知乎网站的用户URL。然后提取用户页面信息进行处理,整理后进行存储。通过此采样系统能够更加便捷的进行社交网络数据的采集和存储工作。