馬玉磊，鐘瀟柔

(1.新鄉(xiāng)學院 繼續(xù)教育學院，河南 新鄉(xiāng) 453000；2.新鄉(xiāng)學院 計算機與信息工程學院，河南 新鄉(xiāng) 453000)

0 引 言

復雜網(wǎng)絡[1]具有無尺度性、高聚類系數(shù)以及小世界性的特點，常用于表達現(xiàn)實系統(tǒng)中客體之間的關(guān)系，在生物領域的蛋白質(zhì)網(wǎng)絡、無線通信領域的蜂窩網(wǎng)絡及計算機領域的社交網(wǎng)絡中具有很大的應用價值。社區(qū)性是復雜網(wǎng)絡的一個重要特性，社區(qū)內(nèi)客體的相似性與關(guān)聯(lián)性較高，社區(qū)間客體的相似性與關(guān)聯(lián)性則較低，社區(qū)檢測[2]是分析復雜網(wǎng)絡的一個重要步驟。

傳統(tǒng)的社區(qū)檢測算法主要包括基于啟發(fā)式與基于模塊度兩類算法。格文-紐曼算法[3]是一種經(jīng)典的基于啟發(fā)式的算法，自Newman提出模塊度的概念起，基于模塊度的社區(qū)檢測算法層出不窮，如模糊模塊度社區(qū)檢測算法[4]、局部模塊度社區(qū)檢測算法[5]。大多數(shù)基于模塊度的社區(qū)檢測算法核心思想是以網(wǎng)絡模塊度為目標函數(shù)，采用不同的啟發(fā)式算法對模塊度進行優(yōu)化，提高社區(qū)劃分的質(zhì)量，其中蟻群算法[6]、多目標演化算法[7]以及凸優(yōu)化算法[8]均取得了良好的效果。

近年來，深度學習技術(shù)被成功用于復雜網(wǎng)絡的社區(qū)檢測任務。文獻[9]利用多層自編碼器與森林編碼器構(gòu)成二級級聯(lián)模型，對相似度矩陣進行降維和表征學習處理，最終使用K-means得到準確的社區(qū)劃分結(jié)果。文獻[10]采用基于s跳的方法對網(wǎng)絡圖的鄰接矩陣進行預處理，采用K-means算法對低維特征矩陣進行聚類得到網(wǎng)絡社區(qū)結(jié)構(gòu)。雖然深度學習具有較強的感知能力，能提取豐富的網(wǎng)絡拓撲結(jié)構(gòu)特征，但深度學習缺乏一定的決策能力，導致通過深度學習識別的社區(qū)邊界準確性不足?？紤]強化學習[11]具有較強的自適應決策能力，因此將深度學習與強化學習結(jié)合，出現(xiàn)了深度強化學習模型[12]。目前，深度強化學習在交通信號控制[13]、路由策略決策[14]以及功能鏈遷移[15]等任務上取得了突出的效果，在多個領域中的性能優(yōu)于基于啟發(fā)式的學習算法。

受此啟發(fā)，本文借助深度強化學習為復雜網(wǎng)絡的社區(qū)檢測問題提出新的解決思路。為了在復雜網(wǎng)絡社區(qū)檢測的效率與準確性之間取得平衡，設計了兩階段的社區(qū)檢測框架。第一階段基于網(wǎng)絡拓撲結(jié)構(gòu)初始化社區(qū)結(jié)構(gòu)，第二階段基于深度強化學習對網(wǎng)絡社區(qū)結(jié)構(gòu)進行微調(diào)與優(yōu)化，利用深度強化學習強大的感知能力與決策能力提高社區(qū)結(jié)構(gòu)的準確性。本文的主要貢獻有以下3點：①提出新的相似性度量指標，該指標度量了節(jié)點在網(wǎng)絡拓撲結(jié)構(gòu)上的相似性；②將深度強化學習模型應用于社區(qū)檢測問題，采用經(jīng)驗重復機制增強神經(jīng)網(wǎng)絡的收斂穩(wěn)定性；③提出新的社區(qū)局部優(yōu)化算子，改善社區(qū)邊界劃分的準確性。本文算法的兩個階段均為無監(jiān)督學習，通過深度強化學習對不同規(guī)模與結(jié)構(gòu)特點的網(wǎng)絡均能進行較好的感知與決策，因此具有較好的可擴展性。

