馬闖 楊曉龍 陳含爽 張海峰

1) (安徽大學(xué)互聯(lián)網(wǎng)學(xué)院,合肥 230039)

2) (安徽大學(xué)物理與材料科學(xué)學(xué)院,合肥 230601)

3) (安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院,合肥 230601)

置信傳播(BP)算法作為推斷概率圖模型的主流算法是求解隨機塊模型中聯(lián)合概率分布的重要方法之一.但現(xiàn)有的方法要么在處理核邊結(jié)構(gòu)問題上存在精度不足問題,要么在理論的推導(dǎo)上存在近似太多,導(dǎo)致求解過程復(fù)雜且難以理解問題,或兩個問題均存在.當然,精度不足也是由近似多造成的.導(dǎo)致理論近似多且推導(dǎo)復(fù)雜的主要原因,是隨機塊模型推斷過程中求解聯(lián)合概率分布并不是直接套用BP 算法,即處理的圖(網(wǎng)絡(luò))與概率圖模型的圖不統(tǒng)一.因此,本文利用平均場近似修正聯(lián)合概率分布,使其完全匹配BP 算法的迭代公式,這樣使得在理論推導(dǎo)上簡單易懂.最后通過實驗驗證,該方法是有效的.

1 引言

復(fù)雜系統(tǒng)可以用復(fù)雜網(wǎng)絡(luò)進行建模,而復(fù)雜網(wǎng)絡(luò)主要由點與邊組成.在現(xiàn)實中,點與邊的信息是可以直接或間接[1]獲取的,如在航空網(wǎng)絡(luò)系統(tǒng)中[2],節(jié)點為機場,如果機場之間具有航班,就存在一條邊;科學(xué)家合作網(wǎng)絡(luò)[3],節(jié)點表示科學(xué)家,如果兩個科學(xué)家有合作就存在一條邊等.這些簡單的點與連邊關(guān)系可以幫助我們揭示復(fù)雜系統(tǒng)的隱藏信息,如節(jié)點的屬性,可以對應(yīng)著節(jié)點在系統(tǒng)中屬于哪個功能塊或組織[4].如航空網(wǎng)絡(luò)中的核心與外圍(邊緣)機場[5],科學(xué)家合作網(wǎng)絡(luò)中的特定研究領(lǐng)域的小組[6]等.因此,如何通過節(jié)點的連邊信息去探測這些中尺度結(jié)構(gòu),如社團結(jié)構(gòu)、核邊結(jié)構(gòu)(核心-邊緣),是一個重要的科學(xué)問題,這些問題得到了來自各個領(lǐng)域?qū)W者的研究.

社團結(jié)構(gòu)的描述為社團內(nèi)部緊密相連,而社團之間連接稀疏[6].社團結(jié)構(gòu)的探測方法已經(jīng)有很多,主要有基于模塊度的方法[7?9]、譜劃分的方法[4,10]、矩陣分解的方法[11,12]、基于動力學(xué)的方法[13,14]、隨機塊模型的方法[15,16]以及其他方法[17,18];核邊結(jié)構(gòu)的描述為核與核緊密相連,核與邊緊密相連,邊與邊連接稀疏[19,20].相較于社團結(jié)構(gòu),對核邊結(jié)構(gòu)探測方法的研究相對較少.主要有給定某種中心性指標,然后通過截斷選取最重要的一部分節(jié)點作為核心節(jié)點[21,22];定義核邊結(jié)構(gòu)的指標,然后利用最優(yōu)化方法求解[23,24];通過隨機塊模型探測核邊結(jié)構(gòu)[25,26]以及其他方法[5,27?29].

可以看出,隨機塊模型在解決社團結(jié)構(gòu)與核邊結(jié)構(gòu)的探測問題上都是行之有效的[25].隨機塊模型是一種生成模型,可以生成具有模塊結(jié)構(gòu)的網(wǎng)絡(luò)[15].即首先給定n 個節(jié)點,隨機分配到k 個模塊中.假設(shè)向量 γ 表示每個模塊的規(guī)模,即 γr表示第r 個模塊的大小占總節(jié)點個數(shù)的比例,則每個節(jié)點就以 γr的概率分配到第r 模塊中.然后給定一個k×k的關(guān)聯(lián)矩陣p (對稱矩陣),任意兩個節(jié)點(一個節(jié)點屬于模塊s,一個節(jié)點屬于模塊r)以 prs的概率相連.這樣就可以得到一個以參數(shù) γ 與p 生成的隨機網(wǎng)絡(luò).如,當 k=2 時,如果p11>p12,p22>p12,生成的網(wǎng)絡(luò)具有社團結(jié)構(gòu);如果 p11≥p12≥p22,生成的網(wǎng)絡(luò)具有核邊結(jié)構(gòu).

