基于深度強化學習的復雜網絡可擴展社區檢測

馬玉磊，鐘瀟柔

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

0 引 言

復雜網絡[1]具有無尺度性、高聚類系數以及小世界性的特點，常用于表達現實系統中客體之間的關系，在生物領域的蛋白質網絡、無線通信領域的蜂窩網絡及計算機領域的社交網絡中具有很大的應用價值。社區性是復雜網絡的一個重要特性，社區內客體的相似性與關聯性較高，社區間客體的相似性與關聯性則較低，社區檢測[2]是分析復雜網絡的一個重要步驟。

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

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

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

1 系統框架設計

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

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

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

2 復雜網絡的社區初始化

2.1 候選社區中心估計

為了識別網絡中的中心節點，計算每個節點在其鄰域內的度數方差，稱為鄰域方差(neighbor variance，NV)。鄰域方差(NV)的計算方法定義為

(1)

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

圖2 社區中心

候選社區中心估計步驟如下：

步驟1 計算網絡G每個節點的NV值保存于向量HV中，將HV的元素按數值降序排列。

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

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

平均距離的計算方法如下

(2)

式中：d(u，v) 為節點u與v之間的最短路徑，V為網絡的節點數量。

2.2 節點相似性評估

2.2.1 網絡結構相似性度量

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

(1)鄰域結構相似性

首先，計算節點vi與其鄰居節點的度數差值，計算方法如下

(3)

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

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

圖3 節點相似性度量的實例

然后，計算節點vi與vj之間的度數差值差異，計算方法如下

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

(4)

式中：vi與vj表示兩個節點。

(2)共同鄰居數量

共同鄰居數量的數學式可表示為

(5)

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

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

將鄰域結構相似性與共同鄰居數量結合，給出兩個節點在網絡拓撲結構上的相似性度量方法，計算方法如下

(6)

式中：vp為vi的鄰居節點，P為vi的鄰居節點數量，vq為vj的鄰居節點，Q為vj的鄰居節點數量。

2.2.2 構建近鄰矩陣

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

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

(7)

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

函數DN()為每個節點產生一個k-近鄰列表，基于每個節點的k-近鄰列表為網絡全部節點創建一個近鄰矩陣。一個簡單的近鄰矩陣如圖4所示。

圖4 近鄰矩陣

2.3 基于標簽傳播的社區初始化

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

(8)

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

標簽傳播處理后的社區劃分結果如圖5所示。

圖5 基于標簽傳播建立的社區結構

3 基于強化學習的社區優化方法

3.1 社區局部優化

3.1.1 社區局部結構評價指標

模塊度是評估復雜網絡社區結構的經典指標，廣義的模塊度計算公式可表示為

(9)

3.1.2 社區局部結構優化算子

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

算法1：社區局部優化算子

輸入：Trymax，網絡G

輸出：優化后的社區結構NewModularity，優化后的網絡模塊度Gmodularity

(1)Foreachtryfrom 1 toTrymax//Trymax與網絡結構有關

(2) Community=InitCommunit(); //輸入當前社區結構信息(強化學習的狀態信號)

(3) Foreach node in Community

(4)SC←CommunityofNode(node);

(5)Nout←節點連接到其它社區的邊數;

(6) Endfor

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

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

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

(10)j←1;LModularity←InitModularity;

(11) Foreach iter from 1 toNmax

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

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

(14) If (NewModularity>LModularity)

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

(16) 更新社區結構; //強化學習的狀態信號

(17) End if

(18) Endfor

