基于遺傳算法的大規模社交網絡社區發現算法

陳永建，周 艷,2，劉超英

(1.肇慶學院 計算機科學與軟件學院、大數據學院，廣東 肇慶 526061； 2.西北工業大學 自動化學院，陜西 西安 710129)

0 引 言

在社交網絡中，社區是一個重要的結構，社區內的節點互相具有大量的連接，社區間的節點則僅有少量的連接[1-3]。搜索社交網絡中的社區結構能夠有助于預測網絡的行為、分析網絡的功能，目前社區發現問題已經成為社交網絡的研究重點。對于大規模社交網絡，社區的數量極大并且社區之間的連接也較為復雜，這為大規模社交網絡中社區發現算法的準確率與計算效率帶來了困難[4]。

許多研究人員已經提出了大量的方案來解決社交網絡的社區發現問題，其中一部分算法基于網絡的統計分析與聚類分析檢測出連接密集的節點集合[5]，但這些算法往往需要一些網絡的先驗信息，例如：社區數量、網絡中社區是否重疊、社區規模等等[6]，而這些先驗信息在實際應用中往往難以預知。文獻[7]設計了定量描述社區結構的模塊性Q函數，隨之出現許多元啟發式算法將Q函數作為目標函數，從而檢測出網絡的社區結構，這些元啟發式算法包括：模擬退火算法[8]、種群智能算法[9]、遺傳算法與演化算法[10]等。遺傳算法具有較強的全局尋優能力，因此將遺傳算法應用于社區發現問題得到了最為廣泛的研究，并且也獲得了較好的效果。文獻[11]為遺傳算法引入了多維染色體與均勻塊交叉算子，能夠較好地刻畫社區重疊部分的節點，但該算法對于社區重疊的社交網絡具好較好的性能，而對于社區不重疊的社交網絡并未表現出優勢。文獻[12]為遺傳算法引入了免疫機制，該機制能夠保證種群的多樣性，并且設計了新的染色體編碼方案，有效地縮小了種群的搜索空間。文獻[13]為了解決遺傳算法易于陷入局部最優與缺乏穩定性的問題，設計了基于網絡局部信息的節點-社區隸屬度機制，該機制能夠有效地縮小初始化種群的搜索空間，但該算法的隸屬度機制主要考慮了社區內部的隸屬度。文獻[14]為遺傳算法引入了強化學習機制，將agent編碼為網絡的一個劃分方案，并且設計了一系列新的遺傳算子，包括：鄰居節點競爭算子、混合鄰居節點交叉算子、自適應變異算子與自學習算子。上述算法對于遺傳算法的改進主要關注于遺傳算法的種群多樣性、收斂速度以及初始化種群的搜索空間，但如果預測出大規模社交網絡的社區數量，能夠極大地縮小初始化種群的搜索空間，并且能夠提高種群演化的準確性。

當前的社交網絡中普遍存在社區重疊的現象，因此許多社區發現算法在計算節點與社區隸屬度的過程中，將重疊社區作為先驗知識，這類算法[11]無法適用于非重疊社區的社交網絡。本文設計了一種基于遺傳算法的社區發現算法，采用遺傳算法搜索Q函數的最優解，選擇隨機節點的鄰居節點與鄰接節點作為初始化種群，并且設計了節點對社區的隸屬度計算方案，通過設置合適的閾值能夠控制檢測的社區規模，該方案也能夠預測網絡中的社區數量，為社區的規模進行約束，提高種群演化的準確性。因為本算法的社區隸屬度計算方案同時考慮了節點的社區內部關聯性與外部關聯性，因此能夠同時適用于社區重疊與社區不重疊的社交網絡。

1 背景知識

1.1 社區發現的模塊性

模塊性是社區發現研究中應用最為廣泛的目標函數，能夠定量地描述社區的結構，并且形式簡潔、易于計算。模塊性表示了網絡中連接社區結構內部節點的邊占網絡總邊數的比例與一個隨機網絡中連接社區結構內部節點的邊占網絡總邊數比例的差值，模塊性函數(Q)定義為下式

(1)

