一種求解最小支配集問題的置信傳播算法

劉子琳，王曉峰，2，蘆 磊，程亞南

(1. 北方民族大學計算機科學與工程學院，寧夏 銀川 750021；2. 北方民族大學圖像圖形智能處理國家民委重點實驗室，寧夏 銀川 750021)

1 引言

在運籌學中，最小支配集已經(jīng)被證明是一個NP難問題[1]。最小支配集(Minimum Dominating Set，簡稱為MDS)是一種最重要的支配集問題，在社會網(wǎng)絡[2]、城市交通網(wǎng)絡[3]，以及物流網(wǎng)絡中心的選址[4]等領域有著廣泛的應用。最小支配集問題的目的是構造一個最小的節(jié)點集合，使得網(wǎng)絡的任何節(jié)點要么在該集合中，要么與該集合中至少一個節(jié)點相鄰。目前，求解最小支配集問題的算法主要分為精確算法[5]和啟發(fā)式算法[6]，精確算法能夠處理一些小規(guī)模問題，但處理大規(guī)模問題時的時間復雜度和空間復雜度較高；啟發(fā)式算法能獲得較好近似度結果，時間復雜度較低，但容易陷入局部最優(yōu)解，其完備性和唯一性不能保證。

在無向圖G(V，E)中，V表示圖G中的所有節(jié)點，E表示所有節(jié)點之間的邊。令集合S={v1，v2，…，vm}，其中vm?V，若S?V，S≠?，對于?x∈V-S，x都與S中至少一個節(jié)點有邊相連，則稱S是圖G的支配集。所有支配集中節(jié)點數(shù)目最少的則稱為圖G的最小支配集。|S|為最小支配數(shù)，相關文獻中也用γ(G)表示[7]。

在求解最小支配集的相關算法研究中，文獻[5]描述了求解最小支配集的精確算法，錯誤率較小，但時間復雜度極大。文獻[8]采用線性規(guī)劃的內點法求解最大集合覆蓋，極大地降低了計算復雜度。文獻[9]比較了標準的貪婪算法、LP近似算法以及將貪婪算法和LP近似算法相結合而設計的混合算法的性能，得出了LP混合算法具有高效性。文獻[10]將粗糙集理論中的屬性序引入到圖論中，研究頂點序下圖的支配集問題。文獻[11]通過對蟻群算法添加信息素校正策略，設計了求解最小連通支配集的蟻群優(yōu)化算法。局部搜索算法也已經(jīng)被提出來啟發(fā)式地解決MDS問題[12-15]，到目前為止，最好的多項式算法只能保證得到的支配集的大小不超過最小值的lnN倍[16.17]。

線性規(guī)劃(Linear Programming)是運籌學中研究、發(fā)展較成熟的一個重要分支，是一種用來輔助科研人員進行科學研究的數(shù)學方法。線性規(guī)劃問題一般是指求線性目標函數(shù)在線性約束條件下的最大值或最小值的問題，構建線性規(guī)劃方程來求問題最優(yōu)解[18]。

近年來，信息傳播算法(Message Propagation Algorithm，MP)發(fā)展迅速，信息傳播算法基于統(tǒng)計物理學的“空腔”概念提出，是一種作用于因子圖(Factor Graph)上的概率算法[19，20]。在組合優(yōu)化問題方面，信息傳播算法的應用已取得豐碩的成果，如MAX-SAT問題、Maximum-Weight Matching問題、Minimum Cost Network Flow問題、圖的著色、最大獨立集等[21]。文獻[20]提出了三種信息傳播算法求解可滿足問題，分別為警示傳播(Warning Propagation，WP) 算法、置信傳播(Belief Propagation，BP) 算法和調查傳播(Survey Propagation，SP)算法，SP算法是目前求解可滿足問題最為有效的算法，能夠稍高于線性時間求解難解SAT區(qū)域的具備107變量規(guī)模的實例，幾乎能夠有效求解接近相變點的可滿足性實例。文獻[22]指出，廣義葉子移除過程可以精確地解決MDS問題，并用平均場方法求解了一個自旋玻璃模型來估計MDS的大小。文獻[23]指出，BP算法可以解決用線性規(guī)劃(Linear Programming，LP)公式來描述的組合優(yōu)化問題，并且證明了其收斂性。文獻[24]設計了大量組合優(yōu)化問題的BP算法，這對我們設計求解最小支配集的置信傳播算法很有參考意義。

基于上述研究，本文將MDS問題的無向圖通過集合覆蓋映射為因子圖，基于因子圖構建線性規(guī)劃方程，設計出一種求解最小支配集問題的置信傳播算法。實驗結果表明：本算法可以近似解決最小支配集問題，且算法的性能優(yōu)于其它算法。

2 基本知識

2.1 集合覆蓋

