论文部分内容阅读
近年来,在多种科学领域,大量数据都可以转化为不确定图,例如:社会网络、蛋白质交互网络等。通过不确定图,可以形象地看到信息间的结构关系,也可以从节点获得数据信息。如何从现有的图数据结构中挖掘出对象的结构特征、整体趋势、模式等知识,是一个有实际意义和学术价值的问题。在不确定图数据挖掘领域中,已经有了初步研究,包括频繁子图挖掘、最大团挖掘、近邻挖掘、最短路径、可达性等等,但是对于不确定图的探索才刚刚开始,还有很多问题需要研究。本文的最大流问题,就是在不确定图的基础上,引出的新问题。本文提出了不确定图上的两个新问题:最大最大流概率和最大概率最大流。1)对于最大最大流概率,本文提出了基于蕴含子图空间分解计算模型的MMFP精确算法,并且给出了优化算法,同时也证明了该问题是#P-Hard的;然后基于切诺夫边界提出了采样近似算法,同时证明近该算法是无偏估计的。最后通过实验对MMFP算法进行时间比较,和对近似算法进行误差分析。2)对于最大概率最大流,本文提出了基于最大流空间分解计算模型的MPMF精确算法,使用子图同构和割点进行优化,同时指出该问题是NP-C的;然后根据影响结果的两个因素(结构和边概率)提出了三种近似算法:结构贪心算法、概率贪心算法、综合贪心算法。最后通过实验对MPMF算法进行时间比较,和对近似算法进行时间和误差分析。