式中：M表示網絡中邊的總數量，下標i與j表示網絡的兩個節點，Ki與Kj分別是第i個節點與第j個節點的度，參數aij表示鄰接矩陣第i行、第j列的元素，δ(i,j)表示第i個節點與第j個節點之間的關系，如果節點i與節點j在同一個社區內，那么δ(i,j)=1；否則，δ(i,j)=0。對于社交網絡的社區劃分問題，Q值越大，表示社區結構性越強，一般社區劃分較為明顯的Q值范圍為0.3～0.7。本文的遺傳算法將Q值作為適應度函數。

1.2 基于重疊與非重疊區域的社區隸屬度

該文設計了一個基于關聯節點的社區數量估計算法，該估計算法考慮了網絡連接的整體結構。采用兩個參數描述每個節點的社區隸屬度，分析社區的重疊部分與非重疊部分。參數IA(內部關聯性)表示某個節點與鄰居節點的連接情況，該參數度量了社區內節點的內部關聯性，IA已經足以檢測出社區的非重疊部分，但難以檢測出社區的重疊部分。另一個參數EA(外部關聯性)度量了網絡中每個節點在不同社區之間的作用量，采用生成隨機模塊模型[15]實現該參數。最終，一個節點屬于某個社區的概率依賴該節點的鄰居節點數量以及該節點與其它社區的作用量，將這兩個度量指標定義為節點的社區關聯度。

考慮一個一般性的網絡結構，表示為圖結構G=(V,E)，其中V與E分別表示網絡的節點集與邊集合。社區發現問題可建模為搜索節點的分組ci，可將ci表示為C=c1∪c2∪…∪ck。

1.2.1 非重疊區域的內部關聯性

內部關聯度(IA)評估了每個節點與其所屬社區的關聯性，具體定義為下式

(2)

式中：N(vi)是節點vi的鄰居節點，P(vj|ci)表示節點vj對于社區ci的社區傳播概率，該值由邊聚類算法[16]推導而來，N(vi)等于節點vi的鄰居節點數量。

1.2.2 重疊區域的外部關聯性

圖1是重疊社區與非重疊社區的網絡示意圖。通過模塊模型可檢測每個節點與其它社區的外部關聯度，每個節點外部關聯度的計算步驟如下：

步驟1 估計兩個社區之間的作用矩陣；

步驟2 基于鄰居節點的社區傳播概率與作用矩陣計算給定節點的外部關聯度。

圖1 非重疊社區與重疊社區的網絡

2 針對社區發現的遺傳算法

針對社交網絡的社區發現問題提出了一種遺傳算法，采用模塊性函數(Q函數)引導遺傳算法的演化過程，并且設計了不同的策略與遺傳算子來識別網絡的社區。

隨機初始化策略的網絡節點之間缺少關聯性導致初始解的質量較低，影響了遺傳算法的尋優能力與收斂速度。為了解決該問題，設計了一種初始化方案，將原網絡圖中連接的相鄰點作為初始化空間，該方案有助于提高算法的收斂速度；然后，采用社區密度指標度量個體數據的結構，從而平衡各個社區的規模。

本文的社區初始化機制有以下兩種：

(1)一級鄰居初始化機制：圖2是初始化機制的示意圖，隨機選擇一個節點(圖中為節點3)，將節點3與其一級鄰居納入初始化社區中，如果達到預設的最大社區規模，則結束搜索過程。如果節點3沒有一級鄰居，則重復上述過程直至達到預設的最大社區規模。

(2)二級鄰居初始化機制：圖2是初始化機制的示意圖，隨機選擇社區內一個具有一級鄰居的節點(圖中為節點3)，將節點3的二級鄰居納入初始化社區中，如果達到預設的最大社區規模，則結束搜索過程。如果節點3沒有二級鄰居，則重復上述過程直至達到預設的最大社區規模。

圖2 一級鄰居初始化與二級鄰居初始化

2.1 種群初始化方案

在初始化階段，使用估計的社區數量(1.2小節)計算每個社區的最大規模，采用平衡初始化機制計算最大規模值：將網絡節點總數量除以估計的社區數量，計算結果稱為社區密度，將該值作為初始化種群中每個社區的最大規模值。然后開始鄰居社區初始化程序，如果①一級鄰居初始化機制未能達到最大的社區規模，則開始②二級鄰居初始化過程。圖3(a)是種群初始化的一個實例。

圖3 社區初始化實例

