基于置信傳播的復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法

尤心心，葛 檬

(天津大學(xué) 軟件學(xué)院，天津 300350)

基于置信傳播的復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法

尤心心，葛 檬*

(天津大學(xué) 軟件學(xué)院，天津 300350)

經(jīng)典的置信傳播(BP)算法能夠通過有限次數(shù)的迭代，推斷出所有節(jié)點(diǎn)的邊緣概率分布和最大似然概率。針對該算法在迭代過程中產(chǎn)生的影響精度和收斂速度的強(qiáng)烈震蕩，找出了造成震蕩的三個主要因素：強(qiáng)勢能、緊密的環(huán)路和矛盾的方向，并有針對性地改進(jìn)了該算法的核心更新規(guī)則；同時又進(jìn)一步提出了異步消息傳遞方式，克服傳統(tǒng)置信傳播算法采用的同步消息傳播方式的收斂慢、效率低等缺點(diǎn)。利用隨機(jī)塊模型擬合網(wǎng)絡(luò)的生成過程，利用經(jīng)典的期望最大化算法對模型進(jìn)行求解，分別利用改進(jìn)前后的置信傳播算法推斷隱變量的后驗概率。在五個真實網(wǎng)絡(luò)上的實驗表明，兩個改進(jìn)均使得精度和速度不同程度地提高。

復(fù)雜網(wǎng)絡(luò)；社團(tuán)發(fā)現(xiàn)；置信傳播；隨機(jī)塊模型；收斂速度

0 引言

社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)[1]的一個重要特征，它將網(wǎng)絡(luò)分成具有密集內(nèi)在聯(lián)系的子群，同一社團(tuán)中的節(jié)點(diǎn)通常擁有共同的性質(zhì)和緊密的關(guān)系[2]。因此，社團(tuán)發(fā)現(xiàn)[3]問題成為了復(fù)雜網(wǎng)絡(luò)研究中的一個重要的熱點(diǎn)問題，激發(fā)了大量來自不同領(lǐng)域的學(xué)者對其進(jìn)行研究。從社團(tuán)發(fā)現(xiàn)算法的研究內(nèi)容方面，可分為：1)基于網(wǎng)絡(luò)結(jié)構(gòu)的社團(tuán)發(fā)現(xiàn)，代表方法有：凝聚或分裂算法[4]、基于模塊度優(yōu)化的方法[5]、譜方法[6]、動力學(xué)方法[2]、基于標(biāo)簽傳播的方法[7]、基于仿生算法的方法[8]；2)基于隨機(jī)模型的社團(tuán)發(fā)現(xiàn)[9-11]等。隨機(jī)模型被視為一類非常有前景的方法[12]，其大部分都是通過拓展或改進(jìn)隨機(jī)塊模型[13]對社團(tuán)結(jié)構(gòu)進(jìn)行描述，并通過定義不同類型的目標(biāo)函數(shù)、采用不同優(yōu)化算法來推導(dǎo)出社團(tuán)結(jié)構(gòu)。本文利用隨機(jī)塊模型擬合網(wǎng)絡(luò)的生成過程，使用經(jīng)典的期望最大化算法進(jìn)行優(yōu)化[10-11]，期望部分的目標(biāo)是推理隱變量的后驗概率，本文利用置信傳播算法[14]承擔(dān)這一關(guān)鍵任務(wù)，該算法能夠通過有限次數(shù)的迭代，推論出節(jié)點(diǎn)的邊緣概率分布和最大似然概率；最大化部分是利用通過期望部分得到的隱變量的后驗概率計算模型參數(shù)。通過期望和最大化兩個步驟的多次迭代達(dá)到收斂，收斂后每個節(jié)點(diǎn)的邊緣概率分布中最大的值對應(yīng)的社團(tuán)被認(rèn)為是該節(jié)點(diǎn)的社團(tuán)標(biāo)簽，隨機(jī)塊模型的參數(shù)也得到確定。

