基于深度編碼器的復雜網絡社區發現算法*

張士進，張 勝，田紀彪，吳志強，戴維凱

(南昌航空大學信息工程學院,江西 南昌 330063)

1 引言

復雜網絡是復雜系統的抽象，網絡中的節點是復雜系統中的個體，節點之間的邊則是系統中個體之間按照某種規則自然形成或人為構造的一種關系。隨著對復雜網絡的不斷深入研究，學者們發現復雜網絡具有多種特性，如無標度特性、小世界特性、分形特性和社區結構特性等。其中，社區結構的研究有利于理解復雜網絡構成的特點，具有重要的應用價值，如社交網絡的精準推薦、電力網絡的最佳規劃和蛋白質互作網絡的功能預測等。復雜網絡不是將具有相同屬性的節點隨機地連接在一起，而是將不同屬性節點組合在一起。具有社區結構的復雜網絡是由若干社區組成，而社區是具有相同特性的節點所組成的集合，社區內部的節點之間的連接比較緊密，而不同社區之間的節點連接卻相對稀疏[1]。社區發現是找出一個給定的復雜網絡的社區結構的過程，它是復雜網絡分析中的一種基本手段。

復雜網絡的社區發現起源于圖論與模式識別相關理論，而Newman和Girvan的研究成果使得社區發現成為一個研究熱點。社區發現能夠揭示復雜網絡中節點之間的交互關系，大量的研究人員嘗試從不同角度探究社區結構，其算法可以分為基于圖分割的算法[2]、基于聚類的算法[3]、基于網絡動力學特性的算法[4]和基于目標函數的優化算法[5]等。近幾年將深度學習用于解決大規模復雜網絡的社區發現成為熱點，雖然研究人員提出了很多基于深度學習的模型，但存在模型復雜性高和參數過多導致普適性差的問題。Wang等[6]提出DA-ELM(Deep Auto-encoded Extreme Learning Machine)算法，使用多層自動編碼器和極限學習機對相似矩陣表征學習，提高了精確度和穩定性，但訓練耗時過高。Jia等[7]提出CommunityGAN(Community detection with Generative Adversarial Nets)算法，利用對抗網絡優化節點隸屬社區強度，使生成器與判別器之間相互競爭，二者交替迭代提高了精確度，但參數多造成普適性差。Li等[8]提出CD-ERL(Community Detection algorithm based on Edge Representation Learning)算法，通過對網絡的邊進行表征學習，利用邊聚類算法轉化成節點的重疊社區劃分，提高了精確度，但穩定性不高。尚敬文等[9]提出CoDDA(Community Detection algoritym based on Deep sparse Autoencoder)算法，利用多層稀疏自動編碼器對s-jump相似矩陣降維并進行表征學習，用K-means聚類，提高了精確度，但算法的參數不易選擇，普適性較差。Zhang等[10]利用多層的譜聚類對網絡的社區進行劃分，該算法的精度比單層的要高，但層數是一個不穩定參數。

為解決上述算法的不足，本文提出一種新的算法DA-EF(Deep Auto-encoder and EForest)和用于度量節點之間相似度的影響力擴散指標。影響力擴散是對節點之間不存在連邊的情況，賦予節點網絡的局部信息，使其更全面地表征網絡。本文算法是將多層自動編碼器級聯一層森林編碼器，用于復雜網絡的社區發現，其貢獻有2點：(1)提出了用于度量節點之間相似度的影響力擴散指標，可以更加完整地表示網絡；(2)提出了DA-EF算法，級聯的森林編碼器在保持神經網絡模型的深度的同時，大幅降低了模型的時間復雜度。實驗表明，該算法的表征學習能力優異，社區結構劃分更加準確。

2 相關工作

2.1 影響力擴散

若一個網絡是由n個節點和m條邊組成，那么可以簡述為：網絡G=(V,E)，節點集合V={v1,v2,…,vn}，邊集合E={e1,e2,…,em}。一般用來刻畫網絡中節點間信息的是鄰接矩陣A=[aij]n×n，其中元素aij是表示節點之間有無連邊，如果節點vi與節點vj有連邊，則aij=1；否則aij=0。鄰接矩陣只能表示網絡中具有連邊的節點信息，然而網絡中沒有連邊的節點之間同樣具有一定的相似度，因此，將節點局部信息引入到鄰接矩陣，以更加全面地刻畫網絡，本文提出影響力擴散指標，用于度量節點之間的相似度。影響力擴散是將網絡中節點的重要程度作為節點的影響力，將其影響力擴散到其鄰居節點，由鄰居節點再去影響其沒有輻射到的鄰居節點，直到影響力衰減到某個閾值(假定沒有影響作用)為止，從而計算節點之間的相似度。

