一種改進(jìn)的分布式最大權(quán)獨(dú)立集算法

王向陽 張 源

(東南大學(xué)移動通信國家重點(diǎn)實(shí)驗室 南京 210096)

1 引言

文獻(xiàn)中已提出了幾種分布式MWIS算法[6,8]。這些算法都是基于啟發(fā)式的貪婪原則的。在文獻(xiàn)[9]中，提出了一種新型的分布式MWIS算法。該算法直接應(yīng)用了機(jī)器學(xué)習(xí)以及信道編碼領(lǐng)域的信用傳播(belief propagation)及最大乘(max-product)方法[10]，使相鄰節(jié)點(diǎn)之間不斷交換包含軟信息的消息，并且每個節(jié)點(diǎn)根據(jù)所有收到消息各自獨(dú)立判斷是否屬于最大權(quán)獨(dú)立集。如果圖是樹結(jié)構(gòu)(即不含圈)的，該算法一定可以收斂至最優(yōu)；如果圖是一般結(jié)構(gòu)(即含圈)的，則該算法被證明只有當(dāng)對應(yīng)的松弛的線性規(guī)劃的最優(yōu)解非分?jǐn)?shù)時才可以收斂至最優(yōu)。值得注意的是，該結(jié)論對圖匹配問題來說一般也是成立的[11,12]。對于該分布式MWIS算法來說，可以通過修改其中的消息計算公式進(jìn)一步提高性能。事實(shí)上，在文獻(xiàn)[9]中已經(jīng)提出了一種改進(jìn)算法。該算法利用松弛原始線性規(guī)劃的對偶規(guī)劃，首先收斂至對偶問題的最優(yōu)解，然后啟發(fā)式地映射為原問題的解。這種基于對偶的改進(jìn)算法被證明只有當(dāng)圖是二分圖時，才能收斂至最優(yōu)，仍然具有較大的局限性。

針對已有工作的不足，本文提出了一種新的改進(jìn)的分布式MWIS算法。該算法以文獻(xiàn)[9]中基于最大乘信用傳播的分布式MWIS算法的迭代運(yùn)行方式為框架，通過細(xì)致分析一般圖中最大權(quán)獨(dú)立集中元素構(gòu)成的特點(diǎn)，啟發(fā)式地提出一種新的改進(jìn)的相鄰節(jié)點(diǎn)間交換消息的計算公式以及節(jié)點(diǎn)判斷的計算公式。這些計算公式將要求所有節(jié)點(diǎn)知道自己所有鄰居節(jié)點(diǎn)之間是否有連接的信息。在該局部拓?fù)湫畔⒌膸椭?，所提出算法可以擺脫文獻(xiàn)中已有算法對圖必須是樹或者二分圖的要求，在大多數(shù)情況下都可以收斂至最優(yōu)解，具有更好的性能，并被仿真結(jié)果所驗證。

本文接下來的部分組織如下。首先，第2節(jié)描述了一般圖中的最大權(quán)獨(dú)立集問題，并介紹了基于最大乘信用傳播的分布式算法框架。第3節(jié)提出了一種新的相鄰節(jié)點(diǎn)間交換消息計算的方法以及相應(yīng)的分布式算法。第4節(jié)給出了新算法性能的仿真結(jié)果。最后，第5節(jié)對全文進(jìn)行了小結(jié)。

2 最大權(quán)獨(dú)立集問題

考慮一個一般的無向圖G=(V,E)，其中V代表所有節(jié)點(diǎn)的集合，E代表所有邊的集合。如果任意兩個節(jié)點(diǎn)i與j之間有一條邊，即(i,j)∈E，則稱這兩個節(jié)點(diǎn)是相鄰的。記N(i)為節(jié)點(diǎn)i的所有鄰居節(jié)點(diǎn)構(gòu)成的集合。每個節(jié)點(diǎn)i都被賦予一個正權(quán)重wi。任意V的一個子集都可以用變量集合x=(xi)來表示，其中xi=1表示節(jié)點(diǎn)i在該子集內(nèi)，xi=0則表示節(jié)點(diǎn)i不在該子集內(nèi)。在一個子集中，如果其中任意兩個節(jié)點(diǎn)都不是鄰居，在稱該子集為獨(dú)立子集(independent set)。本文研究如何尋找具有最大權(quán)重的獨(dú)立子集，即最大權(quán)獨(dú)立集(MWIS)。一般來說，MWIS問題可以表示為下列線性二值整數(shù)規(guī)劃問題，

