论文部分内容阅读
信息行业的飞速发展带来了智能设备的普及,给人们在社交、购物、出行等领域提供了极大的便利。与此同时这也给我们带来了海量的数据信息,例如淘宝用户的购物记录、微博用户相互分享的消息、微信用户的社交群和朋友圈点赞等。互联网公司为了提供更好的服务给大众,于是利用这些海量数据来分析用户行为和喜好,从而为用户提供他们喜欢的事物,如购物时推荐商品等。在此种大数据挖掘的背景下,网络数据挖掘也成为了热门的研究方向之一。而网络数据挖掘领域中,网络社区检测是分析网络结构,划分网络社区的重要工具。作为网络社区检测算法的一个类别,多目标进化算法解决网络社区检测时具有动态自调整和同时得到多个层次分割结果的优点。然而传统进化算法在解决大规模网络社区检测问题时,受到了诸多计算资源的限制,严重影响了检测的效率和算法的适用性。本文针对传统多目标进化算法在大规模网络社区检测上遇到的问题,将多目标进化算法在分布式计算系统Spark进行了实现,并应用在大规模网络的社区检测问题上。本文所做的主要工作和创新如下:1)实现了一种用于大规模网络社区检测的分布式进化算法。首先基于GraphX模型实现了一种种群存储结构。而后通过分析社区检测的主流目标函数及社区检测的主要目的,针对社交网络的特点,以及分布式计算框架的特点,设计了适合分布式计算的多目标函数。该多目标函数分别考虑了社区内连接紧密度和社区间连接的稀疏度。而且去掉了统计社区节点数,从而提高了目标函数计算的异步特性。2)实现了一种基于RDD的社区检测进化算法。首先是基于RDD实现了一个多子种群的种群结构。而后利用分布式计算系统Spark的弹性分布式数据集的作用于分区上的算子,实现了子种群的交叉变异概率的多样性,以及相应的交叉变异操作,和计算目标函数。3)本文在人工网络Benckmark上以及真实世界的小网络和大规模网络上进行了实验以检测算法的有效性。实验结果证明本文所提算法在处理大规模网络时是有效的,且在处理小数据网络时依然有效。