基于通信负载均衡的社交网络图分割算法研究与实现

摘要

海量社交网络数据中蕴含着丰富的信息，图论是挖掘这些信息的重要方法之一。面对日益增多的图数据，分布式计算成为处理大规模图数据的有效手段。在分布式图计算中，通信所消耗的时间占有很大的比例，通过图分割算法的设计可以有效地降低通信量并实现负载均衡，从而提高分布式图计算的效率，典型的例子包括Met is图分割算法。但是，用现有的图分割算法处理非均衡图数据会造成各个子图之间通信量不均衡，从而影响了计算效率。
　　本研究针对社交网络图数据特点进行了深入研究，并以传统图分割模型为基础，建立了实现通信负载和存储负载双重平衡的图分割模型。以通信负载均衡图分割方法为理论依据，设计并实现了通信均衡标签交换算法(Communication Balanced Lable Exchanging method)，同时为进一步减小贪婪算法模型带来的局部优化影响，使用模拟退火算法对C BLE算法进行深入优化。使用Hash方法，Metis方法与CBLE算法进行实验分析，分别在通信边数量，顶点规模均衡度，通信边分布均衡度指标对三个算法进行比较，C BLE算法整体具有明显优势。为更加有力证明本文算法在提升分布式图计算框架处理社交网络数据的效率方面的优势，最后将CBLE算法应用于Apache开源图计算框架Hama中，使用Twitter大规模社交网络数据集进行测试。其结果表明分割子图的通信负载均衡对分布式图计算框架处理社交网络数据的效率提升有一定的效果，并且随着集群资源利用率的提高，本算法的分割结果对图计算效率有10％到15%的提升。

目录

声明

第一章 绪论

1. 1 课题研究背景和意义

1. 2 研究现状

1. 3 存在问题以及本文贡献

1. 4 论文安排

第二章 大规模图分割方法

2. 1 图分割相关知识

2. 2主流算法介绍

2. 3本章小结

第三章 图分割方法建模及算法设计

3. 1 基于通信负载均衡的图分割方法建模

3. 2 算法理论求解

3. 3 通信平衡标签交换算法

3. 4 模拟退火算法应用

3. 5 本章小结

第四章 基于GraphChi平台的算法实现

4. 1 计算平台介绍

4.2 Graphchi算法设计

4. 3 C BLE算法实现

4. 4 本章小结

第五章 实验环境与结果分析

5. 1 实验设计

5. 2 评价指标

5. 3 结果分析

5. 4 本章小结

第六章 总结与展望

6. 1 工作总结

6. 2 下一步工作展望

参考文献

致谢

攻读学位期间发表的学术论文目录

论文受项目资助情况