給定特定參數(shù) γ 與p,可以生成具有社團結(jié)構(gòu)或核邊結(jié)構(gòu)的網(wǎng)絡(luò).也就是說,如果一個網(wǎng)絡(luò)具有社團或核邊結(jié)構(gòu),那么可以通過學(xué)習該模型(即模型參數(shù)),來確定它是怎么生成的,以此來探測哪些節(jié)點屬于哪個社團,或者哪些節(jié)點屬于核,哪些節(jié)點屬于邊.因此,隨機塊模型不僅可以用來探測社團結(jié)構(gòu),還可以用來探測核心邊緣結(jié)構(gòu).其中EM 算法是學(xué)習該模型的重要方法[16,25,26,30,31],而通過聯(lián)合概率公式,確定邊際概率又是EM 算法的關(guān)鍵部分與難點.基于馬爾科夫鏈的蒙特卡羅方法(MCMC)是解決該難點的一種較好的方法[30],但是由于采樣空間非常大,會造成時間復(fù)雜度過高、精度低的問題.置信傳播(BP)算法[32]可以很好地解決上述問題[16,25,26,31],因此被廣泛用來解決社團或核邊結(jié)構(gòu)的探測問題.BP 算法用來推斷馬爾科夫隨機場中的邊際概率,當馬爾可夫網(wǎng)絡(luò)是樹狀圖時,具有精確解;當馬爾可夫網(wǎng)絡(luò)是稀疏的,會得到近似精確解[33].

應(yīng)用BP 算法解決社團結(jié)構(gòu)的探測問題時,由于網(wǎng)絡(luò)的稀疏性,在公式的推導(dǎo)中關(guān)于節(jié)點鄰居可以忽略不計的近似是合理的[16,31],但是處理核邊結(jié)構(gòu)探測問題時,這種近似卻是致命的,因為核節(jié)點具有天然的大度性質(zhì).因此,在另外一篇文章中,我們對BP 算法進行了稍微的改進(IBP),就可以很好地解決此問題[25].但是伴隨而來的就是IBP 算法的推導(dǎo)過程中,需要進行大量的近似處理,以及各種模糊的推導(dǎo),并不是可以套用BP 算法公式[34]直接得到的.同樣的道理,BP 算法解決社團結(jié)構(gòu)的探測問題時,即使其中各種近似是合理的,也會存在上述不能套用BP 算法公式直接得到的情況.這使得即使BP 或IBP 算法在社團劃分或核邊結(jié)構(gòu)探測中能得到很好的結(jié)果,但是推導(dǎo)過程卻是復(fù)雜且難于理解,或者說是不那么精確的.因此,本文從平均場近似[35]的角度出發(fā),先應(yīng)用平均場近似對聯(lián)合概率進行處理,得到可以完全匹配BP 算法的形式,然后再套用BP 算法公式(而不是以往的先套用公式,然后在公式里近似處理),在不需要任何修改、近似以及假設(shè)的情況下直接得到求解邊際概率的迭代公式.使得隨機塊模型解決社團結(jié)構(gòu)或核邊結(jié)構(gòu)探測問題時,既可以保證結(jié)果的精度,又可以保證理論的簡單明了、有理有據(jù).

2 知識回顧

隨機塊模型最直接的用處就是按照某種需求生成具有某種模塊結(jié)構(gòu)的人工網(wǎng)絡(luò).例如在社團探測中,就可以用隨機塊模型生成具有社團結(jié)構(gòu)的人工網(wǎng)絡(luò),以此來評估社團挖掘算法的好壞.但是本文將用到它的另外一個重要應(yīng)用,就是通過學(xué)習隨機塊模型中的參數(shù)使其最好地匹配給定網(wǎng)絡(luò),從而揭示給定網(wǎng)絡(luò)的結(jié)構(gòu).顯然,這是一個參數(shù)估計問題,可以采用最大似然估計的方法進行解決[16,25,26].

2.1 最大似然估計

