基于多目標進化的復雜網絡社區檢測

2020-06-16 01:04:48柴爭義

計算機技術與發展 2020年6期

王聰，柴爭義

(天津工業大學計算機科學與技術學院，天津 300387)

0 引言

在復雜網絡中，被廣泛關注的一個重要的拓撲屬性就是網絡的社區結構[1]。所謂社區結構，就是指整個網絡由若干“簇”或“組”構成，這些“簇”或“組”叫做社區，位于每個社區內部的節點相互之間的連接非常稠密，而位于不同社區內的節點相互之間的連接比較稀疏[2-3]。

近幾年，復雜網絡社區發現作為一個研究熱點，已經受到越來越多的關注，也有越來越多的學者參與其中，現如今已經涌現出了許多優秀的社區發現算法，主要有以下幾類：

(1)基于節點相似度。

為了準確計算節點的相似性，文獻[4]通過分析二分網絡中兩類節點的結構特征及其對社區密度的影響，結合了Salton指數和改進的Logistic函數，定義了一種新的相似度計算方法；文獻[5]基于網絡節點相似度矩陣，結合改進的K-means算法對網絡節點進行相似性聚類，實現網絡的社區發現；文獻[6]提出一種基于多層節點的節點相似度計算方法，該方法既可以有效地計算節點之間的相似度，又可以解決節點相似度相同時的節點合并選擇問題。

(2)基于層次化聚類。

文獻[7]則引進節點相似度并加以適當改進，然后重新定義模塊度函數，提出基于節點相似度的層次化社區發現算法，提高了層次化社區發現的準確性；為了處理大規模復雜網絡中的社區結構，文獻[8]提出一種基于SCAN算法的密度聚類算法——QSCAN算法。

(3)基于AP算法。

當前很多學者將AP聚類算法應用于社區檢測[9]，文獻[10]利用網絡潛在幾何概念對網絡的相似性矩陣進行改進，能有效提高AP聚類算法的聚類效果；對于復雜度較高的社區網絡，則需要利用并行計算處理對數據進行AP聚類[11]。

(4)結合算法。

有學者提出MOEA/D算法的多目標社區檢測算法，且經過案例測試，在解決復雜網絡社區檢測問題上具有一定優勢，且通過AP聚類算法對初始解進行優化，再用多目標檢測算法進行社區發現的社區發現效果更佳[12-13]。

文中將聚類和啟發式的算法相結合，提出一種改進的多目標進化算法來進行復雜網絡的社區檢測，用半監督的AP聚類算法確定初始解的聚類數目以及節點所屬類別，克服傳統的通過隨機方式產生的初始解聚類效果不穩定的缺點，進而采用模擬退火算法改進MOEA/D算法完成參數尋優過程，防止算法陷入局部最優，提高算法的全局搜索能力。

1 相關技術

1.1 近鄰傳播聚類

Affinity Propagation(AP)算法是一種半監督聚類算法，該算法無需制定聚類數目以及聚類中心，將所有樣本點作為可疑的聚類中心，算法會在每一次迭代過程中對(responsibility)和(availability)的數據進行更新。該算法的終值條件是可以找到m個高質量的聚類中心，且其他樣本點都能規劃到相應的類別。

該算法的步驟如下：

(1)計算數據集的相似度S，再對p賦值。

(2)計算樣本點之間的responsibility值。

(3)計算樣本點間的availability值。

(4)responsibility及availability值更新。

其中λ是收斂系數，主要用于調節算法的收斂速度以及迭代過程的穩定性。

終止計算的條件必須滿足迭代次數已經超過設定的最大值或者經過若干次的迭代計算后聚類中心已經不再發生改變時，計算終止后得出聚類的中心點和每類所包含的數據，反之返回步驟2，繼續計算。

文中將AP聚類算法作為初始解的產生算法，用來實現初始解的半監督聚類。

1.2 模擬退火算法

SA(模擬退火)算法是一種模仿系統中的粒子通過運動逐漸趨向平穩的過程，這個過程可以分為加熱、等溫和冷卻三個階段。隨著迭代的進行，系統的溫度逐漸下降，對于優化問題來說其當前解逐漸逼近真實解，因而系統趨向于穩定[14-16]。

文中溫度T的初始溫度T0=100，且降溫系數為0.9，即個體下一狀態溫度為上一狀態溫度的90%，如下式：

Tk+1=0.9Tk

(1)

其中，k為當前狀態，k+1為下一狀態；Tk,Tk+1分別為兩次相鄰狀態的溫度。

對于個體的變異操作將加入模擬退火的改進，假設當代種群的溫度為Tk，對于個體i來說是否接受其變異后的個體取決于該個體變異后的新個體的適應度是否大于變異前個體的適應度。如果變異后的個體的適應度大于原來個體的適應度，則對其進行變異；反之則以概率p接受該個體的變異，其中：

p=e(f(xk,i,mutatio)-f(xk,i))/Tk

(2)

其中，p為在變異后個體的適應度小于當前個體的適應度的情況下的變異概率，k為當前的迭代種群索引，i為個體索引，f(xk,i,mutatio)和f(xk,i)分別為變異后個體的適應度與當前個體的適應度。

變異原則如下式：

(3)

其中，rand(0,1)為[0，1]之間的一個隨機數。變異后個體的適應度f(xk,i,mutatio)大于原來個體的適應度f(xk,i)，則對其進行變異；反之只有當變異概率p大于隨機數rand(0，1)，接受該個體的變異，其余情況下保持個體不變異，對于k+1代種群的第i個個體依舊沿用上一代的第i個個體。

2 算法思想