1 系統(tǒng)框架設計

將復雜網(wǎng)絡建模為圖，表示為G=(V，E)， 其中V與E分別為圖的節(jié)點集與連接集，社區(qū)發(fā)現(xiàn)問題可描述為將G化分成若干個子圖 {G1，G2，…，Gn}， 子圖內(nèi)節(jié)點間的相關(guān)性較高，而子圖之間節(jié)點的相關(guān)性較低。

為了加快復雜網(wǎng)絡社區(qū)檢測的效率，本文采用兩階段的社區(qū)檢測框架，社區(qū)檢測流程如圖1所示。第一階段基于網(wǎng)絡拓撲結(jié)構(gòu)初始化社區(qū)結(jié)構(gòu)，該階段根據(jù)鄰域度方差檢測網(wǎng)絡中的候選社區(qū)中心，然后基于相似性進行標簽傳播并建立網(wǎng)絡的初始化社區(qū)。第二階段基于深度強化學習對網(wǎng)絡社區(qū)結(jié)構(gòu)進行微調(diào)與優(yōu)化，利用深度強化學習強大的感知能力與決策能力提高社區(qū)結(jié)構(gòu)的準確性。

圖1 基于深度強化學習的社區(qū)檢測流程

2 復雜網(wǎng)絡的社區(qū)初始化

2.1 候選社區(qū)中心估計

為了識別網(wǎng)絡中的中心節(jié)點，計算每個節(jié)點在其鄰域內(nèi)的度數(shù)方差，稱為鄰域方差(neighbor variance，NV)。鄰域方差(NV)的計算方法定義為

(1)

輸入網(wǎng)絡的實例如圖2(a)所示，估計的候選社區(qū)中心如圖2(b)所示。

圖2 社區(qū)中心

候選社區(qū)中心估計步驟如下：

步驟1 計算網(wǎng)絡G每個節(jié)點的NV值保存于向量HV中，將HV的元素按數(shù)值降序排列。

步驟2 將第1個節(jié)點(HV值最高)作為一個候選社區(qū)中心。

步驟3 遍歷HV的每個節(jié)點，計算當前節(jié)點與候選社區(qū)中心之間的平均距離，如果兩者之間的距離大于網(wǎng)絡的平均距離，那么認為當前節(jié)點為另一個候選社區(qū)中心，否則為普通節(jié)點。

平均距離的計算方法如下

(2)

式中：d(u，v) 為節(jié)點u與v之間的最短路徑，V為網(wǎng)絡的節(jié)點數(shù)量。

2.2 節(jié)點相似性評估

2.2.1 網(wǎng)絡結(jié)構(gòu)相似性度量

本文提出節(jié)點相似性度量方法，該方法在網(wǎng)絡拓撲結(jié)構(gòu)上評估節(jié)點間的相似性。該度量方法基于兩點理由而來：①兩個節(jié)點的鄰域結(jié)構(gòu)越相似，兩者的相似性應當越高；②兩個節(jié)點包含的共同鄰居數(shù)量越多，兩者的相似性應當越高。本文分別提出了鄰域結(jié)構(gòu)相似性與共同鄰居數(shù)量兩個度量方法。

(1)鄰域結(jié)構(gòu)相似性

首先，計算節(jié)點vi與其鄰居節(jié)點的度數(shù)差值，計算方法如下

(3)

式中：vi表示目標節(jié)點，δ()函數(shù)計算節(jié)點的度數(shù)，vm為vi的鄰居節(jié)點，即vm∈N(vi)，k為vi的鄰居數(shù)量，m與i均為節(jié)點的索引。

圖3(a)所示是網(wǎng)絡實例的NSI計算結(jié)果，NSI(vi)=|5-4|+|4-4|=1，NSI(vj)=|5-3|+|5-4|+|5-5|=3。

圖3 節(jié)點相似性度量的實例

然后，計算節(jié)點vi與vj之間的度數(shù)差值差異，計算方法如下

DNSI(vi，vj)=|NSI(vi)-NSI(vj)|

