大数据平台下基于图划分的最大团问题求解方法研究

摘要

最大团问题作为图论中经典的组合优化问题，属于NP完全问题，即搜索无向图中规模最大的完全子图。最大团问题的应用范围十分广泛，如模式识别、人工智能、子图同构等等。在社会网络分析中，可通过搜索社会网络中的最大团进一步挖掘社会网络中的用户行为特征和社团结构。因此，求解最大团问题在理论研究和实际应用中都具有重要的意义。
　　随着问题研究的深入以及图规模的指数级增长，确定性算法的求解时间过长，使得启发式算法逐渐成为求解最大团问题的主流算法，并取得了一些研究成果，但仍存在通用性差、求解效率低等问题。大数据领域下图中节点的海量性和分析的复杂性，对最大团问题的研究在速度和精度上都提出了更高的要求，传统的启发式算法已无法满足针对大规模图数据求解最大团问题的研究需求。为此，本文提出一种新的基于Hadoop的并行图划分框架PPMC求解大规模图例的最大团问题。
　　本文的主要研究工作和创新点包括以下三部分：
　　1）在突破局部搜索算法BLS的基础上进行改进，增加基于惩罚值的penalty_BLS子算法，提出一种新的分阶段PBLS算法求解最大团问题，有效的提高算法的通用性和求解效率。
　　2）提出一种新的PGP并行图划分算法对大规模图例的搜索空间进行划分，在保持原有的团结构不变的情况下，利用节点度排序大幅度减小子图的规模，并且保证子图规模在合适的范围内，以平衡求解最大团时的任务负载。
　　3）将PGP并行图划分算法与分阶段PBLS算法相结合形成一种新的基于Hadoop的并行图划分框架PPMC求解最大团问题，首先利用MapReduce编程模型对图文本进行处理，采用PGP并行图划分算法对最大团问题的搜索空间进行划分，选取分阶段PBLS算法求解各个子图的最大团，最终求得整个图例的最大团。
　　最后，本文将提出的基于Hadoop的并行图划分框架PPMC部署到Hadoop分布式云计算平台上，采用Stanford大规模数据集运行测试，实验结果表明PPMC框架能有效求解大规模图例的最大团问题，在降低搜索的时间和空间复杂度同时进一步提高算法的通用性和可扩展性。

目录

声明

第一章 绪论

1.1 课题研究的背景及意义

1.2 研究现状

1.3 论文结构安排

第二章 最大团问题与启发式算法

2.1 最大团问题

2.2 解决最大团问题的蚂蚁算法和遗传算法

2.3 一种新的分阶段PBLS算法求解最大团问题

2.4 实验结果与分析

2.5 本章小结

第三章 图的划分

3.1 图划分问题

3.2 One_Depth图划分策略

3.3 一种新的并行图划分策略PGP

3.4 实验结果与分析

3.5 本章小结

第四章 基于Hadoop的PPMC框架求解最大团问题

4.1 Hadoop大数据计算平台

4.2 基于Hadoop的PPMC框架

4.3 实验结果与分析

4.4 本章小结

第五章 总结与展望

5.1 本文的总结

5.2 工作展望

参考文献

致谢