不确定图最小割边问题研究

周广露

摘要：近年来，在多种领域中产生的大量数据都可以自然地建模为图结构，比如蛋白质交互网络、社会网络等.测量手段的不准确性以及数据本身的性质导致不确定性在很多图数据中普遍存在。文中研究的是不确定图中最小割问题，也就是说：在不确定图中，由于数据的不确定性，当某边或者某顶点去掉时，可能造成最小割变化，而通常最为关心的则是这个最小割的最大值在不确定图中的概率是多少。

关键词：不确定性； 不确定图； 最小割； 最大流

中图分类号：TP311.13 文献标识码：A文章编号：2095-2163（2014）04-0078-03

Abstract：In recent years， large amounts of data generated in the various fields can be modeled as a graph structure naturally， such as protein interaction networks， social networks. Means of measurement inaccuracy and the nature of the data itself， lead to uncertainty prevalent in many chart data. This paper studies the problem that is uncertain minimum cut problem， that is to say： in the uncertain figure， due to the uncertainty of the data， when one side or one vertex removed， minimal cut may be changed， and what is cared about is the maximum the minimum cut probability.

Key words：Uncertainty； Uncertain Graph； Minimum Cut； Maximum Flow

0引言

随着生物信息学、社会科学、互联网及无线通信技术的发展，不确定图上进行挖掘已获得了更多的关注与重视。据已有研究可知，在不确定图上对割问题的研究目前仍未真正涉及，而在确定图上对割问题的研究则已较为完善，但是大多数是在流基础上所开展的研究，并且主要针对的是全局和两点之间求割。其中一方面，全局求割有确定性算法和随机性算法，更具体来说，确定性算法主要是stoerwagner最小割算法[1]，而随机算法中，Monte-Carlo 算法占了相当的比例，Karger–Stein算法更是典型代表[2]。在另一方面，两点之间割集可概述为：去掉两点之间的若干边两点不连通，而去掉这些边的真子集仍旧连通。目前的两点算法建立在流的基础上来求取割集，特别是基于最大流-最小割理论[3]可明确证得最大流和最小割是对偶问题的逻辑结论。基于以上研究成果，时下对于不确定图的研究则主要集中在不确定图的频繁子图挖掘、近邻问题、相似度定义、最短路径、以及可达性问题等方面，而且对于不确定上的问题研究一般至少也都是NP问题。

6结束语

本文研究了不确定图上最大最小割概率问题，并且通过证明可知该问题是Np-Hard，因而采取了最大流分支方法。基于该问题的Np-Hard特性，具体算法表现出一定的局限性，为此将采用近似算法拟获得更高效率，而根据引理3和定理3则可切实推得近似算法的有效性，随后开展的实验测试更进一步验证了本文算法的有效性和正确性。

参考文献：

[1]STORE M， WAGNER F. A simple min-cut algorithm[C]//ACM， 1994：141–147.

[2]KARGER， DAVID. Global min-cuts in RNC and other ramifications of a simple mincut algorithm[C]//ACM-SIAM，1982： 96-107.

[3]FORD，FULKERSON D R. Maximal flow through a network[C]//CJM ，1956：1077-1096.

[4]LI， ZOU，GAO. Mining frequent subgraphs over uncertain graph databases under probabilistic semantics[J].VLDB Journal， 2012：753–777.

[5]HANS L， Bo d laender，WOLLE T. A note on the complexity of network reliability problems[C]// IEEE，2012：1971-1984.

[6]POTAMIAS M， BONCHI F， GIONIS A，et al .k-nearest neighbors in uncertain graphs[C]// VLDB，2010.