一種求解高密度最大權重團的信息傳播算法

摘要： 在高密度復雜結構帶權無向圖中，由于信息傳遞復雜，傳統(tǒng)信息傳播算法求解最大權重團問題效率較低。利用最大權重獨立集與最大權重團的映射關系提出一種針對高密度帶權無向圖求解最大權重團問題算法，該算法以最大積信息傳播算法為框架，將最大權重團的約束條件與置信傳播算法迭代方程相結合，設計信息傳播算法勢函數(shù)。同時，將高密度復雜結構帶權無向圖映射為因子圖，并進行去環(huán)操作，利用信息傳播迭代式進行特征收斂計算，通過迭代收斂后的最大后驗概率計算最大權重團最優(yōu)解。基于不同密度隨機圖進行實驗對比分析，實驗結果表明，該算法求解高密度復雜結構帶權無向圖最大權重問題時非常有效，求解總權值的準確度與求解速率均高于標準置信傳播算法。

關鍵詞： 最大權重團； 信息傳播算法；" 因子圖； 最大積算法

中圖分類號： TP301 文獻標志碼： A 文章編號： 1671－6841（2024）04－0056－09

DOI：" 10.13705/j.issn.1671－6841.2022247

An Information Propagation Algorithm for Solving High－density Maximum Weight Groups

YU" Zhuo1，" WANG" Xiaofeng1，2，" WU" Yuxiang1，" XIE" Zhixin1，" CAO" Zexuan1

（1.School of Computer Science and Engineering，North Minzu University， Yinchuan 750021，China; 2.Key Laboratory of Image and Graphics Intelligent Processing of State Ethnic Affairs Commission，North Minzu University， Yinchuan 750021，China）

Abstract：" In the weighted undirected graph with high density and complex structure， due to the complex information transfer， the traditional information propagation algorithm was less efficient to solve the maximum weighted clique problem. Using the mapping relationship between the maximum weight independent set and the maximum weight clique， an algorithm was proposed to solve the maximum weight group problem for high－density weighted undirected graphs. The propagation algorithm was combined with the iterative equation to design the potential function of the information propagation algorithm. At the same time， the weighted undirected graph of the high－density complex structure was mapped into a factor graph， and the deloop operation was performed， and the feature convergence calculation was performed by iterative information propagation， and the optimal solution of the maximum weight group was calculated by the maximum posterior probability after iterative convergence. Experimental results were compared and analyzed based on random graphs with different densities. The results showed that the algorithm was very effective in solving the maximum weight problem of weighted undirected graphs with high－density complex structures， and the accuracy and speed of solving the total weights were higher than those of the standard belief propagation algorithm.

Key words：maximum weight group; information transmission algorithm; factor graph; maximum product algorithm

0 引言

最大權重團問題是一個經典的組合優(yōu)化問題［1］。相較經典最大團問題，最大權重團問題要同時考慮頂點之間的權重差異和團的頂點數(shù)目兩個因素，最終在保證總權重和最大的基礎上使團中的頂點數(shù)目最大［2］，常規(guī)求解最大團算法在最大權重團問題中通常不適用［3］。最大權重團問題涉及多個領域，橫跨多個學科，在未知蛋白質的功能推測［4］、社會網絡關系分析［5］、計算機視覺圖像分割［6］等問題中提供重要的理論支撐［7］。

目前求解最大權重團問題算法較少，現(xiàn)有的精確求解算法大部分以基于分支定界法的搜索策略為主［8］。早期stergrd等通過剪枝操作結合頂點權重的降序排序進行順序遞歸查詢，提出clique算法求解最大權重團問題［9］。后來，Kumlander等對clique算法進行改進，對初始圖例進行一次染色，利用近似頂點染色法估計最大權重團上界［10］。Li等利用近似頂點染色法和MaxSAT推理技術將圖例進行MaxSAT編碼，計算子句沖突從而估計最大加權團上界［11］。從圖論的角度出發(fā)，在求解最大權重團中發(fā)現(xiàn)求解圖例的自身結構復雜度對求解效率有著重要的影響作用［12］。

