基于多层次划分的大规模动态图分割方法研究

《基于多层次划分的大规模动态图分割方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：单位代码：１０１４０密级：公开学号：４０３１５３１９２３遵Ａ聲ＬＩＡＯＮＩＮＧＵＮＩＶＥＲＳＩＴＹ硕士学位论文ＴＨＥＳＩＳＦＯＲＭＡＳＴＥＲＤＥＧＲＥＥ基于多层次划分的大规模动态图论文题目：分害］方治研究ＲｅｓｅａｒｃｈｏｎｉｔｉＬ－ＳｃａｌｅＤｎａｍｉｃＰａｒｔｏｎＭｅｔｈｏｄｓｏｎａｒｇｅｙ－ＧｒａｈＢａｓｅｄｏｎＭｕｌｔｉＬｅｖｅｌＤｉｖｉｓｉｏｎ英文题目：ｐ论文作者：张梦琳指导教师：宋宝燕教授专工程业：软件二○一八年五月完成时间：辽宁大学学位论文原创性声明本人

2、郑重声明：所呈交的学位论文是本人在导师的指导下独立完成的。论文中取得的研究成果除加以标注的内容外，不包含其他个人或集体已经发表或撰写过的研究成果，不包含本人为获得其他学位而使用过的成果。对本文的研究做出重要贡献的个人和集体均已在文中进行了标注，并表示谢意。本人完全意识到本声明的法律结果由本人承担。ｊ学位论文作者签名：办从年Ｉ月３＾学位论文版权使用授权书本学位论文作者完全了解学校有关保留，、使用学位论文的规定同意学校保留并向国家有关部门或机构送交学位论文的原件、复印件和电子版，允许学位论文被查阅和借阅。本人授权辽宁大学可以

3、将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编学位论文。同时授权中国学术期刊（光盘版）电子杂志社将本学位论文收录到《中国博士学位论文全文数据库》和《中国优秀硕士学位论文全文数据库》并通过网络向社会？公众提供信息服务。学校须按照授权对学位论文进行管理，不得超越授权对学位论文进行任意处理。保密（）。（：，在年后解密适用本授权书保密请在括号内＿‘Ｗ”划）授权人签各＾樣日期：和曰日期：年龙月曰丨Ｓ年Ｘ月ｆｆ申请辽宁大学硕士学位论文基于多层次划分的大规模动态图分割方法研究R

4、esearchonPartitionMethodsonLarge-ScaleDynamicGraphBasedonMulti-LevelDivision作者：张梦琳指导教师：宋宝燕教授专业：软件工程答辩日期：2018年5月22日二○一八年五月·中国辽宁摘要摘要图结构因其能较为准确地表示现实世界中实体间的关系，而被广泛应用于社交网络、生物信息网络、智能交通网等众多领域。随着信息技术的飞速发展，图数据规模日益增大，分布式并行计算成为解决大规模图数据处理的有效方法，而应用分布式并行计算的前提是快速有效地将图分割并分配到若干台计算机中，并尽可能保证负载平衡，避免因较大偏

5、差造成存储空间的浪费。同时，现实应用中，图常随时间而动态变化，如何对大规模动态图进行有效地分割成为处理图数据的关键，因而成为当前图数据处理技术的研究热点之一。本文针对当前图分割问题进行了深入研究，发现在当前数据增长的规模与速度背景下，现实应用对图分割效率、分割结果优劣以及分割中的冗余存储等方面提出了更高的要求，现有的图分割方法已无法有效地解决大规模动态图的分割问题。针对上述问题，本文根据相邻两时刻，图的分区结构具有一定相似性的短暂平滑效应，将动态图分割问题分为两个阶段进行解决。首先针对初始图的静态结构，基于分层划分思想框架，针对初始分割阶段提出了一种利用部分节点

6、交换的算法来进行划分，以尽可能保证负载均衡，即MPA-S方法。其次针对动态图结构，为避免重新分割造成的巨大开销，本文提出一种有向性动态维护策略，即MPA-D方法，该方法以时间片T为单位，收集T时间片内图的动态变化，并通过判断这些变化是否涉及边界节点而给出不同的逻辑移动策略；同时提出一种有向动态优化算法将逻辑移动策略结果进行调整以适应收集到的图节点或边的变化。最后，真实数据集上的大量实验验证，本文提出的MPA方法通过压缩和还原，在一定程度上有效解决大规模图的分割问题，尽可能保证各计算节点的负载平衡，并减少因计算过程的冗余存储造成的存储空间浪费问题，且最终的分割结果

7、质量也有所提高。关键词：动态图，图分割，多层次划分，分布式并行计算，负载均衡IAbstractABSTRACTThegraphstructureiswidelyusedinmanyfieldssuchassocialnetwork,biologicalinformationnetworkandintelligenttransportationnetwork,etc.becauseitcanrepresenttherelationshipamongentitiesintherealworldaccurately.Withtherapiddevelopmentofi

8、nformationte