GraphLab云计算平台下社会网络的社区识别

发布时间：2019-05-24 02:08

【摘要】：随着社会网络的兴起和流行,越来越多的人加入到社会网络的分析研究中。一般来说,社会网络由节点相互连接而成,整个网络以社区结构的形式呈现,可看作由多个社区结构组成,社区结构内部的节点之间连接稠密,社区之间则连接相对稀疏,社区结构对社会网络的分析研究的作用很大。因此,社会网络社区结构的识别已成为社会网络特性分析的研究热点,并且出现了很多经典的社区识别算法。随着网络规模的扩大,社会网络中节点的数量不断增加,很多交友网站如腾讯、新浪微博等用户人数已达到10亿。由于经典社区识别算法大都为单机迭代算法,往往只适用于小规模社会网络的社区识别,对于这样大规模的社会网络,这些经典识别算法已不能有效地识别社区结构。针对此问题,本文基于Graph Lab云计算平台提出了能够并行计算的社区识别算法。本文首先阐述社会网络和社区识别的相关理论知识,如静态网络和动态网络的图表示形式,介绍社区结构的基本描述方式,并给出社区质量的衡量准则,用来评判社区识别算法的优劣。其次,概述处理大数据所需要的并行计算框架,如Hadoop框架下的Map Reduce模型,基于BSP模型的大图处理框架Pregel,并详细介绍本文所依赖的图并行计算框架Graph Lab,Graph Lab作为一种并行的云计算平台,依据Gather-Apply-Scatter三步计算模型,能有效进行大规模图数据的计算。最后,详细介绍在Graph Lab并行计算模型上针对大规模静态社会网络和动态社会网络而分别提出的社区识别算法,即基于重要节点扩展的重叠社区识别算法DOCVN(Detecting the Overlapping Community algorithm based on Vital Node Expanding in Graph Lab)以及基于IC算法改进的并行动态社区识别算法PDCI(Parallel Dynamic Community Identification)。在DOCVN算法中,提出了通过节点的Page Rank值选取重要节点并基于节点到重要节点的节点归属度值进行重要节点扩展的思想来实现大规模静态网络的社区识别;而本文所提的PDCI算法,其算法思想是基于IC算法的并行改进,根据IC算法中所定义的增量相关顶点集以及增量式社区识别的评价函数,本算法首先在Spark并行计算框架上实现查找增量相关顶点集的预处理,然后在Graph Lab平台上并行实现增量式的社区识别。实验表明本文所提的这两个算法可以有效地识别大规模静态网络和动态网络的重叠社区结构,为大规模社会网络社区识别提供了新的思想和方法。
[Abstract]:......
【学位授予单位】：宁波大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP391.41;TP393.09

【参考文献】