最大似然估計研究的是給定什么樣的參數(shù)可以使得似然函數(shù)的值最大,也就是使得已經(jīng)發(fā)生的事件概率最大.假設(shè)給定一個無權(quán)無向網(wǎng)絡(luò)的鄰接矩陣A,其中 Aij=1 表示第i 個節(jié)點與第j 個節(jié)點相連,Aij=0 表示不相連.在隨機塊模型中,當給定參數(shù)p 與 γ,則似然函數(shù)就可以用P(A|p,γ) 來表示.因此,需要最大化 P(A|p,γ),以此求解p 與γ,從而來揭示網(wǎng)絡(luò)的結(jié)構(gòu).但是,通過觀察可以發(fā)現(xiàn),似然函數(shù)里包含一個隱形變量g,其中 gi表示節(jié)點i 所屬的模塊.因此有

可以看出,最大化公式(1)是一個含有隱變量的最大似然估計問題,因此可以應(yīng)用EM 算法進行求解[36].

2.2 EM 算法求解隨機塊模型

EM 算法在理論推導(dǎo)上是根據(jù)詹森不等式不斷求解對數(shù)似然函數(shù)的下界函數(shù)最優(yōu)值,以此逐漸收斂到原始函數(shù)的最優(yōu)值.因此,對(1)式取對數(shù),然后根據(jù)詹森不等式有[25,26]:

其中

可以看出,q(g)=P(g|A,p,γ),表示給定一個網(wǎng)絡(luò),在參數(shù)p 與 γ 給定的條件下,該網(wǎng)絡(luò)每個節(jié)點分配為g 的概率,這是一個聯(lián)合概率.

當(3)式成立的情況下,(2)式等號成立,所以最大化公式(1)問題可以轉(zhuǎn)化為最大化 L(p,γ) 問題.對 L(p,γ) 進一步推導(dǎo)有:

如果gi=r,則δgi,r=1,否則δgi,r=0.

根據(jù)上述推導(dǎo)過程,可以得到一個迭代公式.即首先初始化p 與 γ,根據(jù)(3)式計算邊際概率與,然后根據(jù)(7)式與(8)式計算新的p 與 γ,重復(fù)上述過程直到收斂為止.最后可以通過收斂的邊際概率的值對每個節(jié)點進行劃分.其中,當需要探測社團結(jié)構(gòu)時,只需初始化p 為具有社團結(jié)構(gòu)形式的關(guān)聯(lián)矩陣,如果需要探測核邊結(jié)構(gòu)時,則需要初始化p 為具有核邊結(jié)構(gòu)形式的關(guān)聯(lián)矩陣.

需要注意的是,在應(yīng)用(7)式求解 prs時,需要計算任意節(jié)點對之間的值,這將花費大量的計算時間.因此可以化簡為

所以(7)式可以寫成:

應(yīng)用(11)式代替(7)式只需要計算有邊的節(jié)點對的兩節(jié)點邊際概率,這將很大程度上減少計算量,特別是在稀疏網(wǎng)絡(luò).而且在BP 算法中這種處理更顯得尤為必要,后面將進一步介紹.

到這里并沒結(jié)束,通過遍歷所有構(gòu)型(kn種構(gòu)型)的方法根據(jù)(3)式求解全概率 q(g) 以此求解邊際概率是顯然不可行的.因此如何根據(jù)(3)式求解邊際概率是EM 算法的難點,也是關(guān)鍵部分.下面將介紹兩種求解方法:MC 采樣和BP 算法,并分析他們在處理社團與核邊結(jié)構(gòu)探測中存在的不足之處.

2.3 馬爾科夫鏈蒙特卡羅方法(MCMC)

這里應(yīng)用MCMC 模擬的方法按照聯(lián)合概率公式(3)對網(wǎng)絡(luò)的劃分構(gòu)型(即 g=[g1,g2,···,gn]T)進行采樣.本文將采用單分量 Metropolis-Hastings(M-H) 方法[37].設(shè)表示在馬爾科夫鏈中第t 輪迭代后的狀態(tài),其中每一輪迭代都需要對每個分量的狀態(tài)進行一次迭代更新.

例如,在 t+1 輪迭代中,已經(jīng)迭代好的分量(第i 個分量)的狀態(tài)記為.假設(shè)要對第j 個分量進行采樣,首先設(shè)表示在 t+1 輪迭代中在對第j 個分量進行處理時,其他分量的狀態(tài).特別地,當對每一輪的各個分量進行迭代是按照順序處理時,有:

但是,由于所有構(gòu)型共用 kn種可能,在網(wǎng)絡(luò)較大的情況下,采樣空間巨大,很難收斂到(3)式的概率分布,從而造成計算結(jié)果產(chǎn)生誤差,并且不穩(wěn)定.下面介紹一種快速求解邊際概率的方法,即BP 算法.

2.4 BP 算法

2.4.1 BP 算法簡介

BP 算法可以用來推斷馬爾科夫隨機場(又稱為概率圖模型)中的邊際概率[33].在本文中,考慮一種特殊的概率圖模型—成對圖模型.成對圖模型定義在一個無向圖G(V,E) 上,每一個頂點vi∈V表示X 中的一個隨機變量 xi,每一條邊(vi,vj)∈E表示隨機變量 xi與 xj之間的某種依賴關(guān)系.給定每個節(jié)點 vi一個點位勢 φi(xi),以及每一條邊 (vi,vj)∈E 一個邊位勢 ψij(xi,xj),則在該成對馬爾科夫網(wǎng)上的分布為

其中Z 為歸一化常數(shù),通常稱為配分函數(shù).

求解(14)式這個聯(lián)合概率的邊際概率可以通過BP 算法迭代公式求得,迭代過程如下[34]:

其中,N(i) 表示節(jié)點 vi的鄰居,vi→j(xi) 為概率圖修改后(即刪除節(jié)點 vj) xi的邊際概率,bi(xi) 為xi的邊際概率.另外還可以得到一條邊上兩個節(jié)點的聯(lián)合概率:

2.4.2 BP 算法求解隨機塊模型

對于聯(lián)合概率公式(3),可以看成是一個馬爾科夫網(wǎng)上的概率分布.在這里,馬爾科夫網(wǎng)是一個全連通圖,且隨機變量為 g=[g1,g2,···,gn]T.對于一對節(jié)點 (vi,vj),如果 Aij=1,其邊位勢為ψij(gi,gj)=Pgigj,如果 Aij=0,其邊位勢 為ψij(gi,gj)=1?Pgigj,節(jié)點 vi的點位勢為 φi(gi)=γgi.所以根據(jù)BP 算法的迭代公式(15),當j 節(jié)點是i 節(jié)點的鄰居時,可以得到[26,31]:

假設(shè)1 如果第j 個節(jié)點不是第i 節(jié)點的鄰居,移除節(jié)點 vj對節(jié)點 vi屬于模塊r 的概率沒有影響,即有;

假設(shè)2 當網(wǎng)絡(luò)規(guī)模很大且很稀疏的時候,對集合 V/N?中所有元素做運算近似于對集合V 中所有元素做運算,即有 f(V/N?)≈f(V),其中f(?)代表某種運算.

根據(jù)上述兩個假設(shè),有:

這是一個外場量.所以(18)式可以寫成:

其中配分函數(shù)為

其中配分函數(shù)為

根據(jù)(17)式可以得到一條邊上兩個點的聯(lián)合概率:

通過不停迭代(20)式和(22)式,直到收斂,然后通過(22)式與(24)式即可計算出

上述算法在網(wǎng)絡(luò)規(guī)模比較大且稀疏的時候是適用的,但是應(yīng)用此方法探測核邊結(jié)構(gòu),就會存在問題.眾所周知,一個具有核邊結(jié)構(gòu)的網(wǎng)絡(luò)的核節(jié)點不僅和核節(jié)點緊密相連,而且和邊節(jié)點緊密相連,也就是說核節(jié)點與整個網(wǎng)絡(luò)中的節(jié)點都是緊密相連的,具有天然的大度性質(zhì).所以在假設(shè)2 中,對集合 V/N?中所有元素做運算近似于對集合V 中所有元素做運算,這種假設(shè)在核邊結(jié)構(gòu)的探測中是不合理的,有可能是錯誤的.針對于此,我們在另外一篇文章中對BP 算法進行了修正[25],可以很好地解決這個問題.

2.4.3 修正后的BP 算法(IBP)

首先對聯(lián)合概率分布公式(3)稍作處理,可得:

則每條邊的信使為[25,38]

給定一個假設(shè):

假設(shè)3 當網(wǎng)絡(luò)很大且很稀疏的時候,對集合V/{i,j}中所有元素做運算近似于對集合V 中所有元素做運算.顯然,這個假設(shè)對結(jié)果的影響可以忽略不計.

