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

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

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