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

周廣露

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

關(guān)鍵詞：不確定性； 不確定圖； 最小割； 最大流

中圖分類號：TP311.13 文獻(xiàn)標(biāo)識碼：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引言

隨著生物信息學(xué)、社會科學(xué)、互聯(lián)網(wǎng)及無線通信技術(shù)的發(fā)展，不確定圖上進(jìn)行挖掘已獲得了更多的關(guān)注與重視。據(jù)已有研究可知，在不確定圖上對割問題的研究目前仍未真正涉及，而在確定圖上對割問題的研究則已較為完善，但是大多數(shù)是在流基礎(chǔ)上所開展的研究，并且主要針對的是全局和兩點(diǎn)之間求割。其中一方面，全局求割有確定性算法和隨機(jī)性算法，更具體來說，確定性算法主要是stoerwagner最小割算法[1]，而隨機(jī)算法中，Monte-Carlo 算法占了相當(dāng)?shù)谋壤琄arger–Stein算法更是典型代表[2]。在另一方面，兩點(diǎn)之間割集可概述為：去掉兩點(diǎn)之間的若干邊兩點(diǎn)不連通，而去掉這些邊的真子集仍舊連通。目前的兩點(diǎn)算法建立在流的基礎(chǔ)上來求取割集，特別是基于最大流-最小割理論[3]可明確證得最大流和最小割是對偶問題的邏輯結(jié)論?；谝陨涎芯砍晒瑫r下對于不確定圖的研究則主要集中在不確定圖的頻繁子圖挖掘、近鄰問題、相似度定義、最短路徑、以及可達(dá)性問題等方面，而且對于不確定上的問題研究一般至少也都是NP問題。

6結(jié)束語

本文研究了不確定圖上最大最小割概率問題，并且通過證明可知該問題是Np-Hard，因而采取了最大流分支方法?；谠搯栴}的Np-Hard特性，具體算法表現(xiàn)出一定的局限性，為此將采用近似算法擬獲得更高效率，而根據(jù)引理3和定理3則可切實(shí)推得近似算法的有效性，隨后開展的實(shí)驗(yàn)測試更進(jìn)一步驗(yàn)證了本文算法的有效性和正確性。

參考文獻(xiàn)：

[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，F(xiàn)ULKERSON 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.