云平台下基于复杂网络的社团发现方法研究

摘要

复杂网络是指具有动力学特征和复杂拓扑结构的大规模网络。不同于随机网络，复杂网络具有小世界、无标度、超家族等特性。利用这些特性可以更好地指导复杂网络的研究。社团是复杂网络中非常重要的结构特征。相同社团的点联系紧密，特征相似;不同社团的点联系稀疏，特征相异。挖掘社团信息可以更加深刻地理解网络结构。然而随着互联网和移动终端技术的突飞猛进，以虚拟社交网络为代表的复杂网络规模迅速扩大，在对这些网络进行社团划分时，传统串行划分方法效率十分低下，无法满足实时处理需求。
　　近些年，云计算成为了一种处理海量数据新的技术和服务模式，可以为用户提供大量具有高扩展、高可靠、完善容错机制的计算资源和存储资源。Hadoop和Spark是其中两个应用最广的平台。两个平台各有特色，Hadoop擅长进行大规模数据的批量处理，而Spark平台更适合进行中量数据的迭代计算。本文将两种云平台与复杂网络社团发现问题相结合，进行了以下几部分工作:
　　1.提出了基于云平台实现的静态社团发现处理框架，主要包含三步:并行粗化预处理、并行社团划分、反粗化调优。实现了以三角形作为粗化源的并行粗化预处理和反粗化调优。实验证明粗化预处理可以在保证原图信息不丢失的前提下，缩小图规模;反粗化调优可以在并行划分社团后进一步优化划分结果。
　　2.研究了基于Hadoop平台实现的多层社团并行划分算法。整个划分过程分为Q值优化与层聚合两个阶段。Q值优化负责在某一层得到最理想的社区结构，层聚合负责将该结构合并，形成下一层的拓扑图。两个阶段反复进行直到全局Q值不再提升。实验证明了该划分算法的可靠性和在处理大规模数据集时的速度优势。
　　3.针对复杂网络中经常出现小规模变化的问题，研究了社团发现增量算法。算法将图变化分成四类处理:增加边、删除边、增加单个点、增加批量点。在处理增加批量点时，设计基于Spark平台的并行处理方案。实验证明，相比于重新运行静态划分算法，增量算法可以保证模块度在几乎不降低的情况下将划分速度提高数倍。
　　4.搭建社团发现结果可视化展示系统。系统可将用户上传的原始图与划分结果文本通过D3技术绘制成社团力导向图，展示在浏览器端，并附有点、边、平均度、模块度等社团信息。

目录

声明

摘要

第1章 绪论

1．1 课题研究背景与意义

1．2 国内外研究现状

1．2．1 社团发现算法

1．2．2 云计算平台

1．3 本文研究内容

1．4 本文章节安排

第2章 相关技术

2．1 非重叠社团发现

2．1．1 评价参数

2．1．2 FastUnfolding

2．2 Hadoop

2．2．1 MapReduce

2．2．2 Yarn

2．3 Spark

2．4 本章小结

第3章 多层社团发现算法

3．1 社团粗化预处理

3．1．1 三角形粗化

3．1．2 粗化算法设计

3．2 基于Hadoop的多层并行化处理

3．2．1 模块度最大化原则

3．2．2 静态结构设计

3．2．3 基于超步的并行化设计

3．3 社团反粗化调优

3．4 多层社团发现并行化算法实验

3．4．1 实验方案设计

3．4．2 粗化预处理实验

3．4．3 多层并行划分实验

3．4．4 实验总结

3．5 本章小结

第4章 社团发现增量算法

4．1 增量算法提出背景

4．2 增量算法设计

4．2．1 边变化

4．2．2 点变化

4．3 增量算法实验

4．3．1 实验方案设计

4．3．2 边变化实验

4．3．3 点变化实验

4．3．4 综合变化

4．3．5 实验总结

4．4 本章小结

第5章 社团发现可视化展示系统

5．1 可视化系统简介

5．1．1 数据可视化技术

5．1．2 前端展示与交互

5．1．3 后台数据处理

5．2 可视化系统实现

5．2．1 系统流程设计

5．2．2 系统交互介绍

5．3 本章小结

结论与展望

结论

展望

致谢

参考文献

攻读硕士学位期间发表的论文及科研成果