(4)

式中：vi與vj表示兩個節(jié)點。

(2)共同鄰居數(shù)量

共同鄰居數(shù)量的數(shù)學式可表示為

(5)

式中：vp∈N(vi)，vq∈N(vj)，N(vi) 表示vi的鄰居節(jié)點。 λ(a，b) 為指示函數(shù)：如果a與b為鄰居節(jié)點，那么λ(a，b)=1， 否則λ(a，b)=0。

圖3(a)是網(wǎng)絡實例的DNSI(vi，vj)=|1-3|=2， 圖3(b)實例中的點化線表示vi與vj的共同鄰居連接，即NS(vi，vj)=2。

將鄰域結(jié)構(gòu)相似性與共同鄰居數(shù)量結(jié)合，給出兩個節(jié)點在網(wǎng)絡拓撲結(jié)構(gòu)上的相似性度量方法，計算方法如下

(6)

式中：vp為vi的鄰居節(jié)點，P為vi的鄰居節(jié)點數(shù)量，vq為vj的鄰居節(jié)點，Q為vj的鄰居節(jié)點數(shù)量。

2.2.2 構(gòu)建近鄰矩陣

搜索網(wǎng)絡中各節(jié)點的k-近鄰集，將節(jié)點vi的k-近鄰集按相似性降序排列，該處理的數(shù)學模型可表示為

DN(vi)=desort(kN(vi))

(7)

式中：kN(vi) 輸出節(jié)點vi的k-近鄰節(jié)點集，desort()函數(shù)將節(jié)點集降序排列。

函數(shù)DN()為每個節(jié)點產(chǎn)生一個k-近鄰列表，基于每個節(jié)點的k-近鄰列表為網(wǎng)絡全部節(jié)點創(chuàng)建一個近鄰矩陣。一個簡單的近鄰矩陣如圖4所示。

圖4 近鄰矩陣

2.3 基于標簽傳播的社區(qū)初始化

由候選社區(qū)中心開始標簽傳播過程，每個節(jié)點根據(jù)近鄰矩陣將其標簽初始化為最相似鄰居的標簽，該初始化策略的數(shù)學式可表示為

(8)

式中：Li與Lj分別表示節(jié)點vi與vj的社區(qū)標簽，vj是與節(jié)點vi最相似的節(jié)點，argmax()表示返回最大值。

標簽傳播處理后的社區(qū)劃分結(jié)果如圖5所示。

圖5 基于標簽傳播建立的社區(qū)結(jié)構(gòu)

3 基于強化學習的社區(qū)優(yōu)化方法

3.1 社區(qū)局部優(yōu)化

3.1.1 社區(qū)局部結(jié)構(gòu)評價指標

模塊度是評估復雜網(wǎng)絡社區(qū)結(jié)構(gòu)的經(jīng)典指標，廣義的模塊度計算公式可表示為

(9)

3.1.2 社區(qū)局部結(jié)構(gòu)優(yōu)化算子

社區(qū)性是復雜網(wǎng)絡的一個重要特性，社區(qū)內(nèi)客體的相似性與關(guān)聯(lián)性較高，社區(qū)間客體的相似性與關(guān)聯(lián)性則較低。本文基于社區(qū)性的特點提出了新的社區(qū)局部結(jié)構(gòu)優(yōu)化算子：如果當前社區(qū)內(nèi)的某個節(jié)點與其它社區(qū)存在密集的連接，那么將該節(jié)點遷移至其它社區(qū)，評估遷移前后網(wǎng)絡模塊度的增減情況。算法1總結(jié)了社區(qū)局部結(jié)構(gòu)優(yōu)化算子的處理過程。

算法1：社區(qū)局部優(yōu)化算子

輸入：Trymax，網(wǎng)絡G

輸出：優(yōu)化后的社區(qū)結(jié)構(gòu)NewModularity，優(yōu)化后的網(wǎng)絡模塊度Gmodularity

(1)Foreachtryfrom 1 toTrymax//Trymax與網(wǎng)絡結(jié)構(gòu)有關(guān)

(2) Community=InitCommunit(); //輸入當前社區(qū)結(jié)構(gòu)信息(強化學習的狀態(tài)信號)