針對求解圖例結構的選擇，大部分最大權重團算法通常采用大規(guī)模稀疏加權無向圖為計算圖例［13］，由于求解最大權重團問題需要考慮復雜的鄰居拓撲關系，使得高密度復雜圖例更為難解，通常算法在高密度圖例中表現(xiàn)出難解現(xiàn)象［14］。Pattabiraman等［15］使用改進后的分支定界法對密度為（0，0.5］的圖例進行求解，取得了優(yōu)異求解效率，但圖例密度擴大至（0.5，0.9］時求解速率明顯降低且部分小規(guī)模高密度圖在限制時間內無法求解。Li等［11］在利用MaxSAT推理進行求解大規(guī)模最大權重團問題中，在大規(guī)模稀疏圖中展現(xiàn)出好的結果，但在高密度圖中求解效果不突出。

信息傳播算法［16］作為一種啟發(fā)式的信息傳遞算法，起源于統(tǒng)計物理學，通過相應邊緣概率進行計算求解，在解決Max－3－SAT問題［17］、0－1背包問題［18］、旅行商問題［19］中表現(xiàn)優(yōu)異。特別地，Sanghavi等［20］利用LP（linear programming）的對偶形式與置信傳播算法迭代式結合，求解與最大權重團聯(lián)系緊密的最大權重獨立集問題，證明了置信傳播算法可以有效求解難解組合優(yōu)化問題。但該方法僅對二部圖和樹狀結構求解效果優(yōu)異，對于具有環(huán)狀的一般圖例，特別是奇數(shù)環(huán)圖例，則求解性能較差［21］。

基于上述研究，本文從整數(shù)規(guī)劃與線性規(guī)劃的角度出發(fā)，利用最大權重團問題與最大權重頂點獨立集的映射關系，啟發(fā)式地提出一種針對密集復雜帶權無回圖的最大權重團問題信息傳播算法。本文首先對最大權重團問題求解性質對因子圖進行改進，通過最大積信息傳播算法框架更新信息傳播迭代式，對環(huán)形情況進行去環(huán)操作，在此基礎上進行最大權重團的迭代計算，通過判斷函數(shù)確定最大權重團頂點集與權重數(shù)。最后，對算法利用不同規(guī)模問題模型進行可行性與有效性的實驗分析。實驗結果表明，在求解時間上，高密度帶權有環(huán)無向圖的求解速率隨著圖例規(guī)模的增大逐步優(yōu)于低密度圖，在求解精度與求解時間方面均優(yōu)于標準BP算法。

1 基本知識

1.1 最大權重團

給定一個無向圖G，V表示頂點集，E表示邊集，w為權重函數(shù)，w：V→Z+，w（vi）表示頂點vi的權重，最大權重團問題就是為從G中尋找權重最大的一個團Cmax，即Max∑v∈Cw（v）。特別地，當G中所有權值均為1時，退化為經典最大團問題，所以任何加權最大團問題的算法同樣適用于經典最大團［2］。在本文中對于任意一個團C都可以用變量集合z=（zi）∈{0，1}|V|進行表示，其中zi=1代表頂點i在團內，zi=0表示頂點i不在團內。N（i）為頂點i的鄰居節(jié)點，即N（i）={j∈V：（i，j）∈E}。在形式上，最大權重團問題可以描述為0－1整數(shù)規(guī)劃模型［22］，

1.2 因子圖

給定一個函數(shù)f：D1×…×Dn→R，對n個隨機變量X={X1，X2，…，Xn}，因子圖的思想是將f表示為局部函數(shù)的乘積fs，其中每個局部函數(shù)只依賴于子集XfsX的變量［23］。

因子圖（factor graph）可視為一個無向二部圖G=（V，E），其中V=X∪F，集合X為變量節(jié)點集合，將X作為一個有序向量X={X1，…，Xn}，并且假設該變量的值為x=（x1，…，xn）。對于每一個變量Xi都有一個對應的域Di。將集合F={f1，…，fm}稱為函數(shù)節(jié)點，函數(shù)節(jié)點是一個局部函數(shù)集，其中每個局部函數(shù)fs都是有序向量Xfs一個上域R的變量函數(shù)，記為Xfs=（Xi1，…，Xik）。Xfs的定義域記為Dfs，對應Xfs的所有變量定義域的笛卡爾積。邊集定義為{Xi，fs}∈E當且僅當Xi∈Xfs［23］。公式（2）給出了全局函數(shù)的乘積形式，