根據(jù)假設(shè)1 與假設(shè)3 可以得到下面近似:

這是一個與(19)式一樣的外場量,但是這里的近似與(19)式的近似相比,也就是假設(shè)3 與假設(shè)2 相比不會依賴節(jié)點度的大小,所以更適用于具有核邊結(jié)構(gòu)的網(wǎng)絡(luò).(26)式可以寫成:

其中配分函數(shù)為

其中

根據(jù)(17)式可以得到一條邊上兩個點的聯(lián)合概率:

通過(28)式,(30)式,(32)式與(20)式,(22)式,(24)相比,可以發(fā)現(xiàn)算法改進后,最終的結(jié)果僅僅是代替了 prs,沒有增加任何多余的計算復(fù)雜度,但是修改后的方法已經(jīng)驗證了更適用于含有大度節(jié)點的網(wǎng)絡(luò)[25],如核邊結(jié)構(gòu)網(wǎng)絡(luò).

改進后的算法雖然在結(jié)果上表現(xiàn)出來強大的優(yōu)勢,但是在理論推導(dǎo)上存在一定的問題.根據(jù)BP 算法的計算信使公式(15),從聯(lián)合概率公式(25)并不能直接推導(dǎo)得到的信使迭代公式(26)(這種直接寫法是參考文獻[35]).這是因為概率分布公式(25)相比(3)式雖然做了變形處理,但是兩個公式在數(shù)值上依然相等,即在把一個全連通圖當做一個馬爾科夫網(wǎng)的情況下,對于一對節(jié)點 (vi,vj),如果 Aij=1,其邊位勢還是 ψij(gi,gj)=Pgigj,如果 Aij=0,其邊位勢也還是 ψij(gi,gj)=1?Pgigj.所以說這里得到的信使迭代公式應(yīng)該還是(18)式而不是(26)式.

在這里如果想從概率分布公式(25)得到相比信使迭代公式(18)更好的(26)式,換句話說,如果想得到比BP 算法更好的IBP 算法,可以按照下面的思路去理解.這里的馬爾科夫網(wǎng)不僅僅是一個全連通圖,還需要在全連通圖上再加上M (原網(wǎng)絡(luò)上邊的個數(shù))條額外邊.對于一對節(jié)點 (vi,vj),如果 Aij=1,馬爾科夫網(wǎng)上的邊就要看成兩條邊,其邊位勢就分解成 ψij(gi,gj)=1?Pgigj與如果 Aij=0,其邊位勢還是 ψij(gi,gj)=1?Pgigj.這樣理解以后,就可以按照BP 算法公式(15)得到信使迭代公式(26).即使這樣,根據(jù)假設(shè)3 與假設(shè)2 還是得不到最終的信使迭代公式(28),在這里還應(yīng)滿足相比假設(shè)2更嚴格的假設(shè),即:在馬爾科夫網(wǎng)中所有邊位勢為ψij(gi,gj)=1?Pgigj的節(jié)點對 (vi,vj) (包括原網(wǎng)絡(luò)中不存在邊以及額外增加的存在邊),有意思就是存在一些少部分節(jié)點對 (vi,vj),即使 vj是vi的鄰居也要近似處理,即移除節(jié)點 vj對節(jié)點 vi屬于模塊r 的概率的影響忽略不計.總的來說,雖然改進后的BP 算法在實驗結(jié)果上會表現(xiàn)出很好的效果,但是存在理論推導(dǎo)上比較復(fù)雜、近似處理的過程太多、不易理解等問題.

2.4.4 小 結(jié)

BP 算法可以對聯(lián)合概率公式(3)與(25)進行求解,以此得到兩種迭代公式(前者用BP 算法表示,后者用IBP 算法表示)求解邊際概率.但是都存在一些問題:1)在BP 算法中,要滿足假設(shè)1 與假設(shè)2,因此不適用核邊結(jié)構(gòu)的探測;2)在IBP 算法中,雖然在實驗中已經(jīng)驗證了比BP 算法有著更好的性能,但是在理論上處理得太過復(fù)雜,還存在一些在理論上不易理解的假設(shè).