通過AP聚類算法可實現對節點網絡的半監督聚類，不用再去人為確定聚類數目以及聚類中心；繼而采取模擬退火算法對遺傳算法進行改進，因為模擬退火算法的獨特之處就在于其在個體進化過程中會滿足一定的概率來決定是否接受新個體的產生，這個準則也被稱為Metropolis準則，這也是模擬退火算法相較于遺傳算法的優勢，通過一定概率接受新個體來提高算法的全局解空間的搜索能力，防止陷入局部最優。

3 MOEA/D多目標進化社區發現算法

MOEA/D是由Zhang和Li在2007年提出的一種基于分解的進化多目標優化算法，該算法將一個多目標問題根據權值矢量分解成個單目標子問題，并通過進化計算方法同時優化這些子問題。

文中采用模塊度密度D作為指標對Pareto解進行優秀個體的選取。

3.1 目標函數及評價指標

為了使網絡社區劃分的好壞可以有一個明確的評價指標來衡量，根據對復雜網絡的研究提出了模塊度(modularity)的概念，但利用模塊度來優化會導致分辨率限制的問題，于是有研究者引入了模塊度密度D來避免這個問題。在大量的重復驗證中，以模塊度密度D作為指標要比以模塊度Q作為指標在復雜網絡社區檢測的效果更好。

(4)

文中把RA改成了Kernel K-means(KKM)，將上述問題轉換成了關于最小值的優化問題，則目標函數定義為下式：

(5)

其中，n=|V|，σ為一實數。這樣一來，社團內部的緊密性就可以用KKM的值來表示，而內部節點和外部節點連接的稀疏性則可以用RC的值來表示。KKM的值越小，社區內節點間的連接越緊密；RC的值越大，社區間節點間的連接越稀疏。

3.2 算法構建

文中算法共有三個部分，分別是初始解優化、多目標進化以及結果可視化。

步驟1～6為AP算法初始解優化部分，步驟7～13為AP算法多目標進化部分。

步驟2：計算數據集的相似度S。

步驟3：計算樣本點之間的responsibility值。

(6)

其中，a(i,j)表示節點j對于節點i的availability值，s(i,k)表示節點i和節點j的相似度，r(i,k)表示節點k對于節點i的responsibility值。

步驟4：計算樣本點間的availability值。

(8)

其中，a(i,k)表示節點k對于節點i的availability值，r(k,k)表示節點k的responsibility值。

步驟5：responsibility及availability值更新。

(9)

其中，λ是收斂系數，主要用于調節算法的收斂速度以及迭代過程的穩定性。

步驟6：計算個體的適應度并記錄。

步驟7：判斷p是否等于pmax，如果成立則進入下一步的多目標進化算法，初始尋優過程結束；反之，p=p+Δp返回步驟2。

步驟8：個體編碼采用直接編碼，其中每個個體都包含m個十進制的染色體，也就是每個節點所屬的社團的類別號，這些類別號都是整數，可以是1-m之間的隨機整數。對于一個具有m個節點的網絡圖最多可以分為n類社區，則在這種情況下個體編碼[1,2,…,m]，則該個體具有m個染色體，每個染色體代表一個節點的所屬社團的類別。

步驟10：交叉。對相鄰的兩個父代個體采取單點交叉方式，通過產生一個隨機的位置點，將該點以后的個體的相應位置的編碼進行交換，以此產生兩個新的相鄰的子代個體。對于相鄰兩個個體的交叉過程如圖1所示。

圖1 單點交叉示意圖

步驟11：變異。就是對某一節點所屬的社團分類以概率pm進行隨機改變，但是社團分類小于節點的數目m，也就是對于第i個種群的第j個個體的第k個染色體是否變異應滿足一下原則：

(10)

步驟12：對當代種群進行解碼；計算當代各個個體所對應的兩個目標函數，KKM以及RC數值；且計算個體的模塊度密度D對Pareto解進行優秀個體的選取。

步驟13：是否達到預設最大迭代次數，如果是，則輸出最后一代種群，算法結束；反之則返回步驟(2)。

結果可視化部分則是通過將算法在不同的μ值之下仿真40次，分別求均值以此逼近不同μ值之下的復雜網絡的NMI數值，通過畫圖進行算法效果的對比。

4 實驗分析

文中的分析案例為Footbal足球社交網絡、Karate-Club網絡和Dolphins網絡，編程平臺為MATLAB2016B，機器配置為CPUi5-4200h，12 GB內存。首先，設置AP聚類算法的p參數的上下限為[-20，0]，且對其進行400等分，作為初始種群；然后設置MOEA/D算法的迭代次數為40，種群大小為400，交叉概率為0.8；接著通過改變μ參數從0.1到0.9，間隔為0.1分別進行40次實驗得到實驗結果；最后繪制出不同μ值下所對應的NMI曲線，且以MOEA/D算法[12]和AP-MOEA/D算法作為對比[13]。

選用NMI指標來評價社區檢測效果，歸一化互信息函數(NMI)用于評價兩個社區劃分之間的相似性。互信息在信息論中是一種重要的炮測量方法，用來衡量兩個事件之間的相關性，其啟發式原則是，如果兩個社區是相似的，那么通過其中一個社區的類內信息即可得到另外一個社區的結構。使用幾何均值的方法歸一化互信息的表達式為：

(11)

利用NMI來評價兩個社區之間的相似性，當其值接近1時，表示兩個社區之間結構很相似；當NMI的值接近0時，表示兩個社區之間結構很不相似。

經過MATLAB編程運算可以得到AP-SA-MOEA/D社區發現算法在不同μ值之下的40次實驗經過剔除異常值的NMI平均值曲線，且以AP-MOEA/D算法、MOEA/D算法作為對比算法，對比曲線如圖2～圖4所示，對比結果如表1～表3所示。