(3) Foreach node in Community

(4)SC←CommunityofNode(node);

(5)Nout←節(jié)點連接到其它社區(qū)的邊數(shù);

(6) Endfor

(7)Noutlist←SortDescend(Nout); //按外部連接數(shù)降序排列

(8)Nmax←Nout值大于Nth的節(jié)點數(shù)量; //基于閾值判斷外部連接數(shù)

(9)InitModularity←當前網(wǎng)絡的模塊度;

(10)j←1;LModularity←InitModularity;

(11) Foreach iter from 1 toNmax

(12) 將Noutlist[iter]節(jié)點遷移到最相似的外部社區(qū); //度量相鄰節(jié)點間的相似性

(13)NewModularity←計算網(wǎng)絡的模塊度; //計算遷移后的網(wǎng)絡模塊度

(14) If (NewModularity>LModularity)

(15)LModularity←NewModularity;//更新局部模塊度

(16) 更新社區(qū)結(jié)構(gòu); //強化學習的狀態(tài)信號

(17) End if

(18) Endfor

(19) If (GModularity

(20)GModularity←LModularity; //更新全局模塊度

(21) Endif

(22)Endfor

以一個簡單實例描述社區(qū)局部結(jié)構(gòu)優(yōu)化算子的處理過程：一個初始化的網(wǎng)絡社區(qū)結(jié)構(gòu)如圖6(a)所示，節(jié)點3的外部連接數(shù)為2個，節(jié)點7與節(jié)點8的外部連接數(shù)為1個，其它節(jié)點的外部連接數(shù)均為0，因此該網(wǎng)絡的外部連接列表降序排列為 {3，7，8，0，0，0，0，0，0，0}。 首先，遍歷列表的第一個節(jié)點，計算節(jié)點3與其它社區(qū)內(nèi)鄰居節(jié)點的相似性SS()，如果SS(v3，v7)>SS(v3，v8)， 那么將v3由社區(qū)a遷移至社區(qū)b中，該過程如圖6(b)所示。如果SS(v3，v7)

圖6 社區(qū)局部優(yōu)化算子

3.2 深度強化學習

本文利用深度強化學習的感知能力與自適應決策能力決定網(wǎng)絡的社區(qū)數(shù)量與社區(qū)結(jié)構(gòu)，將社區(qū)檢測問題建模為一個優(yōu)化問題，其目標是最大化網(wǎng)絡的模塊度密度函數(shù)。Q-learning技術(shù)是一種基于自動agent的強化學習技術(shù)，該技術(shù)通過不斷采取動作與環(huán)境交互，以最大化累積的總獎賞。Q-learning的工作原理如圖7所示。Agent根據(jù)當前狀態(tài)St感知環(huán)境的變化，Agent根據(jù)當前環(huán)境選擇執(zhí)行一個動作At，環(huán)境向Agent反饋一個獎賞，并將狀態(tài)變量St更新為St+1，該狀態(tài)變量遷移的概率可表示為P(St，At，St+1)。 Q-learning的目標是學習最優(yōu)策略π(At|St)， 以最大化當前的累積獎賞。

圖7 Q-learning的工作原理

Q-learning框架中的狀態(tài)遷移過程可表示為

(10)

式中：φ∈[0，1] 為獎賞折扣因子。

給定一個策略π，Q-value函數(shù)可估計狀態(tài)St下動作At的累積獎賞期望值，Q-value函數(shù)可表示為：Qπ(St，At)=E[R|St，At，π]。 將每個狀態(tài)下Q-value值最高的策略作為最優(yōu)策略，將最優(yōu)Q-value記為

Q*(St，At)=max(Qπ(St，At))

(11)

Q-value函數(shù)的計算方法記為

Qπ(St，At)=Rt+φ·Q*(St+1，At+1)

(12)

Q-value的動態(tài)更新方法記為

Qπ(St，At)←Qπ(St，At)+η·Δ

(13)

式中：η∈[0，1] 為學習率，Δ為時間差分誤差。Δ的計算方法如下

Δ=Rt+φ·maxAt+1[Qπ(St+1，At+1)-Q(St，At)]

(14)

Q-learning框架將Q-value保存于一張查找表中，如果可選狀態(tài)的數(shù)量過大，那么根據(jù)查找表搜索最優(yōu)策略的速度較慢。深度強化學習中的DQN(deep q-network)模型可加快Q-learning的學習速度，DQN采用神經(jīng)網(wǎng)絡估計強化學習的Q-value。DQN模型的輸入為狀態(tài)向量，輸出為Q-value，采用均方偏差函數(shù)作為DQN的損失函數(shù)。DQN的損失函數(shù)可定義為

L(Θt)=(QT-Q(St，At，Θt))2

(15)

QT=Rt+φ·maxAt+1Q(St+1，At+1，Θt)

(16)

式中：Θt為第t次迭代的神經(jīng)網(wǎng)絡參數(shù)。

通常神經(jīng)網(wǎng)絡作為損失函數(shù)存在收斂穩(wěn)定性不足的問題，本文采用經(jīng)驗重放機制改善DQN的收斂穩(wěn)定性。該機制采用兩個相同結(jié)構(gòu)的神經(jīng)網(wǎng)絡，兩個網(wǎng)絡的超參數(shù)分別記為Θ與Θ′，前者用于計算Q-value，后者用于保存訓練過程中的全部Q-value，每隔C個時間步將Θ更新為Θ′。該機制的原理如圖8所示。

圖8 深度強化學習的經(jīng)驗重放機制

3.2.1 狀態(tài)信號

狀態(tài)St表示復雜網(wǎng)絡被劃分成P個社區(qū)，將St表示為一個向量形式

St=[wt，1，wt，2，…，wt，P]

(17)

式中：向量元素wt，i=[vm，…，vn] 表示第i個社區(qū)包含的節(jié)點集。

設Sp表示指定社區(qū)p對應的全部狀態(tài)集，Sp可表示為

Sp=[S1，p，S2，p，…，ST，p]

(18)

式中：T為社區(qū)p的狀態(tài)數(shù)量，即該社區(qū)在每個時間步包含的節(jié)點集。

3.2.2 動作信號

將AgentAt，p的動作表示為一個向量形式，表示社區(qū)局部優(yōu)化算子(第3.1.2部分)的節(jié)點遷移方案，動作信號可表示為

At=[ct，1，ct，2，…，ct，P]

(19)

式中：P為發(fā)生遷移的節(jié)點數(shù)量，t為當前的時間步，動作信號的元素ct，i為遷移方案向量，如ct，i=[1，2，3] 表示節(jié)點1從第2個社區(qū)遷移到第3個社區(qū)。

3.2.3 獎賞信號

相較于廣義密度函數(shù)，模塊度密度函數(shù)對社區(qū)尺寸差異大的網(wǎng)絡效果更好，因此采用復雜網(wǎng)絡的模塊度密度函數(shù)作為Agent的獎賞函數(shù)。獎賞函數(shù)可表示為

(20)

式中：Gi表示復雜網(wǎng)絡G第i個社區(qū)的子圖，l為網(wǎng)絡的社區(qū)數(shù)量，Vi為子圖Gi的頂點集。

模塊度密度值越大，說明網(wǎng)絡的社區(qū)劃分越準確。Q-learning中Agent的任務是尋找狀態(tài)集與動作集之間的最優(yōu)映射關(guān)系，該最優(yōu)映射集關(guān)系最大化累積獎賞，即最大化網(wǎng)絡的模塊度密度。

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

實驗使用Gephi version 0.9.2軟件分析社交網(wǎng)絡數(shù)據(jù)，使用Python 3.6實現(xiàn)文中相關(guān)算法，編程環(huán)境為PyCharm與Eclipse集成的開發(fā)平臺。PC機的配置為Intel Core i7-11700，主頻為2.5 GHz，內(nèi)存為32 GB，操作系統(tǒng)為Ubuntu 18.04。

4.1 實驗數(shù)據(jù)集

為評估本文算法的有效性，使用6個不同規(guī)模的真實社區(qū)檢測數(shù)據(jù)集，分別為Polblogs、Texas、Cora、Citeseer、Facebook2與Artists。一方面，所選數(shù)據(jù)集在社區(qū)數(shù)量、連接數(shù)量與節(jié)點數(shù)量上均有所區(qū)別，具有較好的多樣性；另一方面，所選數(shù)據(jù)集被廣泛用作benchmark數(shù)據(jù)集，便于進行對比實驗。

表1總結(jié)了各數(shù)據(jù)集的相關(guān)屬性，Polblogs、Texas、Cora與Citeseer屬于中小規(guī)模的網(wǎng)絡，Polblogs與Texas數(shù)據(jù)集的連接較密集，Cora數(shù)據(jù)集的連接較稀疏。Citeseer數(shù)據(jù)集的連接最為稀疏，難以通過連接直接度量出節(jié)點間的相似性。Facebook2與Artists屬于大規(guī)模的網(wǎng)絡，兩個網(wǎng)絡的連接較密集，F(xiàn)acebook2的社區(qū)結(jié)構(gòu)較簡單，Artists的社區(qū)數(shù)多達20個，社區(qū)檢測的難度更大。

表1 社區(qū)檢測數(shù)據(jù)集的相關(guān)屬性

4.2 性能評價指標

為便于進行對比實驗，采用3個常用指標評估各社區(qū)檢測算法的性能，分別為準確率、正則化互信息(norma-lized mutual information，NMI)與蘭德指數(shù) (adjusted rand index，ARI)。

準確率評價了社區(qū)檢測結(jié)果中被正確劃分的社區(qū)比例。準確率越高，社區(qū)檢測算法的性能越好。準確率的計算公式如下

(21)

式中：n為節(jié)點數(shù)量，Ci為節(jié)點i的正定社區(qū)，C′i為本文算法為節(jié)點i分配的社區(qū)。k(x，y) 為一個指示函數(shù)，如果x=y，那么k(x，y)=1， 否則k(x，y)=0。

NMI能客觀地評價檢測算法所劃分社區(qū)與正定社區(qū)之間相比的準確度。NMI值越高，社區(qū)檢測算法的性能越好。NMI的計算公式如下

NMI(A，B)=

(22)

式中：A與B分別為實際社區(qū)與檢測社區(qū)，NMI值越高說明社區(qū)檢測的性能越好。

ARI通過比較社區(qū)檢測結(jié)果與正定社區(qū)劃分之間的誤差來評價社區(qū)檢測的正確性。ARI值越高，社區(qū)檢測算法的性能越好。ARI的計算公式如下

(23)

式中：E為ARI的期望值，E的取值范圍為[-1，1]。Rand()函數(shù)的計算方法如下

(24)

式中：A表示聚類與類之間鄰居對的數(shù)量，B表示鄰居對的數(shù)量被分成聚類與分類。

4.3 對比算法

選擇6個社區(qū)檢測算法與本文算法進行對比實驗，橫向評估本文算法的性能。對比算法如下：

DAE_PSOCA[16]：該算法是基于深度自編碼器與粒子群優(yōu)化算法的復雜網(wǎng)絡社區(qū)檢測算法。它利用粒子群優(yōu)化算法訓練深度自編碼器，緩解深度自編碼器在復雜網(wǎng)絡上容易收斂于局部極值的問題。

DLT[17]：該算法是基于自編碼器與卷積神經(jīng)網(wǎng)絡的社區(qū)檢測算法。它包含網(wǎng)絡鄰接矩陣重建、空間特征提取以及社區(qū)檢測3個步驟。利用卷積神經(jīng)網(wǎng)絡提取網(wǎng)絡的空間結(jié)構(gòu)特征，利用自編碼器重建鄰接矩陣，以此增強社區(qū)檢測所需的相關(guān)信息。

MOEA[18]：該算法是基于多目標演化算法的社區(qū)檢測算法。它通過改進遺傳變異算子與交叉算子提高對社區(qū)模塊度的優(yōu)化效果。

LEPSO[19]：該算法是基于協(xié)作粒子群優(yōu)化的動態(tài)社區(qū)檢測算法。它通過多粒子群間協(xié)作機制解決社區(qū)不平衡與不顯著導致社區(qū)劃分不準確的問題。

K-Means[20]：該算法是基于K-means聚類的社區(qū)檢測算法。它通過余弦距離度量節(jié)點間的相似性，采用K-means聚類算法對復雜網(wǎng)絡進行無監(jiān)督聚類處理。

ModMRF[21]：該算法是基于乘積和信息傳遞置信度傳播的社區(qū)檢測算法。它使用模塊度作為能量函數(shù)驅(qū)動置信度傳播過程。

4.4 參數(shù)設置與訓練

將式(7)中k-近鄰的k參數(shù)設為網(wǎng)絡的平均度數(shù)，權(quán)重因子γ設為0.1，Nth的設為網(wǎng)絡的平均度數(shù)，Trymax設為30。在TensorFlow框架與Keras深度學習庫上編程實現(xiàn)文中所提及的神經(jīng)網(wǎng)絡，在MATLAB 2019B上編碼非深度學習算法。神經(jīng)網(wǎng)絡訓練過程終最大epoch次數(shù)為500。

DRL在各數(shù)據(jù)集上訓練的損失曲線如圖9所示。觀察圖中曲線可知，Cora與Citeseer兩個數(shù)據(jù)集大約經(jīng)過150次epoch達到收斂，Polblogs數(shù)據(jù)集大約經(jīng)過200次epoch達到收斂，Texas數(shù)據(jù)集大約經(jīng)過350次epoch達到收斂，F(xiàn)acebook2數(shù)據(jù)集大約經(jīng)過300次epoch達到收斂，Artists數(shù)據(jù)集大約經(jīng)過250次epoch達到收斂。

圖9 各數(shù)據(jù)集訓練的損失曲線

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

各社區(qū)檢測算法在6個benchmark數(shù)據(jù)集上的平均檢測準確率結(jié)果如圖10所示。DAE_PSOCA算法在Texas數(shù)據(jù)集與Artists數(shù)據(jù)集上的檢測準確率較高，在其它4個數(shù)據(jù)集上的檢測準確率較低。Texas與Artists數(shù)據(jù)集的網(wǎng)絡連接較密集，DAE_PSOCA算法利用深度自編碼器強大的感知能力提取網(wǎng)絡連接的信息，利用粒子群優(yōu)化算法緩解深度自編碼器在復雜網(wǎng)絡上容易收斂于局部極值的問題，在Texas與Artists數(shù)據(jù)集上性能較好。DLT算法在Texas數(shù)據(jù)集與Citeseer數(shù)據(jù)集上的檢測準確率較高，在其它4個數(shù)據(jù)集上的檢測準確率較低。DLT算法利用卷積神經(jīng)網(wǎng)絡提取網(wǎng)絡的空間結(jié)構(gòu)特征，提取了Texas數(shù)據(jù)集密集的連接信息，因此在Texas數(shù)據(jù)集上性能較好。此外，DLT算法利用自編碼器重建鄰接矩陣，增強了社區(qū)檢測所需的相關(guān)信息，因此在Artists數(shù)據(jù)集上性能也較好。MOEA算法與LEPSO算法均為基于啟發(fā)式算法優(yōu)化復雜網(wǎng)絡模塊度的社區(qū)檢測算法，比較這兩個算法在6個數(shù)據(jù)集上的實驗結(jié)果可得出結(jié)論，多目標演化算法的優(yōu)化效果好于多目標粒子群算法。ModMRF用置信度傳播代替?zhèn)鹘y(tǒng)標簽傳播，將模塊度作為驅(qū)動傳播的能量函數(shù)，該算法的準確率較低。本文算法利用新的相似性度量指標度量了節(jié)點在網(wǎng)絡拓撲結(jié)構(gòu)上的相似性，利用深度強化學習模型發(fā)現(xiàn)網(wǎng)絡的社區(qū)結(jié)構(gòu)，并通過社區(qū)局部優(yōu)化算子改善社區(qū)邊界劃分的準確性。本文算法在Polblogs、Texas、Facebook2與Artists共4個數(shù)據(jù)集上均取得了最優(yōu)的檢測準確率，且大幅領先于其它對比社區(qū)檢測算法，而在Cora與Citeseer兩個數(shù)據(jù)集上的檢測準確率低于DLT算法，本文算法對連接密度低的網(wǎng)絡性能較低，對連接密度較高的網(wǎng)絡性能較好。其原因在于：本文算法在社區(qū)初始化階段以網(wǎng)絡度數(shù)為社區(qū)中心判定依據(jù)，在社區(qū)局部優(yōu)化算子中以網(wǎng)絡連接為節(jié)點遷移依據(jù)。綜上所述，連接過少難以發(fā)揮本文算法的優(yōu)勢，容易出現(xiàn)誤判與漏判的情況；而連接密集度越高，本文算法的優(yōu)勢越大。

