基于MapReduce的并行图序列社区挖掘算法研究

摘要

作为数据挖掘的重要研究方向，图序列社区挖掘在社交网络等实际问题中有着广泛应用。如何精确地获得图序列中有价值的信息，以及如何加快算法在大规模数据集上的速度尤为关键。现有社区挖掘方法大多基于树状图记录的分裂算法或自底向上的凝聚算法，且多为静态挖掘而无时间方面的考虑。针对上述问题，本文提出基于编码代价的图序列社区挖掘算法GSCM，并设计出基于谱聚类的GSCM-SC算法，在Hadoop MapReduce并行计算框架下对后者进行并行化研究提出了PGSCM算法。
　　本文研究二值图序列，首先提出了编码代价的概念，通过优化此代价函数提出GSCM算法。算法不需任何参数，并借鉴最小描述长度原理使社区划分的复杂性与社区结构的质量达到平衡。将信息压缩后再聚类以获得较好的初始划分，并利用遗传算法的随机演化和择优思想来避免被困于局部极小值。根据新图对编码代价的影响，及时判断出社区结构的变化。并在实际数据集上验证了GSCM的有效性。
　　而后基于谱聚类提出GSCM-SC算法，并对其性能瓶颈进行并行化提出并行图序列社区挖掘算法PGSCM。利用相似度矩阵数据点间的独立性对其并行化；利用Lanczos方法解决图拉普拉斯矩阵特征向量计算的并行化；利用K-Means计算数据点与聚类中心距离及迭代的独立性对其并行化。并用多台虚拟机构成机器集群来搭建Hadoop平台，验证算法在真实数据集上的有效性及其性能提升。
　　最后，初步探索了图序列社区挖掘灰度方面的问题，为今后提供了很好的研究方向。

目录

封面

声明

中文摘要

英文摘要

目录

图表清单

算法清单

符号表和缩略词清单

第一章 绪论

1.1本课题研究背景

1.2本课题研究现状

1.3本文的主要工作及创新点

1.4本文各章内容安排

第二章 基于编码代价的图序列社区挖掘

2.1引言

2.2算法的主要思想

2.3图序列社区挖掘的符号描述

2.4 图序列编码代价函数

2.5基于编码代价的图序列社区挖掘算法GSCM

2.6实验及分析

2.7本章小结

第三章 MAPREDUCE并行计算技术

3.1 MAPREDUCE简介

3.2 MAPREDUCE执行框架

3.3 Hadoop并行计算

3.4 本章小结

第四章 并行化的图序列社区挖掘

4.1 引言

4.2 谱聚类

4.3并行图序列社区挖掘算法PGSCM

4.4 实验及分析

4.5 本章小结

第五章 灰度图序列初步探索

5.1灰度性质

5.2实验及分析

5.3

第六章 总结与展望

6.1 已有工作总结

6.2 未来工作展望

参考文献

致谢

硕士研究生期间完成的学术论文