給定一個全集U，集合S={S1，S2，…，Sn}，Si∈U且S1∪S2∪…∪Sn=U。集合覆蓋問題要找到一個子集D={D1，D2，…Dk}，D∈S，使得D1∪D2∪…∪Dk=U，同時|D|最小。例如給定全集U={1，2，3，4，5}，S={{1，2，3}，{2，4}，{3，4}，{4，5}}，雖然S中所有元素的并集是U，但是可以找到S的一個最小子集D={{1，2，3}∪{4，5}}，使得{1，2，3}∪{4，5}=U，則集合D可以被稱為一個集合覆蓋。

文獻[25]指出支配集可規(guī)約到集合覆蓋問題，求解網(wǎng)絡無向圖的支配集時，可以先轉化成求集合覆蓋問題的解。轉換的步驟為：遍歷所有的節(jié)點，將當前遍歷到的節(jié)點及其鄰居節(jié)點放置到同一個子集合中，則最小支配集問題轉化為找到一個所含頂點個數(shù)最少的子集T，使得|T∩Sj|≥1，其中Sj是當前節(jié)點及其鄰居節(jié)點的集合。相應地，集合覆蓋問題也可使用BP算法的思路去求解。

2.2 因子圖

因子圖(Factor Graph)用圖模型來代表變量之間的關系，可以將一個復雜的網(wǎng)絡結構模型化。因子圖是一個具有變量節(jié)點和因子節(jié)點的二部圖，可以將一個含有多個變量的全局函數(shù)因子分解，得到幾個局部函數(shù)的乘積。因此在最小支配集問題上，網(wǎng)絡節(jié)點的聯(lián)合置信分布比較復雜的情況下，因子圖結合信息傳播算法可以將網(wǎng)絡節(jié)點的聯(lián)合置信分布進行邊緣化，從而將復雜的實際問題簡單化。

圖1 因子圖模型

給定一個賦值指派z={x1，x2，…xn}∈{0，1}n，如圖1所示的因子圖模型，變量節(jié)點X={x1，x2，x3，x4}，因子節(jié)點F={fa，fb，fc}，當且僅當函數(shù)節(jié)點fn與變量節(jié)點xn之間有對應關系時，兩者有邊相連。則圖1中的因子圖關系可以表示為Pr[Z=z]=fa(x1，x3)fb(x1，x2，x4)fc(x2，x4)。因此我們可用如下GM公式表示因子圖：

(1)

3 因子圖轉換算法

根據(jù)網(wǎng)絡支配集的特性，可以將無向網(wǎng)絡圖的各個節(jié)點映射成變量節(jié)點，各個節(jié)點及其鄰居節(jié)點構成的子集合映射成函數(shù)節(jié)點，即可生成對應問題的因子圖模型。相對應的，在集合覆蓋問題中，一個集合對應一個因子節(jié)點，集合里面的變元即為因子節(jié)點的所有鄰居節(jié)點。下面我們給出最小支配集問題對應的無向圖與因子圖之間的轉換算法。

算法開始時隨機生成無向圖鄰接矩陣，首先生成各節(jié)點及其鄰居節(jié)點構成的集合，映射成函數(shù)節(jié)點，圖中的各個頂點則映射成變量節(jié)點。最后獲得變量節(jié)點和函數(shù)節(jié)點的對應關系，構造成因子圖。具體算法過程如下：

算法1：因子圖轉換算法

輸入：無向圖

輸出：因子圖模型

1)生成無向圖鄰接矩陣；

2)生成各節(jié)點及其鄰居節(jié)點構成的子集合；

3)無向圖中的節(jié)點映射為因子圖中的變量節(jié)點；

4)一個子集合為一個函數(shù)節(jié)點，并向集合里面的變元節(jié)點添加邊。

具體轉化結果如圖2、圖3所示。

圖2 無向圖G

圖2是一個無向圖G(V，E)，頂點集V={1，2，3，4，5，6}。最小支配集為{3，5}或{2，3}，最小連通支配集為{2，3}。轉化成集合覆蓋問題，則有6個集合，分別為：S1={1，2，5}，S2={2，1，3，5}，S3={3，2，5，6}，S4={4，3}，S5={5，1，2，6}，S6={6，3，5}。

圖3 圖2對應的因子圖模型

如圖3所示，將6個節(jié)點映射成為變量節(jié)點，6個集合S={S1，S2，S3，S4，S5，S6}代表每個節(jié)點及其鄰居節(jié)點構成的集合，映射成函數(shù)節(jié)點。算法由Sn與n之間相互傳遞消息，改變兩類節(jié)點的信息，直至收斂。

4 最小支配集的信念傳播算法

4.1 置信迭代方程

BP算法的迭代方程為

(2)

(3)

其中Z是歸一化函數(shù)。

4.2 最小支配集線性規(guī)劃方程

最小支配集問題是一類經(jīng)典的組合優(yōu)化問題，該問題的LP方程

(4)

其中δ(a)是因子圖中因子節(jié)點a的所有相鄰變量節(jié)點，xi對應因子圖中變量節(jié)點，xi=1表示選取該點選入最小支配集中，xi=0表示不選取，則對GM模型有如下定義