圖2表示因子圖中每條邊（f，x）上的信息傳遞方程，其中包括約束節(jié)點發(fā)送給變量節(jié)點的信息vx→f（Ci）與變量節(jié)點發(fā)給約束節(jié)點的信息uf→x（Ci），Ci表示頂點xi對應的具體信息值。例如，圖3給出了假設后的變量節(jié)點取值x=（x1，…，x5）與局部函數(shù)節(jié)點fs的對應關系，其中局部函數(shù)f1與變量值的具體對應關系為xf1=（x1，x2，x3），局部函數(shù)f2與變量值的具體對應關系為xf2=（x2，x4，x5），局部函數(shù)f3與變量值的具體對應關系為xf3=（x1，x3，x5），代入公式（2）可得全局函數(shù)乘積形式為f（x）=f1（xf1）f2（xf2）f3（xf3）。

1.3 線性規(guī)劃方程的簡單映射

最大權重團問題作為一種特殊的最大團問題同樣是一種線性規(guī)劃問題，且涉及約束條件與目標函數(shù)。給出一個無向圖G=（V，E），每個頂點zi上不僅有自身序列編號i，同時還有自身權重wi。對最大權重團的規(guī)劃方程進行LP松弛后得到最大權重團，用線性方程定義為［21］

其中：zi、zj為圖中頂點；E為圖G的補邊集。

通過文獻［24］可知，針對部分的線性規(guī)劃問題，存在一種簡單的因子圖映射轉化方法，即線性方程中的四個約束條件映射為相應因子圖的因子節(jié)點a、b、c、d，由方塊表示；條件變量x1、x2、x3被映射為因子圖中的變量節(jié)點，由圓圈表示。該方程求解的目標函數(shù)由多個函數(shù)、變量節(jié)點求和得到，具體的線性規(guī)劃問題與因子圖模型中各個節(jié)點的對應關系及約束關系用實線連接，如圖4所示。

四個約束條件映射為四個因子節(jié)點，連接關系表明了它們之間存在的約束關系，各節(jié)點相互獨立并且信息并行傳播。

2 求解最大權重團的信息傳播算法

2.1 最大積信息傳播算法框架

2.2 因子圖的改進表示

本文提出的方法利用了最大權重獨立集問題（maximum weight independent set，MWIS）和MWCP的映射關系ω（G）=α（G），其中：ω為最大權重團數(shù)；α為最大權重頂點獨立集數(shù)。由于最大頂點獨立集同樣是一類特殊的線性規(guī)劃問題，可將問題模型轉化為因子圖模型進行求解［23］，所以對與MWIS有著較強映射關系的MWCP提出新的因子圖構建模型。

首先，提取給定無向圖每個頂點對應的權重、頂點序列、位置關系、約束條件等；其次，將圖中相鄰頂點的約束聯(lián)系與權重關系映射為因子圖中的函數(shù)節(jié)點和變量節(jié)點，其中包括隱含節(jié)點和觀察節(jié)點；最后，生成對應的無向權重圖的因子圖模型。

在式（10）、（11）中可以看出計算聯(lián)合概率時需要對每個因子節(jié)點所連接的相鄰節(jié)點進行計算，因此對有邊相連的兩個節(jié)點進行約束關系映射，映射為因子節(jié)點，與變量節(jié)點相連，從而構成因子圖模型。

1） 變量節(jié)點。在原有的變量節(jié)點中添加兩類節(jié)點。a） 隱含節(jié)點hi，因子圖模型中包含一組隱含節(jié)點{h1，h2，…，hn}，代表每個頂點的權值數(shù)目；b） 觀察節(jié)點vi，因子圖模型中包含一組觀察節(jié)點集合{v1，v2，…，vm}，表示相應頂點選取概率大小。

