分布式环境下图坚韧度的计算

分布式环境下图坚韧度的计算

ID:34178900

大小:3.52 MB

页数:66页

时间:2019-03-04

分布式环境下图坚韧度的计算_第1页
分布式环境下图坚韧度的计算_第2页
分布式环境下图坚韧度的计算_第3页
分布式环境下图坚韧度的计算_第4页
分布式环境下图坚韧度的计算_第5页
资源描述:

《分布式环境下图坚韧度的计算》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库

1、硕士学位论文分布式环境下图坚韧度的计算GRAPHTOUGHNESSCOMPUTATIONINDISTRIBUTEDENVIRONMENT任强哈尔滨工业大学2015年6月国内图书分类号:TP315学校代码:10213国际图书分类号:004.4密级:公开工程硕士学位论文分布式环境下图坚韧度的计算硕士研究生:任强导师:李建中教授申请学位:工程硕士学科:计算机技术所在单位:计算机科学与技术学院答辩日期:2015年6月授予学位单位:哈尔滨工业大学ClassifiedIndex:TP315U.D.C:004.4DissertationfortheMasterDegreei

2、nEngineeringGRAPHTOUGHNESSCOMPUTATIONINDISTRIBUTEDENVIRONMENTCandidate:RenQiangSupervisor:LiJianzhongAcademicDegreeAppliedfor:MasterofEngineeringSpeciality:ComputerTechnologyAffiliation:ComputerScienceandTechnologyDateofDefence:June,2015Degree-Conferring-Institution:HarbinInstituteo

3、fTechnology哈尔滨工业大学工程硕士学位论文摘要随着社交网络等应用的飞速发展,图结构数据的理论研究,尤其是大规模图数据在分布式环境计算变得十分必要。图处理作为大数据处理领域的一个分支,形成了独有的特色:包括较差的局部性,I/O操作频繁,难以并行化,大规模的中间结果等等。图坚韧度是表示图结构稳定性的图因子,与图顶点连通度和图边连通度相比,坚韧度可以提供更多关于图的稳定程度的信息。给定任意正实数k,判断一个图是否是k-坚韧的是coNP-完全问题。尽管它的计算是困难的,图坚韧度的概念在交通网络分析,社交网络分析等问题中仍起着重要作用。本文研究了分布式环境下图

4、坚韧度的近似计算问题,结合图坚韧度与图的拉普拉斯特征值的关系,给出了计算图坚韧度的下界的LowerLap算法。我们设计了图坚韧度求解的分布式近似算法:基于广度优先搜索的算法BFS-T和基于拼接短随机游走PageRank的PageRank-T算法。我们基于Spark分布式计算平台RDD和GraphX通用图数据处理框架,利用道路交通网络数据和人工合成图数据评测了图坚韧度在交通网络分析和复杂网络分析中的效果,验证了上述算法的有效性。此外,我们设计和实现了资源监测优化系统,通过调整图数据划分,初始点选择,分析系统瓶颈,进一步提升了图坚韧度的计算效率。关键词:分布式计算

5、;图坚韧度;Spark;-I-哈尔滨工业大学工程硕士学位论文AbstractAstherapiddevelopmentofsocialnetworkapplications,researchonlargescalegraphdataprocessingisbecomingmoreandmoreessential.Largescalegraphprocessinghasitsownfeatures,includingweaklocality,frequentI/Ooperations,hardtoparallize,verylargescaleintermedi

6、ateresults,etc.ToughnessisagraphfactorintroducedbyChavtalin1973,denotingthestructuralstabilityofagraph.Comparedwithgraphvertexconnectivityandgraphedgeconnectivity,graphtoughnesscanprovidemoreinformationongraphstructuralstability.Foranyfixedpositiverationalk,itiscoNP-completetodecide

7、whetheragraphisk-tough.Despiteitscomputationalhardness,graphtoughnessfactorplaysanimportantroleintrafficnetworkanalysisandsocialnetworkanalysis.Weinvestigateintodistributedapproximategraphtoughnesscomputingandwedesignatoughnesslowerboundalgorithm:LowerLap,usinggraphLaplacianeigenval

8、ues.Wedesigntwoappr

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。