圖10 社區(qū)檢測算法的平均準確率

各社區(qū)檢測算法在6個benchmark數(shù)據(jù)集上的平均檢測NMI值如圖11所示。DAE_PSOCA算法與DLT算法在Artists數(shù)據(jù)集上的NMI結(jié)果較好，在其它5個數(shù)據(jù)集上的NMI結(jié)果較低。MOEA在Texas、Facebook2與Artists數(shù)據(jù)集上的NMI結(jié)果較高，LEPSO則在Cora數(shù)據(jù)集上的NMI結(jié)果較高，由此可知基于啟發(fā)式的社區(qū)檢測算法發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)與正定社區(qū)結(jié)構(gòu)的偏差較大。ModMRF用置信度傳播代替?zhèn)鹘y(tǒng)標簽傳播，將模塊度作為驅(qū)動傳播的能量函數(shù)，該算法高連接密度小規(guī)模數(shù)據(jù)集Polblogs上的NMI性能最佳，在其它大規(guī)模數(shù)據(jù)集或低連接密度數(shù)據(jù)集上的NMI性能較低。本文算法利用新的相似性度量指標度量了節(jié)點在網(wǎng)絡拓撲結(jié)構(gòu)上的相似性，利用深度強化學習模型發(fā)現(xiàn)網(wǎng)絡的社區(qū)結(jié)構(gòu)，并通過社區(qū)局部優(yōu)化算子改善社區(qū)邊界劃分的NMI值。本文算法在6個數(shù)據(jù)集上均取得了最優(yōu)的檢測NMI值，由此可知，本文算法發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)與正定社區(qū)結(jié)構(gòu)最為接近。