(1)節點的初始影響力。

網絡中節點重要程度可以用節點度表示，為了避免網絡中某些節點度過大而造成影響力失衡，采用對數的形式計算任意節點的初始影響力：

Ei=lg(1+di)

(1)

其中,di表示節點vi的度，節點影響力Ei>0。

(2)影響力擴散規則。

假設節點vi的初始影響力為Ei，其鄰居節點集為Φi。

①若|Φi|=1，即節點vi只有1個鄰居節點，那么此節點稱為跟隨節點(無影響力)，其鄰居節點獲得全部影響力Ei，但不繼續擴散。

②若|Φi|>1，節點vi至少存在2個鄰居節點，而且認為該節點能夠直接對鄰居節點造成影響，但影響力大小由2個部分組成，一個是所有鄰居節點都相同的基礎影響力，保證具有連邊的節點存在影響；另一個是增量影響力，依據節點的共同鄰居節點數增加影響力的值，使聯系緊密的節點之間影響更大，保證節點之間影響力的差異化。基礎影響力的定義如式(2)所示：

(2)

從式(2)可知，鄰居節點的基礎影響力之和為初始影響力的一半，那么節點vi的另外一半影響力值作為增量影響力。增量影響力的引入，不會使節點受到的影響力的值大于1。增量影響力的定義如式(3)所示：

(3)

其中Φj是節點vj的鄰居節點集，且vj∈Φi，則節點vi傳遞到鄰居節點的影響力為：

(4)

(3)影響力擴散終止條件。

隨著影響力不斷擴散，其值將越來越小，那么在網絡中起到的作用也是越來越小。設定一個影響力閾值作為影響力元，當節點接收的影響力小于閾值時，終止傳遞。

(5)

其中,β是影響因子，取值為(0,1)。

2.2 自動編碼器

近幾年深度學習成功應用于許多領域，而自動編碼器(Auto-encoder)[11]是人工神經網絡的一種，常用于表征學習和特征降維，屬于非監督學習。自動編碼器是一個3層的神經網絡，由編碼和解碼2部分組成，其結構如圖1所示。

Figure 1 Structure of auto-encoder圖1 自動編碼器的結構

從第1層到第2層是表征學習和特征降維的編碼過程，將輸入的n維數據映射到h維(n>h)；第2層到第3層是重構原始數據的解碼過程。在自動編碼器中，具體的訓練過程如下所示：

由Salton得到的相似度矩陣As作為自動編碼器的輸入，As=[bij]n×n=(x1,x2,…,xn)T，其中xi=(bi1,bi2,…,bin),是相似度矩陣的第i個節點對應的向量，將向量xi作為自動編碼器的第i個輸入向量。將xi輸入到一個具有h個神經元的編碼層，通過式(6)得到編碼 。

yi=f(Wxi+b)

(6)

其中，f是編碼器的sigmoid激活函數，W∈Rh×n是權重矩陣，b∈Rh×1是編碼層的偏置向量。

(7)

(8)

2.3 森林編碼器

研究表明[15]，森林編碼器EForest對原始特征的表征學習能力比自動編碼器強，重構誤差更小，因此本文選擇森林編碼器對低維相似度矩陣做更深一層的學習。森林編碼器是由編碼和解碼2部分組成，其具體操作是基于決策樹產生的。

前向編碼操作是給定一個有T棵樹的隨機森林，而編碼過程就是森林形成過程，將輸入數據送到每棵樹的根節點，并計算每棵樹，得到其所屬的葉節點，最后返回一個T維向量，這個T維向量的每一項是每棵樹中求到的葉節點在樹中的編號。反向解碼操作是重構的過程，將前向編碼得到的T維向量，以及從樹中得到T個決策規則，再根據這些規則得到最大完備規則MCR(Maximal-Com-patible Rule)，并利用MCR重構原始數據。DA-EF沒有利用森林編碼器中的解碼操作，限于篇幅對此不作詳細介紹。

算法1EForest算法前向編碼

輸入：隨機森林T棵樹，數據Aa。

輸出:Xenc。

1.Xenc=zero[T,1];//初始化

2.foreachiinT

