張安珍 李建中

摘要：很多領域產(chǎn)生的大量數(shù)據(jù)都可以很自然地用不確定圖模型表示和描述，如蛋白質交互網(wǎng)絡、社交網(wǎng)絡、無線傳感器網(wǎng)絡等。本文研究不確定圖上最可靠的最小生成樹問題，該問題具有廣泛的應用價值和研究意義。精確地求解算法需要枚舉所有可能的最小生成樹并找出其中出現(xiàn)次數(shù)最多的那個。因此，枚舉開銷隨著邊數(shù)增多呈指數(shù)增長，當圖規(guī)模較大時并不可行。為此本文提出了一個時間復雜度為O（d |V|²）的啟發(fā)式貪心算法，其中d為最大的頂點度數(shù)，|V|為頂點數(shù)。實驗結果表明，該算法具有較好的效率和較高擴展性。

關鍵詞：不確定圖：最可靠最小生成樹：貪心算法

0引言

近年來，很多領域產(chǎn)生的大量數(shù)據(jù)可以利用圖模型表示。由于測量數(shù)據(jù)的工具不精確、數(shù)據(jù)本身性質等多方面原因導致圖數(shù)據(jù)普遍存在不確定性，如蛋白質交互網(wǎng)絡（PPI）、社交網(wǎng)絡、無線傳感器網(wǎng)絡等，將不確定性融入到圖中得到不確定圖。

確定圖上的最小生成樹問題具有十分重要的實際意義。在連通圖G=（v.E）中，E中每條邊有對應的權值，圖G的一棵生成樹是連接V中所有頂點的一棵樹，生成樹中所有邊的權值總和稱為生成樹的代價，使這個代價最小的生成樹稱為圖G的最小生成樹（Minimum Spanning Tree.MST）。很多實際應用問題可以通過求解最小生成樹得到很好的解決。例如，道路規(guī)劃問題，可將各個城鎮(zhèn)作為圖的頂點，城鎮(zhèn)之間的道路作為邊，每條道路的修建代價作為邊上的權值，在該圖上求最小生成樹可以得到修建代價最少的修路方案。如，在無線傳感器網(wǎng)絡中，由于傳感器節(jié)點間的通信鏈路存在一定的干擾，每條鏈路存在一定的失效風險，因此其拓撲結構可以很自然地建模為不確定圖。頂點表示各傳感器節(jié)點，邊表示可能存在的通信鏈路，邊的權值由距離決定，邊的存在概率表示該鏈路正常工作的可能性大小。在該圖上求解最可靠的最小生成樹非常重要，其上的邊集即鏈路集合是最穩(wěn)定可靠的連通路徑，利用該生成樹可以優(yōu)化路由選路過程，用最少的代價完成全部節(jié)點間通信的同時，保證了網(wǎng)絡通信的可靠性與穩(wěn)定性。

不確定圖是邊帶有概率的特殊加權圖，邊的概率表示該邊存在的可能性大小。因此不確定圖有多種可能的存在形式，每一個存在形式稱為蘊含子圖，蘊含子圖是一個以一定概率確定存在的加權圖，由此可知每個連通的蘊含子圖上都有至少一棵最小生成樹，這些最小生成樹構成了不確定圖的最小生成樹集合。

本文研究不確定圖上最可靠的最小生成樹問

1問題定義

本節(jié)介紹一種不確定圖模型，并形式化描述不確定圖上的最可靠的最小生成樹問題。

1.1不確定圖模型

不確定圖是一個四元組G=（v.e.p.W），其中V是頂點集，E為邊集，P是邊的存在概率函數(shù)，即E到（0.1]的映射，P（e）表示邊e存在的概率，W為權重函數(shù)，定義了每條邊的權值大小。由于邊的不確定性導致不確定圖具有多種存在形式，每種確定的存在形式稱之為蘊含子圖，也稱為可能世界。所有的蘊含子圖構成不確定圖所蘊含的確定圖集合，記為Imp（G）。對于g∈Imp（G），稱之為G蘊含g.記作C→g.假定所有邊相互獨立，蘊含概率P（G→g）等于所有g中的邊的存在概率與不在g中的邊不存在概率之積，如公式（1）所示。

下面通過一個簡單的例子來說明蘊含子圖及其存在概率的含義。

例1如圖1（a）所示，圖G是包含3個頂點和3條邊的不確定圖，每條邊存在與否決定了圖G共有2³=8個蘊含子圖，每個子圖的存在概率由公式（1）計算得到。以圖1（b）中的子圖g²為例，P（C→g²）=0.4×（1-0.9）×（1-0.7）=0.012.其它子圖的存在概率計算與之類似，結果如圖1（b）所示。

1.2 最可靠的最小生成樹

下面通過例2求圖1（a）中不確定圖G上的MST_max來說明公式（3）的含義。

MST_max是最小生成樹集合中存在概率最大的那棵，即MST₃，MST_max={Ac，BC}，P（MST_max）=P（MST₃）=0.378，利用|MST|表示最小生成樹的代價，則|MST_max|=|MST₃|=7。