圖11 社區(qū)檢測算法的平均NMI

各社區(qū)檢測算法在6個benchmark數(shù)據(jù)集上的平均檢測ARI值如圖12所示。DAE_PSOCA、DLT、MOEA這3個算法在6個benchmark數(shù)據(jù)集上的平均檢測ARI值較低，由此可知，這3個算法發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)與正定結(jié)構(gòu)存在較大的誤差。ModMRF用置信度傳播代替?zhèn)鹘y(tǒng)標簽傳播，將模塊度作為驅(qū)動傳播的能量函數(shù)，該算法發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)誤差較小，但產(chǎn)生較多的小尺度社區(qū)，所產(chǎn)生的社區(qū)數(shù)量與正定社區(qū)結(jié)構(gòu)存在較大的偏差。本文算法在6個數(shù)據(jù)集上均取得了最優(yōu)的檢測ARI值，由此可知，本文算法發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)與正定社區(qū)結(jié)構(gòu)的誤差最小。

圖12 社區(qū)檢測算法的平均ARI

5 結(jié)束語

為提高復雜網(wǎng)絡社區(qū)檢測的準確性，本文利用深度強化學習為復雜網(wǎng)絡的社區(qū)檢測問題提出新的解決思路。第一階段基于網(wǎng)絡拓撲結(jié)構(gòu)初始化社區(qū)結(jié)構(gòu)，第二階段基于深度強化學習對網(wǎng)絡社區(qū)結(jié)構(gòu)進行微調(diào)與優(yōu)化，利用深度強化學習強大的感知能力與決策能力提高社區(qū)結(jié)構(gòu)的準確性。該算法在社區(qū)初始化階段以網(wǎng)絡度數(shù)為社區(qū)中心判定依據(jù)，在社區(qū)局部優(yōu)化算子中以網(wǎng)絡連接為節(jié)點遷移依據(jù)。因此，連接過少難以發(fā)揮本文算法的優(yōu)勢，而連接密集度越高，本文算法的優(yōu)勢越大。