種群演化的過程中，兩個社區邊界之間的節點可能發生遷移，遷移策略是基于邊向最有吸引力目標遷移的思想，即給定一個節點，該節點將遷移至該節點連接的最大規模社區。邊界之間遷移向量的初始化方案，如圖3(b)所示。表1是邊界遷移的產生方法，表1的列表示了社區1與社區2，節點數量直接與列節點連接。列遷移向量按照所有社區計數器中的最高值(最多連接數)選擇每個節點的最終目標社區。

表1 邊界遷移的產生方案

2.2 基于社區隸屬度的社區發現規模控制

在許多實際應用中，社區結構的數量是已知值，能夠縮小搜索算法的搜索空間；而在其它的多數場景下，社區結構的數量是未知值，但可以估計出社區結構的數量，據此也可以縮小搜索空間。預測或者預知社交網絡中社區結構的數量，能夠有效地縮小搜索空間，并且提高算法的性能。

網絡中的社區規模存在巨大的差異，為了滿足可控制的社區發現算法，設計了基于社區隸屬度的社區發現規模控制方案。通過節點的社區隸屬度估計出網絡中不同規模的社區數量，如果用戶請求搜索大規模的社區結構，則可以設置較大的社區隸屬度閾值，從而減小網絡中的目標社區數量，該機制能夠有效地縮小遺傳算法的搜索空間；如果用戶請求搜索網絡中的全部社區結構，則可以設置較小的社區隸屬度閾值。

圖4是社區隸屬度的計算方法的流程框架，包含了節點的內部關聯性與外部關聯性。

圖4 社區隸屬度算法的流程框架

假設網絡由相互關聯的社區組成，網絡中每個節點與社區具有兩層關聯性，第一層是同一個社區節點之間的內部關聯性，第二層是節點與其它社區的外部關聯性。該文提出一個基于概率的隸屬度方法，檢測出網絡的社區數量。

將每個節點vi對于社區ci的概率隸屬條件定義為下式

P(vi∈ci)=P(vi∈ci|N(vi)∈ci)+
P(vi∈ci|N(vi)∈c-i)

(3)

P(vi∈ci)=P1(ci).IAci(vi)+p2(ci).EAci(vi)

(4)

(5)

式中：β(ci,cj)是社區ci與cj之間的作用矩陣。通過最大似然估計方法獲得每對社區之間的近似作用矩陣

(6)

式中:ρ是已知的稀疏正則化因子，ρ的計算方法為[17]

(7)

式中：F(vi|ci)=max(P(vi|ci)×P(vj|cj),P(vi|cj)×P(vj|cj))。

圖5是3個社區重疊的實例，節點v4同時屬于3個社區，根據式(2)～式(6)可計算出圖中：ρ=39/53，βc1,c2=1.25，βc1,c3=0.8，βc2,c3=1，EAv4(c1)=53/70，EAv4(c2)=45/70，EAv4(c3)=46/70，IAv4(c1)=2/7，IAv4(c2)=3/7，IAv4(c3)=2/7。計算出節點的內部關聯性與外部關聯性之后，最終傳播概率依賴權重值p1與p2，p1與p2的計算方法如下

(8)

圖5 3個社區重疊的實例

節點v4同時屬于3個社區，根據式(2)～式(6)可計算出：ρ=39/53，βc1,c2=1.25，βc1,c3=0.8，βc2,c3=1，EAv4(c1)=53/70，EAv4(c2)=45/70，EAv4(c3)=46/70，IAv4(c1)=2/7，IAv4(c2)=3/7，IAv4(c3)=2/7。

2.3 遺傳算子

為了增強遺傳算法對社交網絡相關數據結構的尋優效果，設計了特殊的遺傳算子。

2.3.1 交叉算子

交叉算子基于社區邊界間節點的交換而實現，將目標社區邊界的一個節點與當前社區的另一個節點進行交換，并且目標社區不應是當前的社區。第二個節點應當滿足其社區最優的外部關聯性(第1.2小節描述)。通過選擇外部關聯性最優的節點進行交叉操作，有助于維護社區之間規模的平衡。圖6是交叉算子的操作實例，在該實例中，選擇節點3作為互換節點，其目標社區是節點1，圖6中目標社區的節點是與源社區(社區2)關聯性最高的社區，選擇這兩個社區的節點進行交換。列“節點”列出了外部連接的數量，選為交換的節點是具有最多鄰居數量的節點：節點3有3個外部連接，節點5有1個外部連接，選擇節點5與節點3交換。

