不确定图上的最大流研究

《不确定图上的最大流研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文不确定图上的最大流研究RESEARCHONTHEMAXFLOWOFTHEUNCERTAINGRAPH周广露哈尔滨工业大学2014年7月万方数据国内图书分类号：TP301.6学校代码：10213国际图书分类号：004.4密级：公开工学硕士学位论文不确定图上的最大流研究硕士研究生：周广露导师：李建中申请学位：工学硕士学科：计算机科学与技术所在单位：计算机科学与技术学院答辩日期：2014年7月授予学位单位：哈尔滨工业大学万方数据ClassifiedIndex:TP301.6U.D.C:004.4DissertationfortheMasterDeg

2、reeinEngineeringRESEARCHONTHEMAXFLOWOFTHEUNCERTAINGRAPHCandidate：ZhouGuangluSupervisor：LiJianzhongAcademicDegreeAppliedfor：MasterofEngineeringSpeciality：ComputerScienceandTechnologyAffiliation：SchoolofComputerScienceandTechnologyDateofDefence：July,2014Degree-Conferring-Institutio

3、n：HarbinInstituteofTechnology万方数据万方数据哈尔滨工业大学工学硕士学位论文摘要近年来，在多种科学领域，大量数据都可以转化为不确定图，例如：社会网络、蛋白质交互网络等。通过不确定图，可以形象地看到信息间的结构关系，也可以从节点获得数据信息。如何从现有的图数据结构中挖掘出对象的结构特征、整体趋势、模式等知识，是一个有实际意义和学术价值的问题。在不确定图数据挖掘领域中，已经有了初步研究，包括频繁子图挖掘、最大团挖掘、近邻挖掘、最短路径、可达性等等，但是对于不确定图的探索才刚刚开始，还有很多问题需要研究。本文的最大流问题，就是在不确

4、定图的基础上，引出的新问题。本文提出了不确定图上的两个新问题：最大最大流概率和最大概率最大流。1）对于最大最大流概率，本文提出了基于蕴含子图空间分解计算模型的MMFP精确算法，并且给出了优化算法，同时也证明了该问题是#P-Hard的；然后基于切诺夫边界提出了采样近似算法，同时证明近该算法是无偏估计的。最后通过实验对MMFP算法进行时间比较，和对近似算法进行误差分析。2）对于最大概率最大流，本文提出了基于最大流空间分解计算模型的MPMF精确算法，使用子图同构和割点进行优化，同时指出该问题是NP-C的；然后根据影响结果的两个因素（结构和边概率）提出了三种近似

5、算法：结构贪心算法、概率贪心算法、综合贪心算法。最后通过实验对MPMF算法进行时间比较，和对近似算法进行时间和误差分析。关键词：不确定图；最大流；计算复杂度；补充流；满流概率-I-万方数据哈尔滨工业大学工学硕士学位论文AbstractRecently,inmanyvariousscientificfields,largeamountsofdatacanbeconvertedintouncertaingraph,eg:socialnetworks,proteininteractionnetworks.Wecanseethestructuralrelatio

6、nshipoftheinformation,getinformationfromtheuncertaingraph.Howtominethestructurefeatures,thetrends,patternsfromthegraphisthepracticalandacademicproblem.Somestudieshavebeendone,includingfrequentsubgraphmining,maximumcliqueproblem,neighborsmining,shortestpath,accessibilityinuncertai

7、ngraph.Therearemanyissuesoftheuncertaingraphtostudysuchasthemaximumflowprobleminthispaper.Thispaperproposestwonewissuesoftheuncertaingraph:maximummaximumflowprobabilityandthemaximumprobabilitymaximumflow.1)Forthemaximummaximumflowprobability，thispaperproposesMMFPbasedonspacedecom

8、positionofsubgraph,andgivestheoptimizati