然而，在置信傳播算法迭代過程中，往往會不斷發(fā)生震蕩的現(xiàn)象，如圖1所示，虛線呈現(xiàn)出非常強(qiáng)烈的震蕩，并且一直沒能收斂，而實線經(jīng)過幾次迭代很快就收斂了，這說明震蕩會導(dǎo)致收斂速度慢，進(jìn)而影響精度。很顯然，本文希望盡量避免這樣的震蕩，也就是在圖中只出現(xiàn)這種快速收斂的實線。經(jīng)過大量理論研究，本文總結(jié)產(chǎn)生震蕩的原因有3個：一是強(qiáng)烈的勢能，也就是不同節(jié)點(diǎn)對之間的勢能差值非常大；二是緊環(huán)，也就是節(jié)點(diǎn)之間形成環(huán)的緊密程度；三是矛盾的方向。這三點(diǎn)組合在一起，勢能差值越大，環(huán)越緊，方向矛盾程度越強(qiáng)烈，震蕩越激烈。

其次，置信傳播算法每次迭代收斂的消息數(shù)量太少，這也將會導(dǎo)致速度和精度同時變差。這主要是因為大多數(shù)置信傳播算法在迭代過程中采用的是同步更新，如圖2(a)所示，每一次更新意味著所有節(jié)點(diǎn)同時計算即將發(fā)出的消息并將其發(fā)出，所有節(jié)點(diǎn)也同時收到所有其他節(jié)點(diǎn)發(fā)來的消息，也就是說每個節(jié)點(diǎn)第一次發(fā)出的消息只是它自身攜帶的信息，并不能結(jié)合其他節(jié)點(diǎn)發(fā)來的消息一并發(fā)送出去，這樣的消息內(nèi)容顯然不夠充分。如果從便于實現(xiàn)的角度來說，這是一個不錯的算法，可以實現(xiàn)平行的工作，彼此之間沒有任何依賴。但不幸的是，同步置信傳播算法每次迭代傳遞的消息中包含的有價值信息太少，這導(dǎo)致每次迭代收斂的消息數(shù)目比較少，收斂速度也非常慢。

圖1 震蕩與收斂對比Fig. 1 Comparison of oscillation and convergence

圖2 同步與異步更新對比Fig. 2 Comparison of synchronous and asynchronous updates

為了解決震蕩問題，本文提出這樣的改進(jìn)措施：在每次計算消息時，采取一個權(quán)重的方式加入舊的消息，也就是說一條新消息等于一定比例的舊消息(上次迭代計算出的信息)加上一定比例的新消息(本次迭代計算出的消息)，并且通過控制權(quán)重參數(shù)平衡新、舊消息產(chǎn)生的影響，這樣能有效減小勢能的強(qiáng)烈差異和方向上的矛盾程度，同時也能緩解緊環(huán)的現(xiàn)象，大幅減弱甚至消除震蕩。針對第二個問題，本文提出針對同步消息傳遞方式缺點(diǎn)改進(jìn)后的異步消息傳遞方式，即每次只更新一條消息，下一條需要被更新的消息能夠綜合發(fā)送方自身的信息和其他節(jié)點(diǎn)發(fā)來的新消息，這樣每條消息攜帶的信息既豐富又新鮮，每次的消息傳遞效率也更高。如圖2(b)所示，第一條消息是1號節(jié)點(diǎn)將自身的信息發(fā)送到2號節(jié)點(diǎn)；第三條消息是2號節(jié)點(diǎn)將自身的信息和1號節(jié)點(diǎn)發(fā)來的新消息進(jìn)行綜合之后，再發(fā)送到3號節(jié)點(diǎn)。采用這樣的消息傳遞方式能夠使得每一條新更新的消息(例如1號節(jié)點(diǎn)發(fā)給2號節(jié)點(diǎn)的消息)立即投入使用，所以每次迭代過后收斂的消息數(shù)量會大幅增多，速度和精度都得到提高。

1 方法

1.1 問題描述