接下來，將簡要介紹文獻(xiàn)[9]中的基于最大乘信用傳播的分布式MWIS算法。所謂信用傳播，是一種來自人工智能與機(jī)器學(xué)習(xí)領(lǐng)域的非?；镜耐茢喾椒?，并已在信道編解碼領(lǐng)域獲得非常成功的應(yīng)用[10]。文獻(xiàn)[9]將該方法直接應(yīng)用于解決MWIS問題，得到了相應(yīng)的分布式MWIS算法，選擇其中包含兩類消息的版本介紹如下。首先，該算法是以迭代方式運(yùn)行的，其中在每次迭代過程中，每個節(jié)點(diǎn)i都要發(fā)送兩類消息給自己的每個鄰居節(jié)點(diǎn)j∈N(i)，其計算公式為

接下來，每個節(jié)點(diǎn)i計算下列度量

傳統(tǒng)靜態(tài)地圖主要用于描述和傳遞自然和人文地理環(huán)境特征，而信息時代下的地圖已經(jīng)不再局限于表達(dá)地理環(huán)境特征、實(shí)現(xiàn)科研用途等特定的領(lǐng)域，而是進(jìn)入到了前所未有的全民位置地圖新時代.以“互聯(lián)網(wǎng)+”為代表的基于位置的服務(wù)無不都與地圖相關(guān)，如實(shí)時路線導(dǎo)航、共享單車、外賣配送等，可以說地圖的服務(wù)范圍已經(jīng)深入了到社會經(jīng)濟(jì)發(fā)展的各個部門.當(dāng)前地圖學(xué)教學(xué)和實(shí)踐內(nèi)容中仍主要以傳統(tǒng)地形圖教學(xué)為主，鮮有涉及地圖服務(wù)的最新進(jìn)展的系統(tǒng)化介紹，易造成學(xué)生所學(xué)知識用不到，用到的沒學(xué)到等現(xiàn)象.因此，在教學(xué)內(nèi)容改革中應(yīng)補(bǔ)充和更新地圖在不同領(lǐng)域最新應(yīng)用的案例學(xué)習(xí)，做好課堂理論知識與實(shí)際應(yīng)用出口的銜接，提高學(xué)生對地圖的學(xué)習(xí)興趣.

根據(jù)該度量，每個節(jié)點(diǎn)i進(jìn)行如下判斷：

其中問號代表不確定情形。

在上述算法中，所有節(jié)點(diǎn)只與相鄰節(jié)點(diǎn)交換消息，因此是分布式的。文獻(xiàn)[9]證明了該算法只有當(dāng)松弛線性規(guī)劃的最優(yōu)解非分?jǐn)?shù)時才可以收斂至最優(yōu)解。在該算法基礎(chǔ)上，文獻(xiàn)[9]提出了一種利用對偶的改進(jìn)算法，并證明了只有當(dāng)二分圖時才能收斂至最優(yōu)解，仍具有較大的局限性。

3 一種改進(jìn)的分布式算法