(19) If (GModularity

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

(21) Endif

(22)Endfor

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

圖6 社區局部優化算子

3.2 深度強化學習

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

圖7 Q-learning的工作原理

Q-learning框架中的狀態遷移過程可表示為

(10)

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

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

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

(11)

Q-value函數的計算方法記為

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

(12)

Q-value的動態更新方法記為

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保存于一張查找表中，如果可選狀態的數量過大，那么根據查找表搜索最優策略的速度較慢。深度強化學習中的DQN(deep q-network)模型可加快Q-learning的學習速度，DQN采用神經網絡估計強化學習的Q-value。DQN模型的輸入為狀態向量，輸出為Q-value，采用均方偏差函數作為DQN的損失函數。DQN的損失函數可定義為

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

(15)

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

(16)

式中：Θt為第t次迭代的神經網絡參數。

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

圖8 深度強化學習的經驗重放機制

3.2.1 狀態信號

狀態St表示復雜網絡被劃分成P個社區，將St表示為一個向量形式

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

(17)

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

設Sp表示指定社區p對應的全部狀態集，Sp可表示為

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

(18)

式中：T為社區p的狀態數量，即該社區在每個時間步包含的節點集。

3.2.2 動作信號

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

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

(19)

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

3.2.3 獎賞信號

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

(20)

式中：Gi表示復雜網絡G第i個社區的子圖，l為網絡的社區數量，Vi為子圖Gi的頂點集。

模塊度密度值越大，說明網絡的社區劃分越準確。Q-learning中Agent的任務是尋找狀態集與動作集之間的最優映射關系，該最優映射集關系最大化累積獎賞，即最大化網絡的模塊度密度。

4 實驗與結果分析

實驗使用Gephi version 0.9.2軟件分析社交網絡數據，使用Python 3.6實現文中相關算法，編程環境為PyCharm與Eclipse集成的開發平臺。PC機的配置為Intel Core i7-11700，主頻為2.5 GHz，內存為32 GB，操作系統為Ubuntu 18.04。

4.1 實驗數據集

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

表1總結了各數據集的相關屬性，Polblogs、Texas、Cora與Citeseer屬于中小規模的網絡，Polblogs與Texas數據集的連接較密集，Cora數據集的連接較稀疏。Citeseer數據集的連接最為稀疏，難以通過連接直接度量出節點間的相似性。Facebook2與Artists屬于大規模的網絡，兩個網絡的連接較密集，Facebook2的社區結構較簡單，Artists的社區數多達20個，社區檢測的難度更大。

表1 社區檢測數據集的相關屬性

4.2 性能評價指標

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

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

(21)

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

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

NMI(A，B)=

(22)

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

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

(23)

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

(24)

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

4.3 對比算法

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

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

DLT[17]：該算法是基于自編碼器與卷積神經網絡的社區檢測算法。它包含網絡鄰接矩陣重建、空間特征提取以及社區檢測3個步驟。利用卷積神經網絡提取網絡的空間結構特征，利用自編碼器重建鄰接矩陣，以此增強社區檢測所需的相關信息。

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

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

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

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

4.4 參數設置與訓練

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

DRL在各數據集上訓練的損失曲線如圖9所示。觀察圖中曲線可知，Cora與Citeseer兩個數據集大約經過150次epoch達到收斂，Polblogs數據集大約經過200次epoch達到收斂，Texas數據集大約經過350次epoch達到收斂，Facebook2數據集大約經過300次epoch達到收斂，Artists數據集大約經過250次epoch達到收斂。

圖9 各數據集訓練的損失曲線

4.5 實驗結果與分析

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

圖10 社區檢測算法的平均準確率

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

圖11 社區檢測算法的平均NMI

各社區檢測算法在6個benchmark數據集上的平均檢測ARI值如圖12所示。DAE_PSOCA、DLT、MOEA這3個算法在6個benchmark數據集上的平均檢測ARI值較低，由此可知，這3個算法發現的社區結構與正定結構存在較大的誤差。ModMRF用置信度傳播代替傳統標簽傳播，將模塊度作為驅動傳播的能量函數，該算法發現的社區結構誤差較小，但產生較多的小尺度社區，所產生的社區數量與正定社區結構存在較大的偏差。本文算法在6個數據集上均取得了最優的檢測ARI值，由此可知，本文算法發現的社區結構與正定社區結構的誤差最小。

圖12 社區檢測算法的平均ARI

5 結束語

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