而且,通過觀察可以看出,無論是BP 算法還是IBP 算法所處理的馬爾科夫網(wǎng)(至少也是全連通圖)都是與要處理的原始網(wǎng)絡(luò)不一致的.雖然原始網(wǎng)絡(luò)是稀疏的,但是馬爾科夫網(wǎng)絡(luò)卻是全連通的,這也造成了即使BP 算法與IBP 算法表現(xiàn)得效果好,卻有所疑惑.這是因為我們都知道:當馬爾科夫網(wǎng)是樹狀網(wǎng)絡(luò),BP 算法是精確的,當馬爾科夫網(wǎng)是稀疏的時候,BP 算法是近似精確的.

所以,下面將從另外一個角度出發(fā),即首先對聯(lián)合概率公式(3)與(25)進行近似處理(而不是在BP 算法的推理中近似處理),得到一個新的概率公式,這個概率公式要滿足兩個條件:1)由這個公式導(dǎo)出的馬爾科夫隨機網(wǎng)與原始網(wǎng)絡(luò)一致;2)這個公式在形式上與(14)式完全一致.前者可以保證馬爾科夫網(wǎng)的稀疏性,后者可以保證在應(yīng)用BP 算法的時候簡潔明了且便于理解.

3 基于平均場近似的BP 算法

首先對聯(lián)合概率公式(3)進行平均場近似處理.概率分布(3)式可以表示為

再應(yīng)用一次平均場近似,即

因此聯(lián)合概率公式(3)經(jīng)過兩次平均場近似可以寫成:

把此聯(lián)合概率分布定義為一個成對馬爾科夫網(wǎng)上的概率分布,而且馬爾科夫網(wǎng)與原始網(wǎng)絡(luò)一致.其中,對于一條邊 (vi,vj),其邊位勢為ψij(gi,gj)=[Pgigj,對于一個(節(jié)點 vi,) 其點位]勢為φi(gi)=所以直接根據(jù)BP 算法的公式(15)—(17)式,可以不經(jīng)過任何近似地得到:

其中配分函數(shù) Zi→j與 Zi可以分別表示為

上述迭代過程我們記為MFBP 算法.

類似地,針對IBP 算法處理過程,也可以對聯(lián)合概率公式(3)先進行變形、再平均場近似處理.即概率分布(3)式可以表示為

因此聯(lián)合概率公式(3)經(jīng)過一次平均場近似可以寫成

把此聯(lián)合概率分布定義為一個成對馬爾科夫網(wǎng)上的概率分布,而且馬爾科夫網(wǎng)與原始網(wǎng)絡(luò)一致.其中,對于一條邊 (vi,vj),其邊位勢為ψij(gi,gj)=對于一個節(jié)點vi,其點位勢為φi(gi)=所以直接根據(jù)BP 算法的公式(15)—(17)式,可以得到:

其中配分函數(shù) Zi→j與 Zi可以分別表示為

上述迭代過程記為MFIBP 算法.

對比BP 算法與MFBP 算法、IBP 算法與MFIBP 算法的最終迭代公式,發(fā)現(xiàn)不同的只是外場量.在節(jié)點個數(shù)足夠多,且網(wǎng)絡(luò)比較稀疏的情況下,BP 與IBP 算法的外場都可以表示為

又因為,di/n →0 且 ln(1?prs)→ prs,則MFBP 算法的外場量可以近似為

MFIBP 算法的外場量可以近似為

可以看出:理論上,經(jīng)過平均場近似后得到的MFBP 算法和MFIBP 算法在一定條件下分別與原有的BP 算法和IBP 算法是等價的.但是在理論推導(dǎo)上,平均場近似的方法要更簡單合理且便于理解.MFIBP 算法與MFBP 算法相比較,少了一次平均場近似.

下面將對比BP 算法和MFBP 算法,以及IBP 算法和MFIBP 算法實驗上的效果.

4 中尺度結(jié)構(gòu)的探測

下面將在社團結(jié)構(gòu)及核邊結(jié)構(gòu)探測上進行實驗驗證.在社團結(jié)構(gòu)探測中,為了驗證不同算法探測結(jié)果的好壞,將采用NMI 指標進行衡量,即[39]:

其中,X 與Y 分別為算法探測的結(jié)果以及真實的結(jié)果;I(X,Y) 表示X 與Y 之間的互信息;H(X) 與H(Y)分別表示X 與Y 的信息熵.