上節(jié)中的式(2)-式(5)中的算法只適用于樹結(jié)構(gòu)，而在一般圖中則無法保證其性能。對其中可能的原因啟發(fā)式的定性分析如下。記U(x)=∑iwixi代表系統(tǒng)總效益函數(shù)(即總權(quán)重)。考慮某節(jié)點(diǎn)i，需要自己分別計算xi=1與xi=0時U(x)的最大取值，然后計算兩者的差，稱為凈效益bi。如果凈效益大于0，則可以取xi=1，否則就只能取xi=0。這就是bi與式(5)的物理含義。為計算bi，首先需要計算xi=1時U(x)的最大值。由于采用分布式算法，節(jié)點(diǎn)i只知道xi=1以及節(jié)點(diǎn)i的所有相鄰節(jié)點(diǎn)k只能取xk=0，從而U(x)中至少包含wi項。至于其余節(jié)點(diǎn)的信息，節(jié)點(diǎn)i無法直接獲得，只能通過接收鄰居節(jié)點(diǎn)k的消息得到。記節(jié)點(diǎn)i的所有鄰居節(jié)點(diǎn)組成集合為N(i)={i(1),i(2),…,i(|N(i)|)}，其中|X|代表集合X中元素的個數(shù)。以每個節(jié)點(diǎn)i(n)為根，可以得到|N(i)|個子集Sn(i)(1≤n≤|N(i)|)，其中i(n)∈Sn(i)。由于是樹結(jié)構(gòu)，任意兩個子集Sj(i)與Sk(i)中的節(jié)點(diǎn)都不同且沒有邊相連，并且V= {i} ∪S1(i) ∪S2(i) ∪…∪S|N(i)|(i)。這樣，節(jié)點(diǎn)i的每個鄰居節(jié)點(diǎn)i(n)將負(fù)責(zé)計算當(dāng)xi(n)=0時，子集Sn(i)中獨(dú)立約束下總權(quán)重的最大值，然后報告給節(jié)點(diǎn)i使用。這就是消息qk→i的物理含義。這樣，xi=1時U(x)的最大值就等于wi+∑k∈N(i)qk→i。 接下來還要計算xi=0 時U(x)的最大值。類似地，節(jié)點(diǎn)i只知道xi=0以及節(jié)點(diǎn)i的所有相鄰節(jié)點(diǎn)k只能取xk=1。因此，每個節(jié)點(diǎn)i(n)將負(fù)責(zé)計算當(dāng)xi(n)=1時，子集Sn(i)中獨(dú)立約束下總權(quán)重的最大值，然后作為消息pk→i報告給節(jié)點(diǎn)i。這樣，xi=0 時U(x)的最大值就等于∑k∈N(i)pk→i。綜合這兩方面的計算，可以得到bi的計算公式。這就是式(4)的物理含義。至此，關(guān)鍵問題在于如何計算消息。首先考慮qk→i。在計算qk→i時要考慮下列兩方面的因素。一方面，由于xk=0，則qk→i中將不會出現(xiàn)wk項；另一方面，由于xk=0，則節(jié)點(diǎn)k的所有的相鄰節(jié)點(diǎn)j則可以取xj=1。因此，qk→i應(yīng)該等于所有相鄰節(jié)點(diǎn)j發(fā)送給自己的消息pj→k的和，即式(3)所示的計算過程。接下來考慮pk→i。類似的，由于xk=1，則pk→i中將包含wk項；另一方面，由于xk=1，則節(jié)點(diǎn)k的所有的相鄰節(jié)點(diǎn)j則只能取xj=0。因此，pk→i應(yīng)該等于wk與所有相鄰節(jié)點(diǎn)j發(fā)送給自己的消息qj→k的和，即式(2)中前一半所示的計算過程。在式(2)中的后一半計算過程則是基于下列簡單的考慮，即如果將pk→i與qk→i合并為單個消息mk→i=pk→i-qk→i并且希望該消息是非負(fù)的，即mk→i≥0，那也就要求pk→i≥qk→i，即式(2)中后一半所示的計算過程。

上述是對式(2)-式(5)物理含義的分析，從中可以得到對算法進(jìn)行改進(jìn)的線索。事實(shí)上，上述分析表明，該算法主要基于下列推斷：如果節(jié)點(diǎn)i的xi=1則節(jié)點(diǎn)i的所有相鄰節(jié)點(diǎn)k都有xk=0，反之亦然，并以之為基礎(chǔ)得到式(2)-式(4)中的計算公式。該斷言在樹結(jié)構(gòu)下顯然是正確的，但對一般圖結(jié)構(gòu)則一般是不成立的。這是導(dǎo)致該算法在一般圖中無法保證性能的主要原因。為此，本文針對該導(dǎo)致性能下降的主要原因，提出了一種新的改進(jìn)算法，以提高該類型算法在一般圖中的性能。

在算法中包括有每節(jié)點(diǎn)度量的計算與節(jié)點(diǎn)間交換消息的計算兩個部分，分別討論如下。首先是每節(jié)點(diǎn)度量bi的計算。為計算bi，首先需要計算xi=1時U(x)的最大值。由于xi=1，則U(x)中至少包含wi項。接下來考慮節(jié)點(diǎn)i的所有相鄰節(jié)點(diǎn)k。如果圖是樹，如圖1(a)所示，則只能取xk=0；如果是一般圖，由于尋找的是獨(dú)立集，該性質(zhì)仍然是成立的。因此，xi=1時U(x)的最大值就等于

