基于复杂网络的网络大数据聚类应用研究

摘要

本文以网络大数据为研究对象，分析大数据的特性，得出复杂网络是网络大数据的重要组成形式，而复杂网络中社区结构的发现与聚类算法具备天然的相似性。因此本文即运用复杂网络的方法来解决网络大数据的聚类问题。
　　本文通过分析网络大数据的特性得出网络大数据所形成的复杂网络节点数较多，规模较大，并且网络大数据的聚类对是时间要求较高，所以全局发现算法不适合于网络大数据的聚类。因此本文从局部发现的角度出发来进行网络大数据的聚类研究。提出了基于局部关键节点的大数据聚类算法。首先，引入局部关键节点的思想，结合全局关键节点的发现方法，提出了局部关键节点的发现方法。然后，将局部关键节点与其邻居节点组成初始社区，并用推导后的适应度公式向外进行扩张得到最终社区。然后分析大数据集的特性，得出在大数据集中往往一个社区内有多个关键节点，因此，从局部关键节点根据适应度公式向外逐个节点的扩张就可能导致其他的关键节点被排除在外，并且关键节点与其邻居节点组成初始社区就有可能将相邻社区的节点加入进来导致聚类结果质量下降。针对这两点不足，提出了基于局部关键社区的大数据聚类算法，通过引入极大团的概念和进一步对适应度公式进行改进来提高聚类结果质量。首先，分析极大团的特性，得出极大团是社区内联系最紧密的一组节点。所以由此可以判定，极大团的所有节点都在一个社区内，一个社区内规模最大的极大团则是这个社区内最大团即是这个社区的最核心的类别，也是整个社区的极大类。因此，可以将局部关键节点的发现方法和极大团的发现方法相结合来发现局部关键社区。这样可以将数据集分为局部关键社区和普通节点两个部分。由于原适应度公式只能适合单一节点向外扩张，而现在需要将较小的关键社区加入到社区中，因此对适应度函数进行改进。然后，以规模最大的局部关键社区为初始社区运用改进后的适应度公式向外扩张得到最终社区。最后在真实数据集上进行检验，证明算法具有可行性并且能减少时间消耗。接着分析所提出算法的组成部分，提出对应部分的并行策略和总体算法的并行策略，并在真实数据集上进行验证。结果证明提出的并行策略在不影响结果质量的前提下有效减少时间消耗，在大规模的数据集上尤为明显，并与并行线程数成正比。说明提出的并行策略适用于网络大数据的聚类。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 研究背景和意义

1.2 大数据的特征和构成

1.3 国内外动态

1.4 论文主要研究内容

1.5 论文组织结构

2 基于局部关键节点的大数据聚类算法

2.1 局部关键节点的发现

2.2 适应度函数的改进

2.3 基于局部关键节点的大数据聚类算法具体算法步骤

2.4 算法复杂度的分析

2.5 社区评价函数

2.6 实验分析

3 基于局部关键社区的大数据聚类算法

3.1 局部关键社区的发现

3.2 局部社区发现

3.3 基于局部关键社区的大数据聚类算法具体算法步骤

3.4 算法复杂度的分析

3.5 实验分析

4 基于局部关键社区的大数据聚类算法的并行研究

4.1 极大团的并行发现

4.2 关键社区的并行策略

4.3 局部社区发现的并行策略

4.4 总算法的并行策略

4.5 并行算法复杂度的分析

4.6 实验分析

结论

致谢

参考文献

攻读学位期间的研究成果