對于核邊結(jié)構(gòu)的探測結(jié)果的評價,NMI 并不是一個合理的指標,這是因為核邊結(jié)構(gòu)的核與邊的地位并不是等價的.所以將采用 F1 指標進行衡量,即[40]:

其中,P 表示預(yù)測結(jié)果中,預(yù)測為正(本文中為核)的樣本中預(yù)測正確的概率,R 表示數(shù)據(jù)樣本中,正樣本中預(yù)測正確的概率.

4.1 社團結(jié)構(gòu)探測

首先采用隨機塊模型生成具有社團結(jié)構(gòu)的基準網(wǎng)絡(luò),以此來驗證MFBP 算法和MFIBP 算法分別與BP 算法和IBP 算法的區(qū)別.假設(shè)有k 個模塊,則每個節(jié)點就以 γr的概率分配到第r 模塊中.社團之間節(jié)點的連邊概率定義為prs=cin/n(r=s)和 prs=cout/n(rs),因此網(wǎng)絡(luò)的平均度為c=

如果每個模塊的大小一致,即 γr=1/k,則網(wǎng)絡(luò)的平均度為 c=[cin+q(cout?1)]/q.定義模塊外部與社團內(nèi)部的連接概率比為 ε=cout/cin.所以,當 ε<1 時生成網(wǎng)絡(luò)具有社團結(jié)構(gòu),且越小社團結(jié)構(gòu)越明顯;當 ε=1 時生成網(wǎng)絡(luò)為ER 隨機圖.當n →∞時,網(wǎng)絡(luò)檢測社團結(jié)構(gòu)會存在一個閾值[38]:

即,如果 ε>ε?時,各種社團算法都無法檢測出社團結(jié)構(gòu);當ε<ε?時,BP 算法可以探測出社團結(jié)構(gòu).

從理論上,前面的分析可以看出,當網(wǎng)絡(luò)節(jié)點個數(shù)足夠多,網(wǎng)絡(luò)連接比較稀疏時,BP 算法、MFBP 算法、IBP 算法以及MFIBP 算法是近似等價的,通過圖1(a)可以驗證,所有結(jié)果為10 次結(jié)果的平均值(下同).通過圖1(b)—圖1(d)可以發(fā)現(xiàn),當網(wǎng)絡(luò)連接稀疏且規(guī)模較小時,BP 算法、MFBP 算法、IBP 算法以及MFIBP 算法的結(jié)果也是一致的.但是,在網(wǎng)絡(luò)連接稠密的情況下(如圖2),可以發(fā)現(xiàn)MFBP 算法要優(yōu)于BP 算法,且與MFIBP 算法、IBP 算法一致.

圖1 稀疏基準網(wǎng)絡(luò)社團結(jié)構(gòu)探測 (a) n=10000,c=3,γ=[0.5,0.5]T,ε?=0.27 ;(b) n=200,c=10,γ=[0.5,0.5]T,ε?=0.520;(c) n=200,c=10,γ=[0.3,0.7]T ;(d) n=200,c=10,γ=[1/3,1/3,1/3]T,ε?=0.419Fig.1.Community structure detection in sparse benchmark networks:(a) n=10000,c=3,γ=[0.5,0.5]T,ε?=0.27 ;(b) n=200,c=10,γ=[0.5,0.5]T,ε?=0.520 ;(c) n=200,c=10,γ=[0.3,0.7]T ;(d) n=200,c=10,γ=[1/3,1/3,1/3]T,ε?=0.419.

圖2 稠密基準網(wǎng)絡(luò)社團結(jié)構(gòu)探測 (a) n=200,c=50,γ=[0.5,0.5]T,ε?=0.75 ;(b) n=200,c=50,γ=[0.3,0.7]T,(c) n=200,c=30,γ=[1/3,1/3,1/3]T,ε?=0.599Fig.2.Community structure detection in dense benchmark networks:(a) n=200,c=50,γ=[0.5,0.5]T,ε?=0.75 ;(b) n=200,c=50,γ=[0.3,0.7]T ;(c) n=200,c=30,γ=[1/3,1/3,1/3]T,ε?=0.599.

4.2 核邊結(jié)構(gòu)探測