接下來要計算xi=0時U(x)的最大值。由于xi=0，則U(x)中將不會出現(xiàn)wi項。接下來考慮節(jié)點(diǎn)i的所有相鄰節(jié)點(diǎn)k。如果圖是樹結(jié)構(gòu)，如圖1(a)中所示，則可以取xk=1；但如果是一般圖，則要仔細(xì)分析各種可能的情況。事實(shí)上，考慮N(i)中的某兩個節(jié)點(diǎn)l與n，如果這兩個節(jié)點(diǎn)是相鄰的，如圖1(b)中所示，則這兩個節(jié)點(diǎn)不可能同時xl=1與xn=1。因此，必須對N(i)中的所有節(jié)點(diǎn)進(jìn)行分類。假設(shè)N(i)中包含有T(i)個獨(dú)立子集Dt(i)(1≤t≤T(i))，如果xi=0，則只可能獨(dú)立子集中的節(jié)點(diǎn)取xk=1。第t個子集Dt(i)中所有節(jié)點(diǎn)的權(quán)重為∑k∈D_t(i)pk→i。記具有最大權(quán)重的子集為D*(i)，那么該子集中的節(jié)點(diǎn)都取xk=1，而非該子集中的節(jié)點(diǎn)都取xk=0。這樣，xi=1時，U(x)的最大值就等于

圖1 樹與一般圖結(jié)構(gòu)的對比

綜合這兩方面的計算，可以得到bi的計算公式為