圖6 交叉算子的操作實例

2.3.2 變異算子

選擇適合變異的節點集，從該節點集中隨機選擇一個節點，將該節點與目標社區的一個節點進行交換。圖7是變異算子的操作實例，在該實例中，目標社區的節點是與源社區(社區2)關聯性最高的社區，選擇這兩個社區的節點進行變異操作，關聯性最高的社區能夠提高尋優效果。計算的復制(reproduction)節點數量為2，然后隨機選擇兩個復制節點，將節點5復制為節點2。

圖7 變異算子的操作實例

3 仿真實驗與結果分析

將本算法與其它基于遺傳算法的社區發現算法以及非基于遺傳算法的社區發現算法進行了對比分析，綜合評估本算法的性能。實驗環境為PC機，CPU為Intel Core i7，2.4 GHz主頻，8 GB內存。基于Matlab編程實現本算法。

3.1 性能評價指標

NMI(標準化互信息)是社區發現問題中常用的性能評估指標，NMI定義為下式

(9)

式中：網絡的兩個部分A與B構成了混淆矩陣C，Cij表示屬于A部分中社區i與B部分中社區j的節點數量，CA與CB分別表示A與B部分的社區數量，Ci表示A部分中社區i的節點數量，N表示節點的總數量。如果A=B，那么NMI(A,B)=1；如果A與B完全不同，那么NMI(A,B)=0。NMI值越接近1，說明算法劃分的社區結構與最優網絡結構越相似。

3.2 參數配置

目前已經具有許多基于遺傳算法的社區發現算法，為了評估本文本算法的有效性，首先將本算法與其它基于遺傳算法的社區發現算法進行比較，分別為IGA[12]、GAOM[13]、MAGA[14]。

為了確保對比的公平性，所有的遺傳算法采用相同的參數設置，具體見表2。

表2 遺傳算法的仿真實驗參數

3.3 與基于遺傳算法的社區發現算法比較

3.3.1 benchmark數據集

采用4個常用的公開社交網絡數據集作為benchmark數據集，評估4個基于遺傳算法的社區發現算法的性能，4個社交網絡的描述見表3。

表3 基于遺傳算法的社區發現算法benchmark數據集

3.3.2 社區發現的準確率結果與分析

每個算法對每個benchmark數據集均獨立地運行50次，統計每組數據的平均值與標準偏差。4個算法對4個數據集的社區劃分準確性如圖8所示。從圖中可看出，本算法的NMI平均值與標準偏差均優于其它3個基于遺傳算法的社區發現算法，隨著社交網絡規模的擴大，本算法的優勢更加明顯。本算法的標準偏差也明顯地優于其它3個算法，可看出本算法的社區劃分結果具有較好的魯棒性。

圖8 4個算法對4個數據集的社區劃分準確性(NMI值)

數據集1的網絡規模較小，社區數量也僅有3個，4個社區發現算法的NMI值均較低，遺傳算法對于這種小規模數據集的迭代次數較少，并且容易受到初始化種群的影響，因此小規模數據集的性能低于大規模數據集的性能。但是數據集4的網絡規模約為數據集1的4倍，而IGA[12]、GAOM[13]、MAGA[14]這3個算法的NMI值卻低于數據集2與數據集3，這顯示了這3個遺傳算法未能較好地考慮社交網絡的特點，而本算法設計了基于社區隸屬度的社區數量估計算法，對于不同規模的數據集均能夠獲得較高的準確率。

4個算法對4個數據集的社區劃分模塊性結果(Q函數)如圖9所示。因為4個遺傳算法均將Q函數作為適應度函數，因此Q函數的結果直接反映了4個遺傳算法的最優解結果，可看出4個算法對數據集1,2,3的模塊性結果均在[0.3,0.7]之間，而數據集4提出的最優社區并未考慮模塊性，所以導致GAOM、MAGA兩個算法的模塊性結果小于0.3。

圖9 4個算法對4個數據集的社區劃分模塊性結果(Q函數)

3.3.3 社區發現的時間效率