假設(shè)現(xiàn)在有一個觀測到的隨機(jī)圖[15]，其具有n個節(jié)點(diǎn)和m條邊，這個圖用對稱鄰接矩陣A來表示，如果節(jié)點(diǎn)u和節(jié)點(diǎn)v之間有邊，A中對應(yīng)位置auv=1；否則，auv=0?，F(xiàn)在的目標(biāo)是劃分這n個節(jié)點(diǎn)到K個社團(tuán)中，使用隨機(jī)塊模型刻畫網(wǎng)絡(luò)的生成過程[16]，假設(shè)鄰接矩陣中每一項auv都是獨(dú)立的且服從泊松分布的；每一個節(jié)點(diǎn)u具有一個社團(tuán)標(biāo)簽Gu∈{1，2，…，K}，表示節(jié)點(diǎn)u所在的社團(tuán)，且Gu～Multi(γ)；塊分配是所有Gu的集合。假設(shè)塊之間的邊個數(shù)服從泊松分布，這些泊松分布通過一個K×K的塊關(guān)聯(lián)矩陣ω被指定。

取對數(shù)的完全數(shù)據(jù)似然公式是：

(1)

這里nr是塊r中節(jié)點(diǎn)數(shù)，mrs是連接塊r和塊s的邊的數(shù)量。參數(shù)γ和ω可以通過最大化式(1)給出：

現(xiàn)在的目標(biāo)是通過聯(lián)合在γ、ω和g上最大化式(1)，從而確定塊分配G；如果用統(tǒng)計物理專業(yè)的術(shù)語來表達(dá)，就是去發(fā)現(xiàn)基態(tài)g，基態(tài)g能夠最小化-lb [P(a,g|γ,ω)]的能量。為了得到參數(shù)γ和ω，關(guān)注生成圖的總似然函數(shù)：

(2)

對所有K×n個可能的塊分配進(jìn)行加和。

本文使用期望最大化算法對模型進(jìn)行求解，利用置信傳播算法估計包括對數(shù)似然-lb [P(a,g|γ,ω)]和每個節(jié)點(diǎn)的邊緣化分布，也就是期望步驟的求解目標(biāo)，但置信傳播算法存在嚴(yán)重的震蕩問題，并且同步消息傳遞方式帶來的結(jié)果并不令人滿意，所以本文要針對這兩點(diǎn)問題提出改進(jìn)。

1.2 震蕩減弱

(3)

代表如果Gu=r，Gr=s時auv采取它觀測值的概率。那么有：

(4)

如果直接利用式(4)傳遞消息，就會產(chǎn)生強(qiáng)烈的震蕩，這是因為每個從節(jié)點(diǎn)u發(fā)送到節(jié)點(diǎn)v的新消息都是節(jié)點(diǎn)u“綜合”自己的信息和其他節(jié)點(diǎn)發(fā)來的消息而成的，這可能造成新消息和舊消息之間勢能差值非常大，例如：u和v這對節(jié)點(diǎn)的勢能值是100，而v和w這對節(jié)點(diǎn)的勢能值僅僅是2；或者形成緊環(huán)，在消息傳遞過程中，當(dāng)然不希望傳遞順序太快形成環(huán)路，因為這意味著每個節(jié)點(diǎn)能收集到的消息非常少，容易造成自我增強(qiáng)，環(huán)越緊代表環(huán)路上包含的節(jié)點(diǎn)越少，傳遞的消息越來越失去價值；又或者是方向上的矛盾，例如：在隨機(jī)選擇更新順序的情況下，假設(shè)節(jié)點(diǎn)在本次迭代中是按照順時針方向傳遞消息，這個方向趨于讓兩個節(jié)點(diǎn)具有相同的值，但下次迭代的順序又是隨機(jī)選擇的，可能恰好讓這兩個節(jié)點(diǎn)按照逆時針順序傳遞消息，這個方向又趨于讓兩個節(jié)點(diǎn)具有不相同的值，這就造成了方向上的矛盾。這三種情況中的任何一種，都會使得震蕩發(fā)生，從而導(dǎo)致收斂過慢、精度下降等不好的現(xiàn)象。

為了避免震蕩的發(fā)生，本文針對上面提到的三個導(dǎo)致震蕩的原因提出了改進(jìn)，即每次傳遞消息時，采取權(quán)重的方式加入舊消息，也就是說一條新消息等于一定比例的舊消息加上一定比例的新消息，利用公式表達(dá)：

(5)

