基于随机跳转策略的社交网络采样算法研究

摘要

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

目录

声明

摘要

1．1课题研究背景及意义

1．2在线复杂社交网络介绍

1．3论文的主要贡献

1．4论文的组织结构

2．1采样的基本概念

2．2在线社交网络采样算法

2．2．1广度优先搜索算法(BFS)

2．2．2用户均匀采样法(UNI)

2．2．3随机行走采样算法(RW)

2．2．4马尔科夫链蒙特卡洛采样算法(MHRW)

2．2．5随机跳转采样算法(RJ)

2．3本章小结

3．1设计思想

3．2 HJ算法描述

3．2．1获取跳转节点集

3．2．2三维平均度分布模型进行参数分析选取

3．3 HJ算法伪代码、流程图及复杂度分析

3．3．1 HJ算法伪代码

3．3．2 HJ算法流程图

3．3．3 HJ算法复杂性分析

3．4实验数据集描述

3．5采样性能的对比实验

3．5．1收敛性分析

3．5．2网络度分布分析

3．5．3采样节点分布分析

3．5．4网络的传递性、同配性、簇类系数分析

3．6本章小结

第四章社交网络采样系统

4．1社交网络采样系统框架

4．1．1 uI池管理器

4．1．2 HTML管下载器及解析器

4．1．3数据存储器

4．1．4控制调度器

4．1．5系统执行流程

4．2本章小结

5．1全文总结

5．2后续工作与展望

参考文献

攻读硕士学位期间参加的科研项目和研究成果

致谢