由MST_max的定義可知，一種直觀的求解算法是枚舉所有蘊含子圖g.并在g上求最小生成樹得到一個最小生成樹集合，求集合中存在概率最大的最小生成樹，然而該算法在實踐上并不可行，圖G共有2^|E|，個蘊含子圖，枚舉代價隨邊數(shù)增多呈指數(shù)增長，當圖規(guī)模較大時，算法效率十分不理想。因此本文提出一種啟發(fā)式的貪心算法近似求解MST_max，時間復雜度為0（d²|V|²），相對于枚舉法性能大大提高，實驗結果表明該算法在通常情況下能夠得到MST_max。

2貪心算法求最可靠最小生成樹

啟發(fā)式貪心策略近似求解不確定圖上最可靠的最小生成樹，在2.1節(jié)給出算法的詳細描述，而后在

2.2節(jié)分析貪心算法的運行時間。

2.1 算法描述

給定連通不確定圖G=（v.e.p.W），求解其上MST_max的算法思想與Prim算法求解確定圖上最小生成樹類似，維持一棵樹a.樹A從任意根頂點r開始形成，并逐漸生成，直至樹A覆蓋了V中的所有頂點，每一次，一條連接樹A與G_A=（v.A）中某孤立頂點的概率最大的輕邊被加入到樹A中，其中輕邊是指權值最小的邊，下面給出概率最大輕邊的定義。

定義1概率最大的輕邊（Light Edge withMaximum Probability.LEMP），將所有連接樹A與森林G_A=（v.A）中某孤立頂點的邊加入隊列S中，按公式（4）計算其加入到樹A中的概率，其中概率值最大的邊即為LEMP。

將隊列S中的邊按權值非降序排列，p_i表示位于排序隊列中第i條邊的存在概率，l≤i≤|S|，則第i條邊作為概率最大的輕邊（LEMP）加入到樹A中的概率P;為：

其中，n_i表示隊列中所有與第i條邊權值相等，但位置排在其前面的邊的個數(shù)，O≤n;≤i-1。下面舉例說明公式（4）。

例3假設G中所有與A中頂點直接相連但不在A中的邊有{e₁，e₂，e₃}，將其加人隊列s.按照權值升序排列，假設w₁2=w₃，則這3條邊加入到樹A中的概率依次為：P₁，（1-P₁）·P₂，（1-P₁）·P₃。

直觀地講，e₁具有最小權重值w₁，故其作為輕邊加入樹A的概率就是其自身的存在概率p₁;對于e₂，由于其的權值w₂大于e₁的權值w₁，，所以只有在e₁不存在的情況下，e₂才能作為輕邊加入到A中，概率為e₁不存在的概率乘以e₂存在的概率，即（1-p₁）·p₂;對于e₃，由于e₃的權值w₃和e₂的權值w₂，相等，則其加入到A的概率與e₂存在與否無關，概率等于e₁不存在的概率乘以e₃存在的概率，即（1-p₁） ·p₃。

下面給出具體的算法描述，見算法1。實現(xiàn)時，采用插入排序法排序隊列s.因為每次添加新邊之前，S中已有的邊是按權值升序排列的，只需要將新加入的邊插入到已經(jīng)排好序的隊列中即可，這樣減少了全部邊重新排序的時間開銷。

算法1最可靠的最小生成樹算法，

輸入：不確定圖G=（v.e.p.W）。

輸出：最可靠的最小生成樹MST_max的邊集A

（1）MST_V={r};A=φ;S=φ

（2）將所有與r相連的邊添加到隊列S中

（3）WHILE|MST_V|<|V|DO

（4）將S中的邊按照權值升序排列

（5）按照公式（4）計算S中每條邊加入A的概率值

（6）利用最大堆H求概率最大的邊，記為（u.v）

（7）將（u.v）加入A中，將不在MST_V中的頂點

（8）假設是v.加入到MST_V中

（9）刪除S中所有與v相連的邊

（10）將G中所有與v相連但另一端的頂點不在MST_V中的邊加入到S中

（11）END WHILE

2.2算法的分析

下面分析最壞情況下算法的運行時間。將圖G中最大頂點度數(shù)記作d.1≤d≤|V-1|，第i次迭代時隊列S₁的長度記為|S₂|則有如下關系成立：

第一次迭代時，A中只有一個頂點r.將r的鄰邊加入到S₁中，最多加入d條邊;第i+1次迭代時，S_i+1中的邊由S_i去掉包含新頂點v的邊后，再并上G中v的鄰邊中另外一端不在A中的邊，其中S_i最少去掉

3實驗驗證

3.1實驗環(huán)境及實驗數(shù)據(jù)