Xenc[i] =Forest.Tree[i].encode(Aa)/*第i棵樹的葉子編號*/

3.end

4.returnXenc

3 DA-EF算法

深度神經網絡中自動編碼器(Auto-encoder)能夠將數據從高維映射到低維，從而達到降低維度的效果，同時也能對原始數據進行表征學習。而社區劃分對數據特征的依賴度很高，因此，本文在自動編碼器之后級聯一層森林編碼器，主要目的是再次提取高階特征。通過建立一個由多層自動編碼器和森林編碼器組成的二級級聯模型，本文提出DA-EF算法，如圖2所示，該算法對相似度矩陣As降維和表征學習，能夠更好地對網絡進行社區劃分。DA-EF算法結構由多層自動編碼器和森林編碼器組成，圖2中自動編碼器的層數是2，而算法中自動編碼器的層數是根據復雜網絡的規模確定的，相關實驗在第5.2節探討。自動編碼器的輸入是根據影響力擴散相似度指標得到的節點間的相似度矩陣As，經過多層自動編碼器處理之后，得到一個低維高階特征矩陣Aa，而Aa作為森林編碼器的輸入，提取其高階特征，最后得到輸出矩陣At。

Figure 2 Structure of DA-EF圖2 DA-EF算法結構

從復雜網絡到社區劃分主要分4步：表征網絡鄰接矩陣A；計算相似度矩陣As;降低維度和表征學習；得到低維高階特征矩陣At;利用聚類算法劃分社區集合C，其社區發現流程如圖3所示。本文提出的用于計算節點間相似度的影響力擴散指標，利用網絡中節點的鄰居節點的局部信息，增強了節點相似度的穩定性和準確性；提出DA-EF算法對相似度矩陣進行特征降維和表征學習，得到一個低維高階特征矩陣，有利于提高大規模網絡的社區發現精確度；K-means具有精確度高和時間復雜度低的優點，本文選擇它對網絡的低維高階特征矩陣進行聚類，得到社區劃分結果。

Figure 3 Community detection process圖3 社區發現流程

算法2DA-EF算法

輸入：網絡圖G=(V,E)的鄰接矩陣A，社區個數k，影響因子β，深度自動編碼器的層數L，森林編碼器中T棵樹，每層節點數h={h1,h2,…,hL}。

輸出：社區劃分結果C={C1,C2,…,Ck}。

1.ForeachiinV

2.ForeachjinV

3. 根據式(4)計算節點的相似度;

4. 得到相似度矩陣As;

5.X1=As;

6.ForeachminL

7. 建立一個自動編碼器；

8. 輸入特征矩陣Xm;

9. 通過優化式(8)訓練自動編碼器；

10. 得到隱藏層的表示Yj;

11.Xj+1=Yj;

12. 將XL矩陣作為森林編碼器的輸入；

13. 由算法1得出At；

14. 對低維高階特征矩陣At運行K-means，聚類得到社區劃分結果C={C1,C2,…,Ck}。

4 實驗結果與分析

為了驗證本文算法DA-EF的有效性，將其與其它算法CoDDA[9]、K-means[13]和DA-EML[6]進行實驗對比，實驗的數據集由人工合成數據集和真實數據集組成，而評價標準是模塊度Q(Modurity)[14]和標準互信息NMI(Normalized Mutual Information)[15]。本文的實驗環境配置：Windows 10操作系統，Intel core i7-7800X CPU，128 GB；編程語言是Python 3.6，編譯工具為Pycharm community 2018。

4.1 評價指標

模塊度自被Newman等[16]提出之后，就一直作為社區劃分評價標準之一，能夠在不知網絡真實社區劃分的情況下對劃分結果做出客觀的評價。模塊度的定義如下所示：

(9)

其中，用vi和vj表示網絡中不同的節點；n為網絡節點總數；m為網絡總邊數；aij為圖的鄰接矩陣元素；ki和kj分別為節點vi和vj的度；δi和δj分別為節點vi和vj所在的社區編號，若δi=δj，則c(δi,δj)=1,否則c(δi,δj)=0，Q值越大說明社區劃分得越準確。

標準互信息NMI是在已知網絡真實社區劃分的情況下，對實驗劃分結果的精確度進行評價，其函數表達如下所示：

NMI(A,B)=

(10)

