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

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

1 引言

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

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

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

2 相關(guān)工作

2.1 影響力擴散

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

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

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

Ei=lg(1+di)

(1)

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

(2)影響力擴散規(guī)則。

假設(shè)節(jié)點vi的初始影響力為Ei，其鄰居節(jié)點集為Φi。

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

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

(2)

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

(3)

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

(4)

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

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

(5)

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

2.2 自動編碼器

近幾年深度學(xué)習(xí)成功應(yīng)用于許多領(lǐng)域，而自動編碼器(Auto-encoder)[11]是人工神經(jīng)網(wǎng)絡(luò)的一種，常用于表征學(xué)習(xí)和特征降維，屬于非監(jiān)督學(xué)習(xí)。自動編碼器是一個3層的神經(jīng)網(wǎng)絡(luò)，由編碼和解碼2部分組成，其結(jié)構(gòu)如圖1所示。

Figure 1 Structure of auto-encoder圖1 自動編碼器的結(jié)構(gòu)

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

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

yi=f(Wxi+b)

(6)

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

(7)

(8)

2.3 森林編碼器

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

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

算法1EForest算法前向編碼

輸入：隨機森林T棵樹，數(shù)據(jù)Aa。

輸出:Xenc。

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

2.foreachiinT

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

3.end

4.returnXenc

3 DA-EF算法

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

Figure 2 Structure of DA-EF圖2 DA-EF算法結(jié)構(gòu)

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

Figure 3 Community detection process圖3 社區(qū)發(fā)現(xiàn)流程

算法2DA-EF算法

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

輸出：社區(qū)劃分結(jié)果C={C1,C2,…,Ck}。

1.ForeachiinV

2.ForeachjinV

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

4. 得到相似度矩陣As;

5.X1=As;

6.ForeachminL

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

8. 輸入特征矩陣Xm;

9. 通過優(yōu)化式(8)訓(xùn)練自動編碼器；

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

11.Xj+1=Yj;

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

13. 由算法1得出At；

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

4 實驗結(jié)果與分析

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

4.1 評價指標

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

(9)

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

標準互信息NMI是在已知網(wǎng)絡(luò)真實社區(qū)劃分的情況下，對實驗劃分結(jié)果的精確度進行評價，其函數(shù)表達如下所示：

NMI(A,B)=

(10)

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

4.2 人工合成數(shù)據(jù)集

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

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

Table 1 Main information of the LFR networks表1 LFR網(wǎng)絡(luò)主要信息

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

Figure 4 Comparison of algorithm results on LFR networks圖4 LFR網(wǎng)絡(luò)上算法對比實驗

表2 LFR網(wǎng)絡(luò)的DA-EF結(jié)構(gòu)

4.3 真實數(shù)據(jù)集

本文的真實數(shù)據(jù)選取了Football[18]、Polbooks[19]、Jazz[20]和Facebook[21]。Football是美國NCAA足球聯(lián)賽的對陣關(guān)系網(wǎng)絡(luò)；Polbooks是書店出售政治書籍聯(lián)系網(wǎng)絡(luò)；Jazz是爵士音樂家合作關(guān)系網(wǎng)絡(luò)；Facebook是用戶的朋友圈的關(guān)系網(wǎng)絡(luò)。真實網(wǎng)絡(luò)的信息如表3所示，包括網(wǎng)絡(luò)的節(jié)點數(shù)、邊和社區(qū)數(shù)目，模型結(jié)構(gòu)同LFR。

Table 3 DA-EF structure of real networks表3 真實網(wǎng)絡(luò)的DA-EF結(jié)構(gòu)

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

5 算法DA-EF有效性探討

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

5.1 森林編碼器的影響

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

Table 4 Comparison of algorithms results on real networks表4 真實網(wǎng)絡(luò)上算法結(jié)果對比

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

5.2 自動編碼器的層數(shù)影響

實驗數(shù)據(jù)為LFR編號為2，混合參數(shù)u為0.3的網(wǎng)絡(luò)，自動編碼器的結(jié)構(gòu)為3000-2000-1600-1000-500。實驗結(jié)果如圖6所示，橫軸Deep level表示DA-EF中自動編碼器的層數(shù)。

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

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

5.3 相似度指標的影響

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

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

5.4 算法優(yōu)勢的結(jié)論

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

6 結(jié)束語

本文提出的DA-EF算法，將深度神經(jīng)網(wǎng)絡(luò)中的自動編碼器與森林編碼器組成二級級聯(lián)模型，應(yīng)用于復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)，尤其適用于大規(guī)模網(wǎng)絡(luò)。

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