2） 函數(shù)節(jié)點。根據(jù)式（10）、（11）發(fā)現(xiàn)，每個因子節(jié)點φa（za）需要連接兩個變量節(jié)點zi和zj，在信息傳遞的過程中信息值u從zi傳遞至φa（za），后由φa（za）傳遞至zj；信息值v從zj傳遞至φa（za），后由φa（za）傳遞至zi。可以看出消息傳遞路程多且傳遞時間長，為了減少消息的計算與發(fā)送量，本文將約束函數(shù)設置為隱藏函數(shù)。使消息不經過因子節(jié)點，只在變量節(jié)點之間傳遞。因子節(jié)點只提供約束關系，在最后一次計算中獲得節(jié)點選擇概率傳遞至觀察節(jié)點。

MWCP的因子圖轉化如算法1所示。首先，提取圖中頂點關系，獲取圖中各個頂點權值。對獲取的圖中所有頂點信息、頂點間的約束關系、權重進行對比。將各個頂點映射為變量節(jié)點，加入觀察節(jié)點和隱含節(jié)點后加入變量節(jié)點Ei。然后，將約束團數(shù)目的約束函數(shù)映射為因子節(jié)點a并設置為隱藏因子節(jié)點，只傳遞約束性質與求解概率，不傳遞信息。最后，將因子節(jié)點與變量節(jié)點之間的關系進行連線，得到改進后的MWCP因子圖模型。

算法1 因子圖的轉化

輸入：帶權無向圖G。

輸出：因子圖模型。

1） 提取無向圖頂點zi與對應權重wi。

2） 計算生成無向圖中每個節(jié)點的鄰居節(jié)點N（zi）獲取鄰接關系。

3） 無向圖的節(jié)點映射為變量節(jié)點zi。

4） 加入隱含節(jié)點 hi與觀察節(jié)點vi并共同構成新的變量節(jié)點Ei。

5） 將有邊相連的變量節(jié)點構成因子節(jié)點，并對因子節(jié)點進行隱藏處理。

6） 通過約束關系進行映射連接，確保相應節(jié)點的連接關系，形成改進后的最大權重團因子圖。

圖5（a）為無向加權圖G（V，E，W），zi為圖中頂點，wi為頂點zi的權重。對圖5（a）所示的無向加權圖進行因子圖模型轉化，其轉化結果如圖5（b）所示。

圖5（b）是對應的最大權重團的因子圖模型，Ei代表由隱含變量hi、觀察變量vi和無向圖頂點zi共同映射的因子圖新頂點；a、b、c代表存在邊相連頂點的約束條件，其連接頂點E1，E2，E3的約束關系使用線表示。通過因子節(jié)點提供的約束條件，信息在新節(jié)點之間相互傳遞，并在經過每個新節(jié)點時與節(jié)點內部的隱含變量、觀察變量同步更新信息，迭代完成后計算頂點數(shù)目與最終權重。

圖6給出了因子圖轉換方法，并且展示了因子節(jié)點E1的細節(jié)圖，用線表示內部結構。h1代表隱含變量，表示每個頂點所代表的權值大小，用加粗實線橢圓表示；v1代表觀察節(jié)點用方框表示，代表頂點z1成為MWCP頂點的概率情況。其中v1受到兩個相鄰節(jié)點的約束函數(shù)管制，用雙箭頭虛線表示。對于改進后的約束隱藏函數(shù)a、b、c，在圖6中用虛線方框表示。

2.3 更新信息傳播迭代式

利用最大積框架信息傳播框架，求解最大權重團問題。算法的核心為因子圖兩類節(jié)點的信息處理。在圖模型中，原有信息傳播算法在邊（i，a）有兩種信息傳遞形式［27］：1） 因子節(jié)點發(fā)送給變量節(jié)點的消息ua→i（zi）；2） 變量節(jié)點發(fā)送給因子節(jié)點的消息vi→a（zi）。通過對因子圖轉化法的改進，使得約束節(jié)點只約束相應變量節(jié)點但不進行消息的傳遞，通過變量節(jié)點間的相互傳遞，有效減少了消息傳遞之間的復雜計算。因此，對原有變量節(jié)點與因子節(jié)點之間的消息傳遞進行改進，將消息值 ua→i（zi）改進為