接下來是節(jié)點(diǎn)間交換消息的計算。在節(jié)點(diǎn)間交換兩類消息pk→i與qk→i，分別討論如下。首先是消息qk→i。該消息所對應(yīng)的情況為，由于xi=1，所以必然有xk=0，則節(jié)點(diǎn)k的相鄰節(jié)點(diǎn)j∈N(k)有可能取xj=1。分情況討論如下。首先，如果節(jié)點(diǎn)j與節(jié)點(diǎn)i有連接，如圖1(b)中所示，則必然有xj=0。因此，需要將N(k)中所有與節(jié)點(diǎn)i相鄰的節(jié)點(diǎn)剔除，還要把節(jié)點(diǎn)i也剔除，然后記剩下的節(jié)點(diǎn)構(gòu)成的集合為N'(k)。接下來，對N'(k)進(jìn)行類似于推導(dǎo)式(7)所做的處理。假設(shè)N'(k)中包含有T'(k)個獨(dú)立子集(k) (1 ≤t≤T'(k))，其中D'*(k)是N'(k)的最大權(quán)重獨(dú)立子集。這樣，可以得到qk→i的計算公式為

接下來討論消息pk→i。該消息所對應(yīng)的情況為，由于xi=0，則在一般圖中xk=0與xk=1都是有可能的。如果xk=0，則可以重復(fù)推導(dǎo)式(6)或式(9)的過程，可以得到pk→i的計算公式為

反之，如果xk=1，重復(fù)式(6)的推導(dǎo)過程，可以得到pk→i的計算公式為

綜合這兩方面的計算，可以得到pk→i的計算公式為

為簡化起見，將pk→i與qk→i合并為單個消息mk→i=pk→i-qk→i。則式(8)，式(9)，式(12)中的計算公式可以簡化為

綜上，本文提出的分布式最大獨(dú)立集算法的運(yùn)行方式如下：

(1)初始化所有的消息mi→j=0；

(2)任意兩個相鄰節(jié)點(diǎn)k與i根據(jù)式(14)對消息mk→i進(jìn)行更新；

(3)每個節(jié)點(diǎn)i根據(jù)式(13)計算信用度量bi的取值；

(4)每個節(jié)點(diǎn)i根據(jù)式(5)判斷xi的取值；

(5)重復(fù)上述步驟2-步驟4直至收斂。

值得說明的是，在該算法中，需要每個節(jié)點(diǎn)計算D*(k)與D'*(k)，這就需要每個節(jié)點(diǎn)能夠了解自己鄰居節(jié)點(diǎn)之間的連接情況，并尋找其中的最大權(quán)重子集。與傳統(tǒng)算法相比，這增加了每個節(jié)點(diǎn)的通信復(fù)雜度與計算復(fù)雜度，分析如下。首先是通信復(fù)雜度。新算法要求每個節(jié)點(diǎn)獲得鄰居節(jié)點(diǎn)之間的局部拓?fù)湫畔ⅰＲ虼?，每個節(jié)點(diǎn)要向自己的鄰居節(jié)點(diǎn)廣播自己的鄰居節(jié)點(diǎn)列表，使得每個節(jié)點(diǎn)了解自己的鄰居節(jié)點(diǎn)之間的連接情況。假設(shè)每個節(jié)點(diǎn)平均有n個鄰居節(jié)點(diǎn)，為每個節(jié)點(diǎn)號編碼需要B個比特，則任意兩個相鄰節(jié)點(diǎn)間在每個更新周期內(nèi)將額外增加nB個比特的通信量。對于常見的無線網(wǎng)絡(luò)來說(即非極端密集部署的)，鄰居節(jié)點(diǎn)數(shù)都較小，所帶來的額外通信量一般來說不會很大。事實(shí)上，在一些已有系統(tǒng)標(biāo)準(zhǔn)(如IEEE 802.16)中，已經(jīng)包含了這種廣播鄰居節(jié)點(diǎn)列表的操作了。第二是計算復(fù)雜度。新算法要求每個節(jié)點(diǎn)尋找自己與鄰居節(jié)點(diǎn)組成的小網(wǎng)絡(luò)中的最大權(quán)重子集。由于鄰居節(jié)點(diǎn)僅限于單跳范圍內(nèi)，其規(guī)模一般來說是很小的，因此在其中尋找最大權(quán)重子集只需窮舉即可。假設(shè)每個節(jié)點(diǎn)平均有n個鄰居節(jié)點(diǎn)，則最大窮舉次數(shù)平均不會超過2n，當(dāng)n取值較小時，是比較容易實(shí)現(xiàn)的任務(wù)，所帶來的額外計算量一般來說不會很大。綜上，與傳統(tǒng)算法相比，新算法增加了一定的通信與計算復(fù)雜度，但這樣的復(fù)雜度是可以接受的。仿真試驗表明，改進(jìn)算法可以顯著提高消息交換算法在一般結(jié)構(gòu)圖中尋找最大權(quán)獨(dú)立集的能力，具體內(nèi)容在下節(jié)中給出。

4 性能仿真

本節(jié)仿真驗證新算法的性能。首先介紹仿真場景。假設(shè)在1 km×1 km的正方形區(qū)域內(nèi)隨機(jī)分布有若干節(jié)點(diǎn)。這樣就可以得到一個圖G=(V,E)，其中V是所有節(jié)點(diǎn)組成的集合，且每個節(jié)點(diǎn)都隨機(jī)產(chǎn)生一個0至1之間的數(shù)作為權(quán)重；E是所有邊組成集合。其中如果任意兩個節(jié)點(diǎn)之間距離小于某一門限值，則這兩個節(jié)點(diǎn)間有邊相連。在仿真中假設(shè)門限值為0.4 km。針對給定圖，本文將分別運(yùn)行3種不同的分布式MWIS算法。第1種算法就是文獻(xiàn)中常見的基于貪婪的分布式MWIS算法，并選擇了文獻(xiàn)[8]中的算法作為例子。第2種算法就是文獻(xiàn)[9]中的基于最大乘信用傳播的分布式 MWIS算法，即式(2)-式(4)中給出的算法。第3種算法就是本文新提出的改進(jìn)算法，即式(13)與式(14)中給出的算法。另外，我們還將通過最優(yōu)化方法計算給定圖中的最大權(quán)獨(dú)立子集，作為分布式算法性能的上限。

主要考察兩方面性能的比較，即算法輸出獨(dú)立子集的權(quán)重和性能的比較，以及算法尋找獨(dú)立子集需要迭代次數(shù)的比較。分別假設(shè)節(jié)點(diǎn)總數(shù)為10, 20,30, 40, 50。在不同的節(jié)點(diǎn)總數(shù)下，隨機(jī)生成100個不同的節(jié)點(diǎn)分布并得到相應(yīng)的圖，對每張圖分別運(yùn)行前述3種分布式MWIS算法以及窮舉算法，然后把100次仿真的結(jié)果平均起來作為該節(jié)點(diǎn)總數(shù)下的仿真結(jié)果，分別畫在圖2和圖3中。首先，從圖2中示出了4類算法的平均性能，從中可以看出本文所提出的新算法幾乎是最優(yōu)的，其性能與最優(yōu)化方法幾乎是相同的；未經(jīng)修改的基于信用傳播的分布式算法[9]則明顯性能較差，無法適用于一般圖結(jié)構(gòu)；而貪婪算法[8]則介于兩類算法中的中間，其性能一般來說總是好于信用傳播算法，但與本文的新算法則在性能上總是有一定的差距。接下來，在圖3中示出了兩類算法的平均迭代次數(shù)，從中可以看出本文所提出的新算法的迭代次數(shù)要多于信用傳播算法，并且平均迭代次數(shù)隨著節(jié)點(diǎn)數(shù)的增加而增加，而信用傳播算法的迭代次數(shù)則較少且受節(jié)點(diǎn)數(shù)改變的影響不大。這主要是由于本文新算法相對比較復(fù)雜，從而需要較多的迭代次數(shù)，以換得了較好的性能。

5 結(jié)論

本文研究了一般圖的最大權(quán)獨(dú)立子集的分布式算法。以基于最大乘信用傳播的分布式MWIS算法為框架，通過分析一般圖中最大權(quán)獨(dú)立集構(gòu)成的特點(diǎn)，在所有節(jié)點(diǎn)了解自己鄰居節(jié)點(diǎn)間局部拓?fù)湫畔⒌募僭O(shè)下，提出了一種改進(jìn)的相鄰節(jié)點(diǎn)間交換消息以及節(jié)點(diǎn)度量的計算公式，從而得到了一種新的改進(jìn)算法。仿真結(jié)果表明，該新算法針對一般圖進(jìn)行設(shè)計，擺脫了文獻(xiàn)中已有算法對圖必須是樹或者二分的束縛，能夠達(dá)到近似最優(yōu)的權(quán)重和性能。進(jìn)一步的，本文算法的迭代次數(shù)多于信用傳播算法，并且平均迭代次數(shù)隨著節(jié)點(diǎn)數(shù)的增加而增加，而信用傳播算法的迭代次數(shù)則較少且受節(jié)點(diǎn)數(shù)改變的影響不大。因此，本文算法是以較多的迭代次數(shù)換得了較好的性能。該算法的提出對于研究無線網(wǎng)絡(luò)資源調(diào)配、無線骨干網(wǎng)構(gòu)建等問題的一般方法具有一定的參考價值。