其中，CA(CB)是A(B)劃分的社區數目；Ci和Cj分別表示第i個和第j個社區的節點數目；Ci ·是混淆矩陣C的第i行元素之和；C·j是第j列元素之和；n是網絡節點數目。當A=B時，NMI(A,B)=1，A和B劃分結果相同；當NMI=0時，A和B的劃分結果完全相反，其值越大越接近真實社區劃分。

4.2 人工合成數據集

本文使用的人工合成網絡是LFR benchmark[17]，由于該網絡的節點度和社區大小都是可調節的，而且符合冪律分布，因此生成的網絡更加接近真實網絡。網絡的參數和算法參數如表1所示，網絡節點數分別是1 000， 3 000和5 000，其中k是網絡節點平均度,maxk是最大節點度,mink是社區最小節點數,maxc是社區最大節點數,u是網絡混合參數(Mixing parameter)，其值越大網絡的社區結構越模糊，通過調節該參數值對網絡社區結構進行改變。

DA-EF算法的自動編碼器的層數以及每層節點數設置，如表2所示，譬如LFR編號為1的網絡，其算法結構為1000-800-650-600，其中1 000是輸入節點數，800是第1層自動編碼器隱藏層的節點數，650是第2層自動編碼器隱藏層節點數，600是森林編碼器中樹的棵數，其它網絡算法結構依此類推。

Table 1 Main information of the LFR networks表1 LFR網絡主要信息

DA-EF與K-means、DA-EML和CoDDA 3種算法進行對比，每個網絡都用模塊度Q、標準互信息NMI和運行時間Time作為評價標準。3個不同規模LFR網絡在3種評價標準下的實驗圖如圖4所示，實驗結果是重復實驗20次取得的平均值。DA-EF在3個網絡下的Q和NMI都是高于K-means和CoDDA算法的，而且隨著網絡的節點數增加，精確度下降的趨勢變慢，而且DA-EF、CoDDA和DA-EML的精確度明顯比K-means要高，說明自動編碼器對挖掘網絡深層信息是有效的；在運行時間上，DA-EF明顯比其它算法要低很多，而且優于同類算法CoDDA和DA-EML，體現出了本文算法的高效性。在人工合成數據的實驗中說明，本文提出的算法DA-EF精確度明顯提升，而且與同類算法相比運行時間更少，表明了算法的有效性和高效性。

Figure 4 Comparison of algorithm results on LFR networks圖4 LFR網絡上算法對比實驗

表2 LFR網絡的DA-EF結構

4.3 真實數據集

本文的真實數據選取了Football[18]、Polbooks[19]、Jazz[20]和Facebook[21]。Football是美國NCAA足球聯賽的對陣關系網絡；Polbooks是書店出售政治書籍聯系網絡；Jazz是爵士音樂家合作關系網絡；Facebook是用戶的朋友圈的關系網絡。真實網絡的信息如表3所示，包括網絡的節點數、邊和社區數目，模型結構同LFR。

Table 3 DA-EF structure of real networks表3 真實網絡的DA-EF結構

本文算法DA-EF在真實網絡上的對比實驗結果如表4所示，對比算法依然是K-means、DA-EML和CoDDA；評價指標是模塊度Q和運行時間Time。在Football網絡上，Q值最高的是DA-EML，其次是DA-EF，運行時間最少的是CoDDA；在Polbooks、Jazz和Facebook網絡中，DA-EF的Q值最大，運行時間也同樣相對較少，隨著網絡規模的增大，DA-EML和DA-EF運行時間增加速率明顯小于K-means與CoDDA的。實驗表明，DA-EF算法在真實數據集上精確度高，而且更加有利于大規模網絡的劃分。

5 算法DA-EF有效性探討

在人工合成數據集和真實數據集上的實驗表明，與其它算法相比，本文提出的DA-EF算法能提升社區劃分精確度。DA-EF算法是多層自動編碼器和森林編碼器組成的二級級聯結構，為計算網絡中節點間的相似度，本文提出了影響力擴散指標，下面將探討森林編碼器、自動編碼器的層數和影響力擴散指標對算法的影響。選擇LFR編號為2的數據網絡進行實驗。

5.1 森林編碼器的影響