在進(jìn)行消息傳遞時，有兩種傳遞方式：一種是同步，一種是異步。同步更新方式的問題在于每次迭代使用的值都是上一次整體迭代之后的結(jié)果值，在新一輪迭代中，先計算出的“消息”值沒有立即得到使用，而是一直延遲到本輪迭代之后下一輪才投入使用，所以收斂速度非常地慢，每次收斂的消息數(shù)也比較少。

那么相反，考慮異步置信傳播算法，針對同步方式存在的問題，在異步迭代方式中，先計算出的消息立即投入使用，也就是說每次只計算一條消息，下一條需要被計算的消息能夠立即使用剛剛計算出的所有新的消息，這樣一次迭代使用的所有消息都是目前能得到的最新消息，每條消息所攜帶的信息非常豐富和及時，使得收斂速度變快，并且收斂的消息數(shù)量也會增多。

2 實驗

為了驗證提出方法的有效性，本文分別在5個真實網(wǎng)絡(luò)上進(jìn)行了實驗，關(guān)于網(wǎng)絡(luò)的詳細(xì)數(shù)據(jù)見表1。本文采用蘭德指數(shù)(Rand Index, RI)[18]和歸一化互信息(Normalized Mutual Information, NMI)[19]這兩個指標(biāo)對實驗結(jié)果進(jìn)行評價。

表1 數(shù)據(jù)集介紹Tab. 1 Introduction of datasets

2.1 實驗一

實驗一針對解決震蕩問題提出的改進(jìn)，所以都采用同步消息傳遞方式。實驗方法是控制λ的范圍從0～0.9，每次增加0.1，例如：λ=0.6表示60%的舊消息加上40%的新消息；λ=0代表沒有改進(jìn)。λ的值不能取1，因為取1表示完全都是上次迭代的消息，這本身沒有意義。這里設(shè)置λ=0.5，原因可見后面的2.3節(jié)參數(shù)分析。實驗結(jié)果見表2。很明顯，改進(jìn)后的算法無論是在速度上還是精度上都呈現(xiàn)出了更好的結(jié)果，這說明本文對于產(chǎn)生震蕩問題的原因總結(jié)得比較好，采取的改進(jìn)公式也起到了相當(dāng)好的作用。

表2 不同λ值時，改進(jìn)算法性能Tab. 2 Improved algorithm performance under differfent λ

2.2 實驗二

實驗二針對第二點(diǎn)改進(jìn)，也就是異步同步對比實驗，控制λ=0。異步或者是同步針對的都是置信傳播算法中的消息傳遞方式來說的，從理論上講，這兩種不同的消息傳遞方式會影響算法的收斂速度和精度，并且異步置信傳播算法在多數(shù)情況下應(yīng)該優(yōu)于同步置信傳播算法。實驗結(jié)果見表3。

表3 采用同步異步更新時算法性能Tab. 3 Performace with synchronous vs asynchronous update ways

2.3 參數(shù)分析

實驗測試了參數(shù)λ對于網(wǎng)絡(luò)的影響，正如之前提到的，λ的取值從0～0.9，每次增加0.1，這里忽略λ=0的情況，因為其代表沒有改進(jìn)，和參數(shù)分析無關(guān)。由于不同網(wǎng)絡(luò)趨于展現(xiàn)出相同的結(jié)果趨勢圖，所以這里選取3個網(wǎng)絡(luò)(空手道俱樂部網(wǎng)絡(luò)、海豚社交網(wǎng)絡(luò)和單詞連接詞網(wǎng)絡(luò))為代表。對于這3個網(wǎng)絡(luò)本文分別使用歸一化互信息(NMI)和蘭德指數(shù)(RI)兩種評價指標(biāo)。如圖3(a)所示，在λ取值為0.2～0.6，精度沒有發(fā)生變化，結(jié)果曲線表現(xiàn)得完全穩(wěn)定，在λ取值過低或者過高時，精度值出現(xiàn)了大幅度的下降，這是容易理解的，因為λ代表了混入舊消息的比例，對于某些網(wǎng)絡(luò)，舊消息的比例過大或者過小都會導(dǎo)致結(jié)果的失衡。如圖3(b)和(c)所示，λ在所有取值范圍內(nèi)都使得兩種評價指標(biāo)下的精度表現(xiàn)出趨于穩(wěn)定的結(jié)果，雖然有小幅度的波動，但是沒有非常大的影響，所以本文可以選擇一般的參數(shù)值。如設(shè)置λ=0.5，進(jìn)行實驗一。

