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

发布时间：2017-12-29 07:27

  本文关键词：基于通信负载均衡的社交网络图分割算法研究与实现　出处：《太原理工大学》2017年硕士论文　论文类型：学位论文

  更多相关文章： 社交网络 图论 图分割 分布式计算 负载均衡

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

【参考文献】

相关期刊论文 前6条

1 唐德权;吴绍兵;凌志刚;;一种新的图聚类算法研究[J];计算机应用与软件;2014年06期

2 吴信东;李毅;李磊;;在线社交网络影响力分析[J];计算机学报;2014年04期

3 周爽;鲍玉斌;王志刚;冷芳玲;于戈;邓超;郭磊涛;;BHP:面向BSP模型的负载均衡Hash图数据划分[J];计算机科学与探索;2014年01期

4 王浩成;马静;;高效的大型图聚类方法研究[J];小型微型计算机系统;2013年06期

5 于戈;谷峪;鲍玉斌;王志刚;;云计算环境下的大规模图数据处理技术[J];计算机学报;2011年10期

6 马永刚;谭国真;杨际祥;潘东;;一种改进的并行计算图划分模型[J];小型微型计算机系统;2011年03期

，

本文编号：1349326