DA-EF算法在多層自動編碼器的基礎上級聯了一層森林編碼器，研究表明[12]森林編碼器的重構誤差相比于循環神經網絡和卷積神經網絡要低，能夠更好地提取高階特征。因此，本文將森林編碼器應用到社區發現，并構造一個二級級聯模型，其不僅能夠實現降維和表征學習，還能避免森林編碼器對降維失真的問題。實驗結果如圖5所示，AE算法表示只有多層自動編碼器，沒有級聯森林編碼器，DA-EF是級聯了森林編碼器的算法。將AE與DA-EF進行對比，在評價標準NMI下，可以得出，在級聯森林編碼器之后，算法的精確度明顯得到了提高，森林編碼器的引入有積極效果。

Table 4 Comparison of algorithms results on real networks表4 真實網絡上算法結果對比

Figure 5 Impact of EForest encoder圖5 森林編碼器影響

5.2 自動編碼器的層數影響

實驗數據為LFR編號為2，混合參數u為0.3的網絡，自動編碼器的結構為3000-2000-1600-1000-500。實驗結果如圖6所示，橫軸Deep level表示DA-EF中自動編碼器的層數。

Figure 6 Layer number experiment of auto-encoder圖6 自動編碼器的層數實驗

從圖6中可以看出，當層數增加到2時，算法精確度達到最高；層數增加到3或4時，精確度都變得更低，因此，層數并不是越多越好，要根據網絡的規模選擇。當網絡規模在1 000以下時，選擇1層AE就能夠得到較好的結果，如真實數據集Football、Polbooks和Jazz上的結果；當網絡規模為1 000～5 000時，選擇2層AE，如真實數據集Facebook和LFR網絡；當網絡規模更大時，選擇的AE層數也就越多。AE層數對DA-EF算法具有一定的影響，合適的層數能夠提升社區劃分的精確度。

5.3 相似度指標的影響

使用DA-EF算法進行實驗，實驗數據與5.2節中一樣，相似度指標有s-jump、RA(Resource Allocation)[22]、Jaccard[23]、CN(Common Neighbors)[24]和影響力擴散，其評價指標為NMI和Q，實驗結果如圖7所示。每種指標都是同一種算法DA-EF，從圖7中可知，不同的相似度指標下，算法得到的劃分結果也不同，其中，RA指標是最差的，而CN和影響力擴散的精確度最好，影響力擴散對社區結構不明顯的網絡，也能得到較好的劃分結果。因此，本文提出的影響力擴散選擇指標，更有利于處理網絡結構不明顯的網絡。

Figure 7 Comparative experiment of similarity index圖7 相似度指標對比實驗

5.4 算法優勢的結論

在人工合成數據集和真實數據集上的實驗可知，DA-EF算法具有精確度高以及收斂快的優勢。同時，為了進一步探索該算法優勢的原因，對森林編碼器的引入、自動編碼器的層數和影響力擴散指標分別進行對比實驗。本文算法引入的森林編碼器提升了表征學習的能力，森林編碼器具有簡易的統計學習思維以及快速表征學習的特點，但對于從高維度映射到低維度的數據不敏感，所以將自動編碼器降維優勢和森林編碼器表征學習優勢進行結合。此外，森林編碼器不僅降低了自動編碼器的層數而且能夠提升算法收斂速度，即在保證網絡深度的同時，能夠降低算法的復雜度。影響力擴散指標保證了網絡信息的完整度和提供給模型的良好輸入數據。因此，該算法的優勢主要來自于森林編碼器和自動編碼器優勢互補以及對網絡良好的表示。

6 結束語

本文提出的DA-EF算法，將深度神經網絡中的自動編碼器與森林編碼器組成二級級聯模型，應用于復雜網絡的社區發現，尤其適用于大規模網絡。

為了更好地表征網絡，本文提出了影響力擴散相似度指標，增加節點之間沒有連邊的局部信息。首先，通過影響力擴散計算網絡中節點間的相似度，構成網絡的相似度矩陣；然后，利用DA-EF算法對其進行降維和表征學習，得到低維高階特征矩陣；最后，利用K-means算法聚類，得到網絡的社區劃分結果。經過與K-means、DA-EML和CoDDA算法在人工合成網絡LFR和真實數據集上的實驗對比表明，DA-EF算法具有精確度高和適合大規模復雜網絡的優點；同時對算法的性能分析實驗表明，森林編碼器的級聯形式具有積極作用，使用合適的自動編碼器的層數和相似度指標對算法的精確度有影響。DA-EF算法相比其它算法具有精確度高的優勢，但也存在算法參數和模型結構不易選取問題，森林編碼器和自動編碼器的結合會導致魯棒性較差的問題。下一步將對DA-EF算法作進一步優化，利用半監督學習解決這一問題。