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

发布时间：2020-04-12 22:49

【摘要】：近年来,随着互联网的飞速发展,社交网络正在影响和改变着人们的生活。基于大量复杂数据的网络结构研究日益受到人们的欢迎。由于现有的在线社交网络中,用户交互信息的数据量庞大,且存在隐私问题,如果直接对整个网络数据进行分析耗时严重,几乎不可能完成。因此,一种可靠而有效的网络采样算法对于在线社交网络(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。然后提取用户页面信息进行处理,整理后进行存储。通过此采样系统能够更加便捷的进行社交网络数据的采集和存储工作。
【图文】：

统计图,社交,网络信息,统计图

1.1 课题研究背景及意义近年来，社交网络如 Facebook，Twitter 正在成为我们生活种不可或缺的一部分，使基于互联网的社会化媒体正影响和改变着我们的生活。由《DIGITAL IN 2018 GLOBAOVERVIEW》报告显示，2018 年全球互联网用户数量为 40.21 亿，同比增长 7%。全球交网络的用户总规模为 31.96 亿，同比增长 13%，而全世界的人口总数目前为 75.9 亿。意味着，社交网络用户在互联网用户中占到了绝大多数比例，并且全世界由四成的人口使用社交网络，而且总用户规模还在持续增长着。其中，当今最流行的在线社交网络之Facebook[1-4]，，它的全球用户总数已突破 20 亿（2017 年 7 月数据）。来自 Facebook 的数显示仅有 5%的用户尚未通过移动设备访问过平台，过去一年里，每天都有百万人开始用社交媒体，平均每秒新增 11 人。此外，Twitter[4, 5]全球每月平均活跃用户达到 3.28 （2017 年 6 月数据）。社交网络以前所未有的规模提供大量信息[6]。

曲线,样本集,不同参数,参数值

有节点度的平均值）。图 3.1 HJ 不同参数下获得样本集的平均度图 3.1 中有 19 条不同颜色的曲线，每条曲线代表着当具有相同值的跳转概率 p，平均度随着 degree-list(k)中 k 参数值变化的曲线。图中标记的点，代表着不同跳转概率 p 和degree-list(k)参数值所对应的样本集网络的平均度。由图中可以看出，通过 HJ 算法获得的样本集的平均度与 p 和 degree-list(k)具有相关性，并且可以得到以下一般规律：当设定 p的值相同时，样本集网络的平均度随着 degree-list(k)中 k 参数值的增加而增加；另一方面，当设定 degree-list(k)中度值 k 相同度时
【学位授予单位】：浙江理工大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP393.09

【相似文献】