2.4 求解最大權重團的置信傳播算法

對于信息傳播算法來說，保持算法的收斂是至關重要的。通常來說，對于樹狀結構圖模型信息傳播算法基本可以達到收斂狀態(tài)，但對于一般有環(huán)圖模型，信息傳播算法有較大可能性呈現(xiàn)不收斂狀態(tài)［21］。對于有環(huán)圖的收斂性分析，文獻［21］指出，當圖中無奇數(shù)環(huán)且至多存在一個偶數(shù)環(huán)時信息傳播算法收斂，當圖中包含一個奇數(shù)環(huán)或至少兩個偶數(shù)環(huán)時信息傳播算法不收斂。由于本文研究高密度無向圖的最大權重團問題，因此多數(shù)情況呈現(xiàn)出不收斂狀態(tài)。對于不收斂問題，本文提出標記刪除方法來解決不收斂問題。

由公式（3）可知，根據(jù)約束條件的限定，在圖E集中連接的頂點需要進行取值分類處理。若zi=0，N（i）中的兩個節(jié)點l與h的取值可能為1也可能為0，若zi=1，則N（i）中的點都為0［28］。因此進行去環(huán)操作時需要分類討論，初始化賦值時，若zi=0時，對zk的所有權重進行比較，對權重較大的點進行已有賦值的高概率調整。若zi=1則相應zk=0，k∈N（i），并對zi取1的點進行候選節(jié)點標記，同時k的相鄰節(jié)點j∈N（k）。當zj的取值為1時，與zi=0取值情況相同，對wj較大的點重新調整高概率值；若zj∈N（i），即存在環(huán)路，則記錄ui→j（zi=0）的信息值并且對zi進行候選節(jié)點標記，對zk進行刪除，此時獲得局部非環(huán)圖或非環(huán)子圖。繼續(xù)進行去環(huán)操作，直至無環(huán)后將候選標記節(jié)點進行連接，即得到無環(huán)樹狀圖，按照最新信息值進行傳遞，設置最大收斂次數(shù)進行迭代計算。

綜上，求解高密度最大權重團的信息傳播算法總結為算法2。

算法2 求解最大權重團的信息傳播算法

輸入：帶權無向圖G，最大迭代次數(shù)。

輸出：最大權重團頂點數(shù)目，最大權重團總權重值。

1） 隨機生成帶權無向圖。

2） 調用算法1形成相應因子圖模型。

3） 將有環(huán)因子圖進行去環(huán)操作。

4） 對頂點進行隨機遍歷排序，確定搜索順序。

5） 初始化所有消息ui→j（zi=0），ui→j（zi=1）。

6） 令t←0，依據(jù)式（12）和（13）對所有頂點進行隨機排序，按照隨機排序后的頂點順序依次進行遍歷。

7） 依據(jù)改進的信息傳播算法迭代式進行循環(huán)迭代，達到迭代次數(shù)后退出，確定標記位的信息值。

8） 對已標記的節(jié)點進行數(shù)目與權重的統(tǒng)計。

在算法求解復雜度方面，對算法2進行對比分析。相較于傳統(tǒng)的BP算法，本文算法在傳統(tǒng)因子圖結構上通過設計相應的隱藏函數(shù)與標記函數(shù)對因子圖進行簡化處理，使消息傳遞的路徑更為簡潔高效。對于有n個頂點的無向圖，傳統(tǒng)因子圖構建方法最大權重團一般構建為（2n+e）個頂點的因子圖，傳遞信息的路徑相應增加一倍。而本文算法，將變量節(jié)點與其所對應的因子節(jié)點壓縮為一個節(jié)點，縮短其傳遞路徑，簡化求解結構使其求解復雜度降低，提高了求解效率。

3 數(shù)據(jù)實驗分析

