尤心心，葛 檬

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

基于置信傳播的復雜網絡社團發(fā)現(xiàn)算法

尤心心，葛 檬*

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

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

復雜網絡；社團發(fā)現(xiàn)；置信傳播；隨機塊模型；收斂速度

0 引言

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

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

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

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

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

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

1 方法

1.1 問題描述

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

取對數的完全數據似然公式是：

(1)

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

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

(2)

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

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

1.2 震蕩減弱

(3)

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

(4)

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

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

(5)

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

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

2 實驗

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

表1 數據集介紹Tab. 1 Introduction of datasets

2.1 實驗一

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

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

2.2 實驗二

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

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

2.3 參數分析

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

3 結語

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

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

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

References)

[1] 楊博,劉大有,金弟.復雜網絡聚類方法[J].軟件學報, 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] 李慧嘉,嚴冠,劉志東,等.基于動態(tài)系統(tǒng)的網絡社團線性探測算法[J].中國科學:數學, 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].自動化學報, 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。

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

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

1001- 9081(2017)11- 3115- 04

10.11772/j.issn.1001- 9081.2017.11.3115

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

TP393

A