為了驗證啟發(fā)式貪心算法的效率以及有效性，分別在合成數(shù)據(jù)集和人造數(shù)據(jù)集上進行測試。采用C^{編程，實驗環(huán)境為PC機，英特爾（R）酷睿2雙核2.4GHz CPU和2GB的主內存，運行系統(tǒng)為Ubutu 12.04。MapReduce算法在完全分布式環(huán)境下測試，Hadoop版本為2.6.0.實驗環(huán)境為3臺PC機，配置為英特爾（R）酷睿TM四核3.4GHz CPU和32GB內存。}

實驗中的合成數(shù)據(jù)集是在真實不確定圖數(shù)據(jù)上，隨機標注權值得到，權值取0-100之間的整數(shù)。使用文獻[6]提供的2個真實的不確定圖數(shù)據(jù)集，Nature是蛋白質交互網(wǎng)絡，F(xiàn)lickr是一個社交網(wǎng)絡，圖規(guī)模及連通性見表1.其中N（MST）表示MSF_max中包含的連通分支數(shù)目。

人造數(shù)據(jù)集采用隨機生成一些不確定圖，頂點之間的邊及邊上的權值和概率都隨機生成，權值取O-100之間的整數(shù)，概率取值0.00-0.99之間的兩位有效小數(shù)。在人造數(shù)據(jù)集1中，控制頂點的平均度數(shù)d相同，都為1.23.頂點大小從1k遞增到10k.每次遞增1k：在人造數(shù)據(jù)集2中，控制頂點大小一定，都為1k.平均度數(shù)取3-7.5.每次遞增0.5。人造數(shù)據(jù)集3是一個小規(guī)模圖集合，頂點大小從10遞增至50.平均度數(shù)都為3。

3.2實驗結果

貪心算法在求MST_max時，如果圖不連通，則求最可靠的最小生成森林MSF_max。具體來說，當算法求得一棵生成樹A時，若A中頂點數(shù)小于圖G的頂點數(shù)|V|，則將A加入到MSF_max中，同時隨機選取一個不在A中的頂點作為新的根節(jié)點，生成另外一棵生成樹，直至MSF_max覆蓋所有G中的全部頂點。

首先測試貪心算法在不同圖規(guī)模下的性能表現(xiàn)。在合成數(shù)據(jù)集Nature和Flickr上，逐步抽取其上的子圖進行測試，子圖大小為原圖的10%-100%，運行時間隨頂點大小的變化如圖3所示。實驗結果表明運行時間隨頂點數(shù)|V|的增加大致呈拋物線增長趨勢，與上一節(jié)分析的算法運行時間O（d²|V|²）一致，另外在Flickr數(shù)據(jù)集上，圖規(guī)模為（17273.102356）時的運行時間比圖規(guī)模為（15113.97743）反而少，這是因為（17273.102356）的平均度數(shù)d為5.9.比（15113.97743）上的平均度數(shù)6.4小，接下來測試平均頂點度數(shù)對運行時間的影響。

在人造數(shù)據(jù)集1中，頂點平均度數(shù)d一定，都為1.23.在其上運行貪心算法，測試頂點大小對運行時間的影響，結果如圖4（a）所示。在人造數(shù)據(jù)集2上，頂點大小固定，都為1k.邊的大小從3k遞增到7.5k.即頂點平均度數(shù)取3-7.5.運行結果如圖4（b）所示。

由圖4（a）分析可知，當平均頂點度數(shù)d一定時，算法的運行時間隨|V|的增大呈拋物線增長趨勢，并且期間沒有異常點出現(xiàn)。圖4（b）中的實驗結果表明，當頂點數(shù)一定時，運行時間隨平均度數(shù)d增加而呈線性增長。

若要驗證貪心算法得到的最小生成樹與精確解得到的最小生成樹是否一致，需要枚舉所有可能的最小生成樹，枚舉代價非常大，為O（2^|E|），這為驗證工作增加了很大困難，因此需要設計一個隨機算法用來對比實驗結果，

隨機算法每次向樹A中隨機添加隊列S中的一條邊，由于最小生成樹的存在概率等于每次迭代時加入A中邊的概率P累乘，當圖規(guī)模太大時，最小生成樹的概率P很小，為了方便實驗數(shù)據(jù)對比，取其對數(shù)得到logP從而將其放大，由于log函數(shù)具有單調遞增性，所以不會影響實驗對比結果。在人造數(shù)據(jù)集3小圖上進行實驗，隨機算法執(zhí)行3次，實驗結果如圖5所示。

由圖5上的結果可見，隨著頂點數(shù)增多，貪心算法求出的最小生成樹的概率比3次隨機算法求得的最小生成樹概率大很多，并且權值更小，這在很大程度上說明了貪心算法求出的MST_max是精確解的一個很好的近似。

4結束語

本文研究了不確定圖上最可靠的最小生成樹問題。最可靠的最小生成樹代表了不確定圖上最穩(wěn)定的連通分支，具有廣泛的應用價值。精確求解算法的時間開銷非常大，因此本文給出一個多項式時間的啟發(fā)式貪心算法，實驗結果表明該算法在大多數(shù)情況下能夠得到最優(yōu)解。