3 結(jié)語

在眾多社團(tuán)發(fā)現(xiàn)技術(shù)中，置信傳播算法是一類非常經(jīng)典的概率圖模型推理算法，具有很強(qiáng)的全局尋優(yōu)能力，但該算法在迭代過程中會產(chǎn)生強(qiáng)烈的震蕩，從而影響收斂速度和算法精度。通過大量研究，發(fā)現(xiàn)了導(dǎo)致震蕩的3個主要原因，并且針對這3個原因提出了改進(jìn)措施：為了達(dá)到收斂平滑，以權(quán)重的形式加入前一次迭代的消息，同時通過參數(shù)的調(diào)節(jié)，平衡新舊消息。此外，本文指出同步消息傳遞方式存在的問題，并創(chuàng)新性的提出異步消息傳遞方式，它能夠修正同步方式存在的問題，增加收斂消息數(shù)量，對算法的速度和精度均能產(chǎn)生顯著的影響。針對這兩點(diǎn)改進(jìn)本文在5個真實網(wǎng)絡(luò)上進(jìn)行了實驗，實驗結(jié)果表明兩個改進(jìn)都取得了顯著效果。

圖3 參數(shù)λ對精度的影響Fig. 3 Effect of parameters λ on accuracy

為了能使改進(jìn)后的算法具有更加廣泛的應(yīng)用范圍，一些問題值得進(jìn)行更深入的探討，譬如：1)如何進(jìn)一步提高算法速度，使得其能夠在大規(guī)模網(wǎng)絡(luò)上準(zhǔn)確劃分社團(tuán)；2)現(xiàn)在的算法需要預(yù)先確定社團(tuán)個數(shù)K，這是一個比較大的局限，如何自動并準(zhǔn)確地確定K，是一個很有價值的挑戰(zhàn)。

References)

[1] 楊博,劉大有,金弟.復(fù)雜網(wǎng)絡(luò)聚類方法[J].軟件學(xué)報, 2009, 20(1): 54-66.(YANG B, LIU D Y, JIN D. Clustering methods of complex networks[J]. Journal of Software, 2009, 20(1): 54-66.)

[2] 李慧嘉,嚴(yán)冠,劉志東,等.基于動態(tài)系統(tǒng)的網(wǎng)絡(luò)社團(tuán)線性探測算法[J].中國科學(xué):數(shù)學(xué), 2017, 47(2): 241-256.(LI H J, YAN G, LIU Z D, et al. Linear community detection algorithm based on dynamic network system[J]. Science China: Mathematics, 2017, 47(2): 241-256.)

[3] FORTUNATO S. Community detection in graphs[J]. Physics Reports, 2010, 486(3): 75-174.

[4] JIA S W, GAO L, GAO Y, et al. Defining and identifying cograph communities in complex networks[J]. New Journal of Physics, 2015, 17(1): 013044.

[5] YANG L, CAO X C, HE D X, et al. Modularity based community detection with deep learning[C]// Proceedings of the 25th International Joint Conference on Artificial Intelligence. Menlo Park, CA: AAAI Press, 2016:2252-2258.

[6] FANUEL M, ALAZ C M, SUYKENS J A. Magnetic eigenmaps for community detection in directed networks[J]. Physical Review E, 2016, 95(2):022302.

[7] ANDREI B, KHLOPOTINE A, SATHANUR V J. Optimized parallel label propagation based community detection on the Intel(R) Xeon Phi(TM) architecture[C]// Proceedings of the 27th International Symposium on Computer Architecture and High Performance Computing. Piscataway, NJ: IEEE, 2016: 9-16.

[8] WANG S F, GONG M G, SHEN B, et al. Deep community detection based on memetic algorithm[C]// Proceedings of the 2015 IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2015: 648-655.

[9] 黃立威,李彩萍,張海粟,等.一種基于因子圖模型的半監(jiān)督社區(qū)發(fā)現(xiàn)方法[J].自動化學(xué)報, 2016, 42(10): 1520-1531.(HUANG L W, LI C P, ZHANG H S, et al. A semi-supervised community detection method based on factor graph model[J]. Acta Automatica Sinica, 2016, 42(10): 1520-1531.)