本次實驗主要驗證了本文算法在求解高密度最大權重團問題中的求解準確性與高效性。采用密度在［0.2，0.9］的隨機帶權無向圖進行模擬一般圖例求解。在算法運行中，使用了最大團與最大頂點獨立集的映射關系，因此在求解最大權重團問題時對隨機圖例進行映射輸入。該實驗使用MacOS Monterey系統(tǒng)。基本配置：Intel core i5處理器，2.3 GHz；內存8 GB；進行python程序實現(xiàn)。

首先驗證算法可行性。隨機采用密度為［0.2，0.5，0.8］的帶權無向圖。對圖中每個頂點進行權重賦值，權重值［1，10］的正整數(shù)。選取節(jié)點規(guī)模n={10，20，30，40，50}的中小規(guī)模的帶權無向圖，多次實驗后取平均值。

表2展示了本文算法在n={10，20，30，40，50}且ρ={0.2，0.5，0.8}的無向圖內取得的結果，表明本文算法在不同頂點數(shù)目的情況下，不僅適用于中小規(guī)模高密度復雜圖，對稀疏圖與中等密度圖也產生有效的求解結果，具有良好的泛化性。

為了驗證文本算法針對高密度復雜圖例的快速求解性能，表3為在不同規(guī)模時本文算法在三類密

度下的求解時間與迭代次數(shù)對比表。分析表3實驗數(shù)據(jù)可知，在頂點規(guī)模為10、20、30、40、50時，隨著圖例密度的增加，求解時間逐步減少。例如：在n=50，ρ=0.2，ρ=0.5，ρ=0.8時求解時間分別為0.211 s，0.147 s，0.101 s，可以看出在頂點數(shù)目不變的情況下，高密度圖例求解時間小于低密度圖例，說明本文算法在高密度圖例中有更快的求解速率。

通過對比表3的迭代次數(shù)發(fā)現(xiàn)，相較于三種不同的密度圖例，本文算法求解高密度圖例時使用更少的迭代次數(shù)，對于較為稀疏的圖例則需要較多的迭代次數(shù)獲得求解結果。如n=50時，在密度為0.8的實驗圖例中迭代次數(shù)平均為17.4次，而密度為0.5和0.2的圖例中迭代次數(shù)平均為18.0和18.4，高密度圖例迭代次數(shù)小于較為稀疏的圖例。由此驗證，本文算法對高密度圖例有著較好的尋優(yōu)能力。

由于本文是基于傳統(tǒng)置信傳播算法進行改進，使用標準BP算法［29］進行迭代次數(shù)對比。表4展示了在綜合三類密度平均情況下對每個頂點的置信度取1與取0進行對比，綜合各類密度圖例，本文算法在求解最大權重團問題中具有較少的迭代次數(shù)。

為驗證改進后的置信傳播算法求解準確度，本文將標準BP算法（規(guī)定相同收斂次數(shù)）和貪婪算法［30］進行不同頂點數(shù)目下平均最大權重和對比，實驗結果如表5所示。

在表5中，本文算法求解最大權重團的平均權重和總體優(yōu)于標準的BP算法和貪婪算法。本文算法相較于標準BP算法有著較好的求解效果，呈現(xiàn)出穩(wěn)定上升的態(tài)勢，但標準BP算法起伏較大，這是因為本文算法在因子圖的構建中添加觀察節(jié)點，對高概率點進行標記；在去環(huán)操作中對無效信息點進行剪枝，使其搜索結果更為精確。對比貪婪算法，本文算法在求解結構上采用分布式結構進行求解，相較于傳統(tǒng)串行計算，在求解時間上有著顯著的提升。

4 結束語

最大權重團問題是經典的組合優(yōu)化問題，廣泛應用于各種領域。密集圖拓撲結構復雜，不易求解最大權重團問題，本文提出一種基于線性規(guī)劃方程求解最大權重團的信息傳播算法。首先，通過使用因子圖轉化方法將無向圖轉化為消息更易計算與傳遞的因子圖模型，改進描述函數(shù)，利用因子圖的特性與信息傳遞的并行特征對節(jié)點信息傳遞，經過多次迭代后得到實驗結果。其次，在此基礎上設置觀察節(jié)點、隱含節(jié)點與隱藏因子節(jié)點，并對相應節(jié)點設置約束關系，進行最大權重與最大團數(shù)目的平衡計算，得到符合問題約束的最大權重團。最后，實驗證明，相較于稀疏圖例，本文算法針對中小規(guī)模高密度圖例迭代次數(shù)更少，求解時間更快；與傳統(tǒng)BP算法和貪婪算法相比，本文算法有更低的迭代次數(shù)與更準確的求解效果。

