论文部分内容阅读
近几十年来,互联网历经时代的变革,在线社交网络(OSNs)将人们的面对面的交流逐渐改变为线上虚拟的方式。OSNs注册用户总量及其庞大,人们越爱越重视这类网络数据的研究。与此同时由于数据量庞大,网络结构复杂,使得对整个OSNs进行研究时耗费大量的人力物力。一个可靠的OSNs采样算法可以帮助研究者从完整网络中采集小型代表性样本网络,对于OSNs数据研究意义重大。现有的网络采样算法如广度优先采样算法(BFS),Metropolis-Hasting随机游走算法(MHRW)等已能够从Twitter等大型网络中采集样本网络。但BFS采集的样本节点度数偏高,MHRW采样容易陷入连通良好的子区域。针对现有OSNs采样算法存在的各种弊端,导致采集的样本网络无法反应原始网络特性的问题,本文以网络采样算法为核心内容展开研究。文中主要研究内容如下:1.针对MHRW采样方法无法采集低连通的社交网络的节点,采样过程中易于陷入连通良好的子区域导致部分节点过度入样,获取的样本节点集的特征指标与原始偏差较大等问题。加入节点存储区和全局节点以及存储区的跳跃参数,提出一种多重跳跃无偏的顶点采样算法(MJU),不仅解决了 MHRW的采样缺陷且以更小的采样消耗来采集足够的样本节点。最后基于Twitter和Epinions数据集进行多种算法采样实验,评估节点更新率、样本网络度分布及算法收敛性等网络特性。实验结果证明MJU采样算法能够采集到接近原始网络特征的样本,采集的小型样本数据特性与原始网络匹配度最佳,能够较为准确反应原始网络数据的性质。2.以MJU算法为控制器的核心,设计一个在线社交网络爬虫系统。文中详细的介绍了爬虫系统的框架、组成结构以及爬虫系统进行网络数据采集的工作流程。以知乎网络为研究实例,基于MJU采样算法设计控制器中的URL管理器以便确定网页爬行路径,下载并解析网页数据,分析清洗后存储在资源库中。使用此爬虫系统采集用户数据能够代表整个网络,便于研究网络特性。综上所述,本文研究的MJU采样算法较为高效可行,采集的样本与原网络匹配度较高,以MJU算法为基础设计的网络爬虫系统能够有效爬取网络信息。