基于Spark的大规模社交网络社区发现算法设计与实现

发布时间：2017-09-19 19:04

  本文关键词：基于Spark的大规模社交网络社区发现算法设计与实现

  更多相关文章： 社区发现 大规模 标签传播算法 Spark 并行化

【摘要】：近年来,随着互联网技术的飞速发展,加上移动终端及移动互联网的逐渐普及,越来越多的人成为了社交网络中的一员。社交网络的不断发展,导致了社交网络的规模呈现出了爆炸式的增长。社区发现也面临着数据量大、复杂性高等问题。由于传统的社区发现算法大多数只能适用于一些小规模的网络或者实验生成的网络,当网络中用户数量的规模很大时,使用传统的社区发现算法受到了硬件及算法自身复杂度的限制,因此很难高效的来处理如此海量的数据,严重制约了大规模社交网络中的社区发现。本文针对传统社区发现方法难以适应大规模的社交网络场景,采用Spark大数据处理框架将传统的社区发现算法并行化,利用集群所具有的计算优势来处理海量的用户数据,降低算法执行所消耗的时间。选取经典的标签传播方法作为基础算法,在Spark平台上进行并行化拓展,实现了一种基于Spark的并行化社区发现算法,同时针对算法在实验过程中所产生的问题对算法进行了相应的改进。最后,通过使用Faceboo、Twitter社交网络数据集进行实验,验证了本文所设计的算法的高效与简洁性。本论文的主要工作及创新点有以下几方面：(1)首先,对传统的社区发现算法进行理论研究,同时对其并行化的可行性进行分析；接着,对当前流行的Spark等大数据处理工具作了理论与技术上的分析,为后续算法的并行化提供技术保障。(2)选择传统的标签传播算法作为基础算法,通过将其与Spark技术相结合进行并行化实现,解决了传统标签算法难于解决大规模网络社区发现的问题；(3)为解决基于Spark的标签传播算法在实验过程中表现出的随机性较强等问题,引入社区核心节点影响力的概念,并将其用于标签传播算法之中。同时实现了基于Spark的PageRank算法来解决社区核心节点影响力的计算。通过在Spark平台上实现了改进前后的算法,对改进前后算法所得的实验结果进行了详细的分析,并对出现的相关问题进行了深入探讨。最后,通过几组对比实验对两种算法所发现社区质量进行了比较。
【关键词】：社区发现 大规模 标签传播算法 Spark 并行化
【学位授予单位】：扬州大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP393.09
【目录】：

• 摘要4-5
• Abstract5-9
• 第一章 绪论9-16
• 1.1 选题背景及其意义9-10
• 1.2 研究现状10-14
• 1.2.1 基于图算法的社区发现11
• 1.2.2 基于启发式的算法11-13
• 1.2.3 基于模块度优化的社区发现算法13-14
• 1.3 本文主要工作及章节安排14-16
• 第二章 相关技术基础16-31
• 2.1 社交网络的表示16
• 2.2 社区发现16-18
• 2.3 Spark相关技术介绍18-24
• 2.3.1 Spark的架构20-21
• 2.3.2 Spark运行逻辑21-22
• 2.3.3 RDD22
• 2.3.4 GraphX22-23
• 2.3.5 Spark中图数据的存储结构23-24
• 2.4 Pregel计算框架介绍24-28
• 2.5 Spark的优势28-29
• 2.6 社区质量评价29-30
• 2.7 本章小结30-31
• 第三章 基于Spark的标签传播算法31-48
• 3.1 传统LPA算法31-33
• 3.2 基于Spark的并行化LPA算法33-37
• 3.2.1 Spark化图数据处理33-34
• 3.2.2 LPA算法Spark化实现34-37
• 3.3 实验平台架构及数据集37-40
• 3.3.1 实验系统架构37-39
• 3.3.2 实验数据39-40
• 3.4 实验40-47
• 3.4.1 Facebook数据集40-43
• 3.4.2 Twitter数据集43-45
• 3.4.3 实验分析45-46
• 3.4.4 实验对比46-47
• 3.5 本章小结47-48
• 第四章 基于Spark的改进的标签传播算法48-60
• 4.1 算法思想48-50
• 4.2 社区核心节点影响力50-53
• 4.2.1 PageRank算法51
• 4.2.2 基于Spark的PageRank算法51-53
• 4.3 基于Spark的改进的标签传播算法实现53-54
• 4.4 实验54-59
• 4.4.1 Facebook数据集55-56
• 4.4.2 Twitter数据集56-57
• 4.4.3 两个算法实验结果的对比分析57-59
• 4.5 本章小结59-60
• 第五章 总结和展望60-63
• 5.1 本文工作总结60-62
• 5.2 进一步工作62-63
• 参考文献63-67
• 致谢67-68

【相似文献】

中国期刊全文数据库 前10条

1 ;基于位置的手机社交网络“贝多”正式发布[J];中国新通信;2008年06期

2 曹增辉;;社交网络更偏向于用户工具[J];信息网络;2009年11期

3 ;美国:印刷企业青睐社交网络营销新方式[J];中国包装工业;2010年Z1期

4 李智惠;柳承烨;;韩国移动社交网络服务的类型分析与促进方案[J];现代传播(中国传媒大学学报);2010年08期

5 贾富;;改变一切的社交网络[J];互联网天地;2011年04期

6 谭拯;;社交网络:连接与发现[J];广东通信技术;2011年07期

7 陈一舟;;社交网络的发展趋势[J];传媒;2011年12期

8 殷乐;;全球社交网络新态势及文化影响[J];新闻与写作;2012年01期

9 许丽;;社交网络:孤独年代的集体狂欢[J];上海信息化;2012年09期

10 李玲丽;吴新年;;科研社交网络的发展现状及趋势分析[J];图书馆学研究;2013年01期

中国重要会议论文全文数据库 前10条

1 赵云龙;李艳兵;;社交网络用户的人格预测与关系强度研究[A];第七届（2012）中国管理学年会商务智能分会场论文集（选编）[C];2012年

2 宫广宇;李开军;;对社交网络中信息传播的分析和思考——以人人网为例[A];首届华中地区新闻与传播学科研究生学术论坛获奖论文[C];2010年

3 杨子鹏;乔丽娟;王梦思;杨雪迎;孟子冰;张禹;;社交网络与大学生焦虑缓解[A];心理学与创新能力提升——第十六届全国心理学学术会议论文集[C];2013年

4 毕雪梅;;体育虚拟社区中的体育社交网络解析[A];第九届全国体育科学大会论文摘要汇编(4)[C];2011年

5 杜p，

本文编号：883364