不確定圖最小割邊問題研究

周廣露

摘要：近年來，在多種領域中產生的大量數據都可以自然地建模為圖結構，比如蛋白質交互網絡、社會網絡等.測量手段的不準確性以及數據本身的性質導致不確定性在很多圖數據中普遍存在。文中研究的是不確定圖中最小割問題，也就是說：在不確定圖中，由于數據的不確定性，當某邊或者某頂點去掉時，可能造成最小割變化，而通常最為關心的則是這個最小割的最大值在不確定圖中的概率是多少。

關鍵詞：不確定性； 不確定圖； 最小割； 最大流

中圖分類號：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.