不確定圖最小生成樹算法

張安珍 李建中

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

關(guān)鍵詞：不確定圖：最可靠最小生成樹：貪心算法

0引言

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

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

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

本文研究不確定圖上最可靠的最小生成樹問(wèn)

1問(wèn)題定義

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

1.1不確定圖模型

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

下面通過(guò)一個(gè)簡(jiǎn)單的例子來(lái)說(shuō)明蘊(yùn)含子圖及其存在概率的含義。

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

1.2 最可靠的最小生成樹

下面通過(guò)例2求圖1（a）中不確定圖G上的MST_max來(lái)說(shuō)明公式（3）的含義。

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

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

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

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

2.2節(jié)分析貪心算法的運(yùn)行時(shí)間。

2.1 算法描述

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

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

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

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

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

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

下面給出具體的算法描述，見算法1。實(shí)現(xiàn)時(shí)，采用插入排序法排序隊(duì)列s.因?yàn)槊看翁砑有逻呏埃琒中已有的邊是按權(quán)值升序排列的，只需要將新加入的邊插入到已經(jīng)排好序的隊(duì)列中即可，這樣減少了全部邊重新排序的時(shí)間開銷。

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

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

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

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

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

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

（4）將S中的邊按照權(quán)值升序排列

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

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

（7）將（u.v）加入A中，將不在MST_V中的頂點(diǎn)

（8）假設(shè)是v.加入到MST_V中

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

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

（11）END WHILE

2.2算法的分析

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

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

3實(shí)驗(yàn)驗(yàn)證

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

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

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

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

3.2實(shí)驗(yàn)結(jié)果

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

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

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

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

若要驗(yàn)證貪心算法得到的最小生成樹與精確解得到的最小生成樹是否一致，需要枚舉所有可能的最小生成樹，枚舉代價(jià)非常大，為O（2^|E|），這為驗(yàn)證工作增加了很大困難，因此需要設(shè)計(jì)一個(gè)隨機(jī)算法用來(lái)對(duì)比實(shí)驗(yàn)結(jié)果，

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

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

4結(jié)束語(yǔ)

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