(5)

對于最小支配集問題的能量函數(shù)ψa定義如下

(6)

4.3 最小支配集的置信傳播算法

算法2： BP-update算法

輸入：MDS對應的因子圖，最大迭代次數(shù)tmax；精度ε

0)初始化：對于因子圖的每個邊a→i，隨機初始化消息μa→i(xi)∈[0，1]

1)從t=1到t=tmax：

(7)

因子圖變量節(jié)點的概率即為無向圖節(jié)點的取值概率，根據(jù)式(3)得到每個節(jié)點的取值概率，構建出節(jié)點的概率向量p=(p(1)，p(2)…p(n))。通過以下算法求出具體的最小支配集。定義一個最小支配集τ={x1，x2，…，xn}，如果xi=1，則在最小支配集集合中；如果xi=0，則不在最小支配集集合中。下面給出求解MDS的BP算法，記為BP-MDS算法。

算法3： BP-MDS算法

輸入：節(jié)點的取值概率向量p；節(jié)點集合[nodes]

輸出：最小支配集τ

for i in [nodes]：

if pi(1)>pi(0)：

xi=1

elif pi(1)

xi=0

else：

xi=none

if τ is not [dominating set]：

for i in [nodes]：

if len([xi+neighbor(xi)])<1：

j=random[xi+neighbor(xi)]

xj=1

for i in [nodes]：

if xi==0：

continue

else：

xi=0

if τ is not [dominating set]：

xi=1

5 數(shù)值實驗及分析

本文實驗以普通PC的64位Windows10操作系統(tǒng)為平臺，基于Python3.7進行算法測試。

圖4 不同節(jié)點規(guī)模的收斂速度

圖4所示為BP-MDS算法在不同節(jié)點規(guī)模下的收斂速度。隨機選取三組節(jié)點規(guī)模的無向圖，其中節(jié)點規(guī)模n={50，100，200}，不同規(guī)模分別隨機生成100組實例進行實驗。橫坐標是迭代次數(shù)，縱坐標是收斂概率。由圖可見，隨著節(jié)點規(guī)模增加，迭代次數(shù)增大，收斂速度變慢，意味著算法的效率逐漸降低。但后期始終可以收斂，說明收斂速度并沒有影響算法的尋優(yōu)質量，很好地驗證了BP-MDS算法的可行性。

圖5 三種算法的平均最優(yōu)解

圖5是KCenters算法、貪婪算法與BP-MDS算法在不同節(jié)點規(guī)模下得到的平均最小支配集大小。對n個節(jié)點生成的隨機無向圖求最小支配集，對三種算法在50組實例中取得的解求平均值進行比較?？梢钥吹叫∫?guī)模實例中(n<=20)，三種算法的求解質量相近。但隨著節(jié)點規(guī)模增加，BP-MDS算法的求解質量明顯優(yōu)于KCenters算法和貪婪算法。由此可見，隨著n增大，BP-MDS算法求解性能優(yōu)于另外兩種算法。

圖6 BP-MDS算法收斂性

圖6所示是BP-MDS算法在不同規(guī)模下的收斂性。隨著規(guī)模n的增大，算法求得的解空間也較大，大大增加了運行時間和迭代次數(shù)，當?shù)螖?shù)達到最大值，算法強制退出。雖然隨著問題規(guī)模的增大BP算法效率有一定降低，但是經(jīng)過表1可得，BP算法的效率仍然優(yōu)于其他算法。

表1是BP-MDS算法與KCenters算法、遺傳算法在不同規(guī)模下求得平均最優(yōu)解的時間比較。其中n是節(jié)點規(guī)模，AVG是平均最優(yōu)解，Time是求得最優(yōu)解的平均時間?？梢钥吹皆谛∫?guī)模實例下，雖然BP-MDS算法的求解效率略低于KCenters算法，求得解的質量卻始終優(yōu)于KCenters算法。隨著規(guī)模增大，BP-MDS算法在時間和求解質量上都要優(yōu)于另外兩種算法。

表1 三種算法的平均時間

6 總結

本文設計了求解無向圖的最小支配集問題的置信傳播算法，將把最小支配集映射成因子圖，構建基于因子圖的線性規(guī)劃方程，代入BP迭代方程中，不斷迭代直至收斂得到實驗結果，同時這種算法也為集合覆蓋問題的求解提供了思路。實驗結果表明，置信傳播算法求解的時間復雜度較低，效率較高，總體來說其性能優(yōu)于傳統(tǒng)的啟發(fā)式算法和分布式算法。但缺陷是隨著問題規(guī)模的增大，可能產(chǎn)生不收斂的現(xiàn)象。接下來的工作是盡量解決大規(guī)模不收斂的情況，設計求解最小支配集的調查傳播算法、用信息傳播算法求解支配集及其變種問題、將線性規(guī)劃模型推廣到更多的組合優(yōu)化問題等等。