參考文獻：

［1］仲盛， 謝立. 求解圖的最大團的一種算法［J］. 軟件學報， 1999， 10（3）： 288-292.

ZHONG S， XIE L. An algorithm computing the maximum clique in a graph［J］. Journal of software， 1999， 10（3）： 288-292.

［2］YU Z， WANG X F， ZHAO J. A local dense decision－making method for solving the maximum clique problem in large－scale undirected graphs［J］. Computers and electrical engineering， 2022， 102： 108220.

［3］SHIMIZU S， YAMAGUCHI K， MASUDA S. Parallelization of a branch－and－bound algorithm for the maximum weight clique problem［J］. Discrete optimization， 2021， 41： 100646.

［4］MENG X M， XIANG J， ZHENG R Q， et al. DPCMNE： detecting protein complexes from protein－protein interaction networks via multi－level network embedding［J］. IEEE/ACM transactions on computational biology and bioinformatics， 2022， 19（3）： 1592-1602.

［5］GSCHWIND T， IRNICH S， FURINI F， et al. A branch－and－price framework for decomposing graphs into relaxed cliques［J］. Informs journal on computing， 2021， 33（3）： 1070-1090.

［6］SHIROKANEV A， ILYASOVA N， DEMIN N， et al. Extracting a DME area based on graph－based image segmentation and collation of OCT retinal images［J］. Journal of physics： conference series， 2021， 1780： 012031.

［7］SHU Y C， ZHANG J， XIAO B， et al. Medical image segmentation based on active fusion－transduction of multi－stream features［J］. Knowledge－based systems， 2021， 220： 106950.

［8］江華. 最大團問題精確算法研究［D］. 武漢： 華中科技大學， 2017.

JIANG H. On exact algorithms for the maximum clique problem［D］. Wuhan： Huazhong University of Science and Technology， 2017.

［9］STERGRD P R J. A fast algorithm for the maximum clique problem［J］. Discrete applied mathematics， 2002， 120（1/2/3）： 197-207.

［10］KUMLANDER D. On importance of a special sorting in the maximum－weight clique algorithm based on colour classes［C］∥International Conference on Modelling， Computation and Optimization in Information Systems and Management Sciences. Berlin： Springer Press， 2008： 165-174.

［11］LI C M， LIU Y L， JIANG H， et al. A new upper bound for the maximum weight clique problem［J］. European journal of operational research， 2018， 270（1）： 66-77.

［12］WALTEROS J L， BUCHANAN A. Why is maximum clique often easy in practice？［J］. Operations research， 2020， 68（6）： 1866-1895.

［13］NOGUEIRA B， PINHEIRO R G S. A CPU－GPU local search heuristic for the maximum weight clique problem on massive graphs［J］. Computers amp; operations research， 2018， 90： 232-248.

［14］EL BAZ D， HIFI M， WU L， et al. A parallel ant colony optimization for the maximum－weight clique problem［C］∥IEEE International Parallel and Distributed Processing Symposium Workshops. Piscataway： IEEE Presss， 2016： 796-800.

［15］PATTABIRAMAN B， ALI PATWARY M M， GEBREMEDHIN A H， et al. Fast algorithms for the maximum clique problem on massive sparse graphs［C］∥International Workshop on Algorithms and Models for the Web－graph. Cham： Springer International Publishing， 2013： 156-169.

［16］YEDIDIA J S， FREEMAN W T， WEISS Y. Understanding belief propagation and its generalizations［J］. Intelligence， 2002， 8： 236-239.

［17］吳宇翔， 王曉峰， 丁紅勝， 等. 一種改進的警示傳播算法求解Max－SAT問題［J］. 計算機應用研究， 2022， 39（8）： 2290-2294.