時間效率是遺傳算法的一個重要指標，在此統計了4個遺傳算法對于數據集4的計算時間，結果見表4。GAOM算法為了解決遺傳算法易于陷入局部最優的問題，其變異算子在每輪迭代過程中均需要計算網絡中每個節點的局部信息以及社區隸屬度值，遺傳算法求解大規模問題的迭代次數往往較多，而GAOM每次迭代的計算量均較大，嚴重影響了計算效率。MAGA是一種基于agent的遺傳算法，該算法的各個agent均需要完成多個復雜的算子，包括：基于分割與合并的鄰居節點競爭算子、混合鄰居節點交叉算子、自適應變異以及自學習算子，這些算子計算量較大，因此MAGA的收斂速度也較慢。IGA通過免疫機制約束了遺傳算法的初始化種群，縮小了初始化搜索空間，因此收斂速度較快，計算速度也較快。本算法將社交網絡中的鄰居節點與鄰接節點納入初始化種群中，并且設計了基于社區隸屬度的社區數量估計算法，有效地減小了網絡的社區空間，并且能夠快速地引導種群的演化過程，本算法獲得了最低的計算時間，此外，計算時間的標準偏差為0.0077，因此本算法的計算效率具有較好的穩定性。

表4 4個社區發現算法對于數據集的計算時間(單位：秒，每組實驗獨立運行50次，統計平均值與標準偏差)

3.4 與一般社區發現算法比較

3.4.1 benchmark數據集

因為本算法的社區隸屬度估計算法考慮了重疊社區與非重疊社區，因此本文采用兩種類型的真實數據集評估本算法的性能，分別見表5與表6，表中給出了重疊社交網絡與非重疊社交網絡的結構介紹。10個數據集的網絡規模均較大，能夠測試本算法對于大規模社交網絡的性能。

表5 重疊社區結構的社交網絡

表6 非重疊社區結構的社交網絡

3.4.2 實驗結果與分析

COMBO、NISE是兩個近期性能較好的社區發現算法，并且這兩個算法同時支持重疊社區與非重疊社區的社交網絡，因此將本算法與這兩個算法進行比較。首先對5個重疊社區的社交網絡進行實驗，每組實驗獨立運行50次，統計NMI的平均值與標準偏差，結果如圖10所示。可看出，本算法對于數據集1,2,3,4的社區檢測準確率均優于其它兩個算法，數據集5的最優社區劃分方案并未考慮模塊性，而本算法成功搜索出最優的模塊性結果，但是與數據集5提出的最優社區劃分方案仍然有一定的差異，因此本算法對于數據集5的NMI值較低，略低于其它兩個算法。

圖10 3個算法的對于社區重疊社交網絡的社區檢測NMI結果

然后對5個非重疊社區的社交網絡進行實驗，每組實驗獨立運行50次，統計NMI的平均值與標準偏差，結果如圖11所示。可看出，本算法對于數據集1,2,3,4的社區檢測準確率均明顯地優于其它兩個算法，數據集5中包含大量位于社區邊界的節點，并且這些節點與其它社區的距離均較為接近，3個社區發現算法對于數據集均獲得了較低的NMI值，3個算法的結果較為接近。

圖11 3個算法的對于社區不重疊社交網絡的社區檢測NMI結果

4 結束語

為了提高大規模社交網絡社區發現算法的準確率與計算效率，設計了一種基于遺傳算法的社區發現算法，采用遺傳算法搜索Q函數的最優解，選擇隨機節點的鄰居節點與鄰接節點作為初始化種群，并且設計了節點對社區的隸屬度計算方案，通過設置合適的閾值能夠控制檢測的社區規模，該方案也能夠預測網絡中的社區數量，為社區的規模進行約束，提高種群演化的準確性。因為本算法的社區隸屬度計算方案同時考慮了節點的社區內部關聯性與外部關聯性，因此能夠同時適用于社區重疊與社區不重疊的社交網絡。該算法對于大規模數據集也具有較高的社區檢測準確率。

因為本算法是一種基于社交網絡模塊性的社區發現算法，如果社區的重疊部分存在密集的連接，則會影響社區的模塊性，這為本算法的社區檢測準確率帶來不利的影響，未來將重點關注不滿足社區模塊性的社交網絡問題。