圖2 平均獨(dú)立子集權(quán)重和性能的比較

圖3 尋找獨(dú)立子集需要平均迭代次數(shù)的比較

[1]Dasgupta S, Papadimitriou C, and Vazirani U. Algorithms[M]. New York: McGraw-Hill, 2008, Chapter 8.

[2]Wang P and Bohacek S. Practical computation of optimal schedules in multihop wireless networks[J].IEEE/ACM Transactions on Networking, 2011, 19(2): 305-318.

[3]Lv S, Wang X, and Zhou X. Scheduling under SINR model in Ad hoc networks with successive interference cancellation[C].2010 IEEE Global Telecommunications Conference(GLOBECOM 2010), Miami, Florida, USA, Dec. 6-10, 2010:1-5.

[4]Li H, Cheng Y, Zhou C,et al.. Multi-dimensional conflict graph based computing for optimal capacity in MR-MC wireless networks[C]. 2010 IEEE 30th International Conference on Distributed Computing Systems (ICDCS 2010), Genova, Italy, June 21-25, 2010: 774-783.

[5]Li Y, Guo L, and Prasad S K. An energy-efficient distributed algorithm for minimum-latency aggregation scheduling in wireless sensor networks[C]. 2010 IEEE 30th International Conference on Distributed Computing Systems (ICDCS 2010), Genova, Italy, June 21-25, 2010: 827-836.

[6]Basagni S. Finding a maximal weighted independent set in wireless networks[J].Telecommunication Systems, 2001,18(1-3): 155-168.

[7]Sakai S, Togasaki M, and Yamazaki K. A note on greedy algorithm for the maximum weighted independent set problem[J].Discrete Applied Mathematics, 2003, 126(2-3):313-322.

[8]Nieberg T and Hurink J. Wireless communication graphs[C].Proceedings of the 2004 Intelligent Sensors, Sensor Networks& Information Processing Conference (ISSNIP 2004),Melbourne, Australia, Dec. 14-17, 2004: 367-372.

[9]Sanghavi S, Shah D, and Willsky A S. Message passing for maximum weight independent set[J].IEEE Transactions on Information Theory, 2009, 55(11): 4822-4834.

[10]Kschischang F R, Frey B J, and Loeloger E A. Factor graph and the sum-product algorithm[J].IEEE Transactions on Information Theory, 2001, 47(2): 498-519.

[11]Bayati M, Shah D, and Sharma M. Max-product for maximum weight matching: convergence, correctness, and LP duality[J].IEEE Transactions on Information Theory, 2008,54(3): 1241-1251.

[12]Sanghavi S, Malioutov D, and Willsky A S. Belief propagation and LP relaxation for weighted mathching in general graphs[J].IEEE Transactions on Information Theory,2011, 57(4): 2203-2212.