生成具有核邊結(jié)構(gòu)特性的基準網(wǎng)絡(luò)來驗證MFBP 算法和MFIBP 算法分別與BP 算法和IBP 算法的區(qū)別.給定3 個參數(shù):核與核的連邊概率 PCC,核與邊的連邊概率 PCP,以及邊與邊的連邊概率PPP,當設(shè)置 PCC>PCP>PPP時,可以生成一個具有核邊結(jié)構(gòu)的網(wǎng)絡(luò)[28].在本文中,設(shè)PPP=0.05,PCC=θ,PCP=0.6θ.網(wǎng)絡(luò)的大小 n=200,其中核節(jié)點的個數(shù)為50,邊節(jié)點的個數(shù)為150.圖3所示為4 種算法在不同參數(shù)基準網(wǎng)絡(luò)的核邊結(jié)構(gòu)的探測情況,其中實驗結(jié)果為10 次結(jié)果的平均值.同樣可以發(fā)現(xiàn),MFBP 算法要優(yōu)于BP 算法,且與MFIBP 算法、IBP 算法一致.在BP 算法中,當核邊結(jié)構(gòu)足夠明顯時,卻表現(xiàn)出了較差的結(jié)果,這是因為核邊結(jié)構(gòu)明顯,意味著網(wǎng)絡(luò)結(jié)構(gòu)稠密,特別是核節(jié)點的度很大,這會導(dǎo)致(19)式關(guān)于用所有節(jié)點集合近似鄰居的補集變得極其不合理,而MFBP 算法、IBP 算法以及MFIBP 算法沒有這方面的缺陷.

圖3 基準網(wǎng)絡(luò)的核邊結(jié)構(gòu)探測Fig.3.CP structure detection in benchmark networks.

接著,在美國航空網(wǎng)絡(luò)上驗證本文中的算法,其中每個節(jié)點代表一個機場,共有332 個節(jié)點;每條邊表示兩個機場具有航班,共有2126 條邊[5].應(yīng)用BP 算法,求解結(jié)果有27 個核;應(yīng)用MFBP 算法,求解結(jié)果有34 個核;應(yīng)用IBP 算法,求解結(jié)果有47 個核;應(yīng)用MFIBP 算法,求解結(jié)果有47 個核.其中對應(yīng)的參數(shù)結(jié)果見(54)式—(57)式.為了驗證上述4 個算法求得結(jié)果的精確性,采用MCMC 采樣求解EM 算法,共采樣1000 輪(每輪n次),得到的結(jié)果共有47 核,具體參數(shù)如(58)式.如果把MCMC 結(jié)果作為真實結(jié)果,則BP 算法、MFBP 算法、IBP算法以及MFIBP 算法結(jié)果的F1值分別為0.730,0.840,1.000 以及1.000.從上述結(jié)果可以看出,在美國航空網(wǎng)絡(luò)的核邊結(jié)構(gòu)實驗中,MFBP 算法結(jié)果要優(yōu)于BP 算法,MFIBP 算法結(jié)果與IBP 算法一致,且接近精確解.而且MFIBP算法要優(yōu)于MFBP 算法,這是因為MFBP 算法比MFIBP 算法多一次平均場近似.

5 結(jié)論

本文詳細描述了隨機塊模型探測社團結(jié)構(gòu)、核邊結(jié)構(gòu)的理論,以及MCMC 和BP 算法求解該理論的方法,并分析其優(yōu)缺點.通過理論分析以得到:1)原始的BP 算法不適用于核邊結(jié)構(gòu)的探測;2)修正后得到的IBP 算法,雖然適用于核邊結(jié)構(gòu),但在理論上推導(dǎo)近似多且不明朗;3)無論是BP 算法還是IBP 算法,所處理的馬爾科夫網(wǎng)(聯(lián)合概率分布),既不是原始網(wǎng)絡(luò),也不滿足網(wǎng)絡(luò)稀疏條件.最后一條是造成隨機塊模型中BP 算法和IBP 算法理論難以理解的主要原因.針對于此,本文首先對聯(lián)合概率分布進行平均場近似,得到一個好的聯(lián)合分布函數(shù),然后可以直接套用BP 算法理論,且在這一步不需要任何近似,使得BP 算法求解隨機塊模型這一套方法,不僅在結(jié)果上效果顯著,而且在理論上通俗易懂.這種先通過平均場近似再套用BP 算法還適用于利用最小化哈密頓量(關(guān)于模塊度的函數(shù))探測社團結(jié)構(gòu)的方法中[38],和本文一樣,將使得理該論推導(dǎo)部分變得簡單易懂.

本文的計算工作得到了安徽大學(xué)高性能計算平臺的支持.