[10] ZHANG H Y, ZHAO T, IRWIN K, et al. Modeling the homophily effect between links and communities for overlapping community detection[EB/OL].[2016- 11- 20]. http://www.ijcai.org/Proceedings/16/Papers/554.pdf.

[11] JIN D, WANG H C, DANG J W, et al. Detect overlapping communities via modeling and ranking node popularities[C]// Proceedings of the 30th AAAI Conference on Artificial Intelligence. Menlo Park, CA: AAAI Press, 2016:172-178.

[12] NEWMAN M E J. Communities, modules and large-scale structure in networks[J]. Nature Physics, 2012, 8(1): 25-31.

[13] EWMAN M E J, SLY A. Stochastic block models and reconstruction[EB/OL].[2016- 11- 20]. http://www.stat.berkeley.edu/～jneeman/monesl12.pdf.

[14] DECELLE A, KRZAKALA F, MOORE C, et al. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications[J]. Physical Review E: Statistical Nonlinear and Soft Matter Physics, 2011, 84(2): 066106.

[15] LANCICHINETTI A, RADICCHI F, RAMASCO J. Statistical significance of communities in networks[J]. Physical Review E: Statistical Nonlinear and Soft Matter Physics, 2010, 81(2):046110.

[16] ABBE E, BANDEIRA A S, HALL G. Exact recovery in the stochastic block model[J]. IEEE Transactions on Information Theory, 2015, 62(1):471-487.

[17] LAKEMEYER G, NEBEL B. Exploring Artificial Intelligence in the New Millennium[M]. San Francisco, CA: Morgan Kaufmann Publishers Inc, 2003: 239.

[18] STEINLEY D. Properties of the Hubert-Arable adjusted rand index[J]. Psychological Methods, 2004, 9(3): 386-396.

[19] DANON L, DIAZ G A, DUCH J, et al. Comparing community structure identification[EB/OL].[2016- 11- 20]. http://arxiv-web.arxiv.org/pdf/cond-mat/0505245.

This work is partially supported by the National Natural Science Foundation of China (61303110, 61502334), the Peiyang Scholar-Elite Scholar Program of Tianjin University (2017XRG- 0016).

YOUXinxin, born in 1993, M. S. candidate. Her research interests include community detection, data mining.

GEMeng, born in 1992, M. S. candidate. His research interests include deep learning, community detection.

Communitydetectionalgorithmbasedonbeliefpropagationincomplexnetworks

YOU Xinxin, GE Meng*

(SchoolofComputerSoftware,TianjinUniversity,Tianjin300350,China)

The classical Belief Propagation (BP) algorithm can inference the marginal probability distributions and maximum likelihood probability of all nodes by a finite number of iterations. However, BP algorithm always causes strong oscillation in the iterative process, and it uses synchronous way to pass messages which seriously affects the convergence rate. According to a lot of research, three main factors which caused oscillation were found: strong energy, close loop and contradictory direction. Furthermore, a new update formula and an asynchronous way of passing messages were proposed to solve above two problems. Stochastic block model was used to model the network generation process and the result of community division was obtained by using classical expectation maximization algorithm combined with BP. Extensive experimental results on real-world networks show the superior performance of the new method over the state-of-the-art approaches.

complex network; community detection; Belief Propagation (BP); stochastic block model; convergence rate

2017- 05- 16;

2017- 06- 07。

國家自然科學(xué)基金資助項目(61303110, 61502334)；天津大學(xué)北洋學(xué)者·青年骨干教師項目(2017XRG-0016)。

尤心心(1993—)，女，山東樂陵人，碩士研究生，主要研究方向：社團(tuán)發(fā)現(xiàn)、數(shù)據(jù)挖掘； 葛檬(1992—)，男，浙江臺州人，碩士研究生，主要研究方向：深度學(xué)習(xí)、社團(tuán)發(fā)現(xiàn)。

1001- 9081(2017)11- 3115- 04

10.11772/j.issn.1001- 9081.2017.11.3115

(*通信作者電子郵箱gemengtju@163.com)

TP393

A