WU Y X， WANG X F， DING H S， et al. Improved warning propagation algorithm for solving Max－SAT problem［J］. Application research of computers， 2022， 39（8）： 2290-2294.

［18］張丹丹， 王曉峰， 馮琬晶， 等. 一種求解0－1背包問題的置信傳播算法［J］. 鄭州大學學報（理學版）， 2021， 53（1）： 29-34.

ZHANG D D， WANG X F， FENG W J， et al. A belief propagation algorithm for 0－1 knapsack problem［J］. Journal of Zhengzhou university （natural science edition）， 2021， 53（1）： 29-34.

［19］程亞南， 王曉峰， 劉凇佐， 等. 一種求解旅行商問題的信息傳播算法［J］. 鄭州大學學報（理學版）， 2022， 54（3）： 52-58.

CHENG Y N， WANG X F， LIU S Z， et al. An information propagation algorithm for solving traveling salesman problem［J］. Journal of Zhengzhou university （natural science edition）， 2022， 54（3）： 52-58.

［20］SANGHAVI S， MALIOUTOV D， WILLSKY A. Belief propagation and LP relaxation for weighted matching in general graphs［J］. IEEE transactions on information theory， 2011， 57（4）： 2203-2212.

［21］CORNELISSEN K， MANTHEY B. Belief propagation for the maximum－weight independent set and minimum spanning tree problems［J］. Theoretical computer science， 2018， 738： 53-64.

［22］王曉峰， 于卓， 趙健， 等. 大規(guī)模圖例的最大團問題算法分析［J］. 計算機工程， 2022， 48（6）： 182-192， 199.

WANG X F， YU Z， ZHAO J， et al. Algorithm analysis for solving maximum clique problems of large－scale graphs［J］. Computer engineering， 2022， 48（6）： 182-192， 199.

［23］VIGAN I. Understanding belief propagation dialects and their application to optimization problems［D］. Zurich： Swiss Federal Institute of Technology， 2009.

［24］SHA J， LIU J B， LIN J， et al. A stage－combined belief propagation decoder for polar codes［J］. Journal of signal processing systems， 2018， 90（5）： 687-694.

［25］PARK S， SHIN J. Max－product belief propagation for linear programming： applications to combinatorial optimization［EB/OL］.（2014－12－16）［2022－03－15］. https：∥arxiv.org/abs/1412.4972.

［26］PARK S， SHIN J. Convergence and correctness of max－product belief propagation for linear programming［J］. SIAM journal on discrete mathematics， 2017， 31（3）： 2228-2246.

［27］王向陽， 張源. 一種改進的分布式最大權獨立集算法［J］. 電子與信息學報， 2012， 34（3）： 689-693.

WANG X Y， ZHANG Y. An improved distributed algorithm for maximum weight independent set（MWIS） problem［J］. Journal of electronics amp; information technology， 2012， 34（3）： 689-693.

［28］杜鵬. 一種啟發(fā)式的分布式最大獨立集算法［J］. 南京郵電大學學報（自然科學版）， 2013， 33（6）： 18-23， 28.

DU P. A heuristic distributed algorithm for the maximum weight independent set problem［J］. Journal of Nanjing university of posts and telecommunications （natural science）， 2013， 33（6）： 18-23， 28.

［29］SANGHAVI S， SHAH D， WILLSKY A S. Message passing for maximum weight independent set［J］. IEEE transactions on information theory， 2009， 55（11）： 4822-4834.

［30］NIEBERG T， HURINK J. Wireless communication graphs［C］∥Proceedings of the Intelligent Sensors， Sensor Networks and Information Processing Conference. Piscataway： IEEE Press， 2005： 367-372.

收稿日期：2022－08－18

基金項目：國家自然科學基金項目 （62062001，61962002）；寧夏自然科學基金項目 （2020AAC03214）；北方民族大學重大專項 （ZDZX201901）。

第一作者：于卓（1997—），男，碩士研究生，主要從事算法分析與設計研究，E－mail：zyu@stu.nmu.edu.cn。

通信作者：王曉峰（1980—），男，副教授，主要從事算法分析與設計、可計算性與計算復雜性研究，E－mail：xfwang@nmu.edu.cn。