基于高階信息局部策略的符號網絡社區檢測

楊智翔， 許小可， 肖婧

大連民族大學 信息與通信工程學院，遼寧 大連 116600

現實世界中很多復雜系統都可以用復雜網絡模型來表示, 例如: 社交網絡[1]、 生物網絡[2]、 協作網絡[3]等． 符號網絡作為復雜網絡中一種特殊的網絡, 是指邊具有正或負符號屬性的網絡, 其中正邊和負邊分別表示積極和消極的關系． 例如: 神經元之間存在促進和抑制關系[4]; 社交關系中存在信任和不信任[5-6]． 因此, 符號網絡可以更好地描述節點之間的關系, 符號網絡相關研究具有重要的實際意義．

由于負邊的存在, 使得符號網絡中的社區檢測和無符號網絡中的社區檢測具有明顯區別． 在無符號網絡中, 社區結構定義為一組節點, 這些節點在簇內具有密集連接, 在簇之間具有稀疏連接． 對于符號網絡, 社區結構不僅由連接密度定義, 也由連接的符號定義． 也就是說, 社區內部的正鏈接密集而負鏈接稀疏, 社區之間的負鏈接密集而正鏈接稀疏． 然而, 在現實符號網絡中, 往往社區內部存在一些負鏈接, 同樣社區間也存在一些正鏈接, 這也使符號網絡社區檢測面臨巨大的挑戰．

目前針對符號網絡社區檢測問題的方法大致分為如下幾類: 基于譜聚類的方法[7-8]、 基于概率生成模型的方法[9]、 基于模塊度優化的方法[10]等． 其中模塊度優化是最典型的復雜網絡社區檢測方法之一, 由于其高精確度和強可移植性等優點被廣泛應用． 模因算法作為解決組合優化問題的一個非常強大的工具, 適合于解決模塊度優化的NP難問題, 已被普遍應用于符號網絡社區檢測中． 它的靈感來源于自然系統模型, 該模型將種群的進化適應與個體在其成員生命周期內的學習相結合[11]． 模因算法是一種基于群體的元啟發式算法, 它融合了不同的搜索策略, 即全局搜索策略和局部搜索策略, 在解決優化問題方面, 模因算法已被證明比傳統進化算法更高效[10]．

局部搜索策略作為模因算法中重要組成部分之一, 它能極大地提高全局搜索算法尋找全局最優解的速度, 并輔助提升全局最優化性能． 近年來, 局部搜索策略常被學者們用于加速全局算法的收斂． 如Li等[10]提出并比較了EA-SN和CSA-SN兩種進化算法, 以及EAHC-SN和CSAHC-SN兩種模因算法． 模因算法在進化算法基礎上使用了爬山策略, 僅對最優種群個體進行局部搜索操作, 每次迭代都使用貪婪算法對每個節點選擇最優適應度, 實驗表明模因算法優于進化算法． Amelio等[12]提出了一種結合遺傳算法和局部搜索的符號網絡多目標社區檢測方法, 其局部搜索策略在爬山策略的基礎上增加了僅將節點移動至正相連的鄰居節點社區的限定條件, 若符號模塊度增加則保留移動, 反之則不移動． Che等[13]提出了一種新穎的模因算法(MACD-SN), 其中結合了一種新的局部搜索算法, 能夠以一定的概率跳出局部最佳結果, 并快速接近全局最優值．

上述方法僅簡單地利用節點和連邊等低階結構信息進行局部搜索操作, 忽略了網絡中廣泛存在且具有統計意義的高階組織結構, 如網絡模體[14-15]等, 因此對于提升符號網絡社區檢測性能相對有限． 模體是復雜網絡中的基本拓撲和功能單元[14-16], 而符號模體作為一種連邊具有正或負符號屬性的特殊模體, 可展現出符號網絡節點間更豐富且有意義的拓撲連接關系, 對于局部搜索操作具有很強的指導性意義．

針對上述問題, 本研究提出了一種基于符號模體的三元組局部搜索策略(Triad Local Search, TLS)． 設計了一種基于符號模體進行社區遷移的新方法, 將傳統社區編號在二元組之間的遷移擴展到了三元組, 綜合利用符號網絡低階和高階拓撲結構信息, 進一步優化節點的結構平衡性, 提升算法收斂速度． 為驗證局部策略的有效性, TLS算法同差分進化策略構建成模因算法DE-SN, 實驗結果表明TLS算法在社區劃分的精確性和質量性表現出一定優勢． 將TLS算法遷移至元啟發式優化算法為共生生物搜索算法和遺傳算法的模因算法中, 在模型網絡和實證網絡上均驗證了新算法的通用性．

1 基礎概念和數據集

1.1 符號網絡定義

符號網絡社區檢測旨在挖掘社區內部正鏈接密且社區之間負鏈接密集的社區劃分結構． 本研究主要考慮無向符號網絡． 一個符號網絡可以抽象為一個圖G=(V,E), 其中V={v1,v2, …,vn}代表節點(頂點)集合,E={(vi,vj)|vi,vj∈V∩i≠j}代表邊(鏈接)集合． 圖G還可以表示成加權鄰接矩陣A=(Aij)n×n, 其中n代表節點數目, 若節點vi和vj之間存在正邊(負邊)相連, 則Aij=1(Aij=-1); 若節點vi和vj之間不存在連邊, 則Aij=0． 圖G的一個社區劃分可表示為C={C1,C2, …,Ck}且Ci?V, 其中k代表社區數目, 表示由一組節點組成的第i個社區． 符號網絡上的社區檢測問題可以定義為公式(1)的形式[17]．

(1)

式中:p,q=1,2,…,k, 且p≠q．

1.2 評價指標

1.2.1 符號模塊度QS

在無符號網絡社區檢測中, Newman等[18]定義的模塊度函數是最常用的指標之一, 但由于符號網絡中存在負邊, 因此原始的模塊度Q無法直接應用于符號網絡． Gómez等[19]基于正邊和負邊的貢獻, 改進了模塊度定義, 使其擴展到符號網絡． 本研究中, 將符號模塊度QS作為目標函數, 符號網絡模塊度QS定義為:

(2)

1.2.2 歸一化互信息

歸一化互信息(Normalized Mutual Information, NMI)[20]可用于評估算法檢測結果的精確性． 假設A和B是一個網絡的兩個劃分, 那么歸一化互信息定義為:

(3)

式中:N為網絡的節點數量;C為混淆矩陣;Cij為同時隸屬于A中的第i個社區和B中第j個社區的節點數量;CA和CB分別為劃分A和B中的社區數量;Ci和Cj分別為C中第i行和第j列元素的和．NMI取值范圍為[0, 1], 越接近1, 表示兩個劃分越相似．

1.2.3 節點Frustration指數

Frustration指數[21-22]是目前衡量符號網絡結構平衡最廣泛的指標之一, 它統計的是社區內部的負鏈接數量與社區之間的正鏈接數量的總數, 表示社區的不平衡程度, Frustration指數越低代表社區劃分越穩定． Frustration指數(Frustration of Node,FN)可定義為:

(4)

式中:vi為對象節點i;Ci為節點i所屬社區;δ(Ci,Cj)為罰函數;FN(vi)表示節點i的連邊中在社區內部的負鏈接數量與社區之間的正鏈接數量的總數, 它代表節點i的不平衡程度, 值越小節點i越穩定, 當FN=0時, 節點i達到結構平衡．

1.3 數據集

1.3.1 模型網絡

選擇Yang等[17]設計的隨機生成符號網絡模型, 生成實驗使用的合成符號網絡, 該模型可以描述為:

SG(c,n,k,pin,p-,p+)

(5)

式中:c為網絡中社區的數量;n為每個社區包含的節點數量;k為每個節點的度;pin為每個節點連接同一社區中其他節點的概率;p-為負鏈接出現在社區內的概率;p+為正鏈接出現在社區之間的概率． 為模擬現實世界中不平衡網絡結構, 并且控制生成的社區內部和社區之間的連邊概率相同, 因此pin取值為0.5, 本研究中生成了以下3種不同的不平衡網絡對各局部策略進行評估．

①SG(4, 32, 32, 0.5, 0,p+):p+以0.1為間隔在[0, 1]范圍內取值． 該網絡由128個節點構成, 分成4個社區, 每個社區包含32個節點． 每個節點的度為32, 分別以0.5的比率連接社區內部和社區外部的節點． 社區內部負鏈接出現的概率為0, 社區之間相連以p+比率為正鏈接．

②SG(4, 32, 32, 0.5,p-, 0):p-以0.1為間隔在[0, 1]范圍內取值． 該網絡社區之間正鏈接出現的概率為0, 社區內部相連以p-比率為負鏈接．

③SG(4, 32, 32, 0.5,p-,p+):p-和p+分別以0.1為間隔在[0, 0.5]范圍內取值． 該網絡社區內部相連以p-比率為負鏈接, 社區之間相連以p+比率為正鏈接．

1.3.2 實證網絡

為檢驗算法在現實世界網絡中的可行性及性能優勢, 選擇2個社交網絡和4個生物網絡作為實驗數據． 社交網絡包括描述斯洛文尼亞議會關系的網絡(Slovene Parliamentary Party, SPP)[23]和描述新幾內亞高地的網絡(Gahuku-Gama Subtribes, GGS)[24]． 生物網絡分別為EGFR網絡[25](表皮生長因子受體途徑網絡)、 Macrophage網絡[26](巨噬細胞網絡)、 Yeast網絡[15](酵母網絡)和Ecoli網絡[27](大腸桿菌的基因調控網絡)． 以上實證網絡都從SNAP[28]中獲得, 具體信息如表1所示．

表1 實證網絡信息

2 算法描述

本節首先介紹現有符號網絡中具有代表性的局部搜索算法, 再重點闡述提出的三元組局部搜索策略TLS． 局部搜索策略是模因算法優于傳統進化算法的主要原因之一, 以其收斂速度快、 擴展性強等優勢, 常被用于提高求解效率和精度． 如圖1所示的模因算法流程包括生成初始種群、 計算所有個體適應度值、 元啟發式優化算法、 更新個體適應度值和局部搜索策略, 本研究提出了一種三元組局部搜索策略(Triad Local Search, TLS)應用于模因框架, 旨在提升其在符號網絡社區檢測的性能． 為了展示提出策略的優越性, 在模因框架中選取了差分進化算法[29](Differential Evolution, DE)作為元啟發式優化算法, 與TLS策略構成DE-SNTLS框架進行實驗驗證． 同時, 又在模因框架中選取了共生生物搜索[30](Symbiotic Organisms Search, SOS)和遺傳算法[31](Genetic Algorithm, GA)作為元啟發式優化算法, 與TLS策略構成SOS-SNTLS和GA-SNTLS框架, 驗證本研究提出策略的通用性．

圖1 模因算法流程圖

2.1 基于低階信息的局部搜索算法

現有符號網絡上代表性的局部搜索算法有以下幾種: 爬山算法[32-33]、 利用正邊信息的改進爬山算法[12]以及模因算法MACD-SN[13]中具有概率跳出局部最優的局部搜索策略．

2.1.1 爬山算法

爬山算法(Hill Climbing, HC)是一種局部擇優的啟發式方法, 核心思想是貪婪地尋找每個節點局部最優適應度, 缺點是極易陷入局部最優． 它是一種經典的局部搜索算法, 被廣泛使用于無符號網絡社區檢測和符號網絡社區檢測, 如Gong等[33]將爬山策略與算法相結合實現無符號網絡社區檢測, Li等[10]在其基礎上將爬山策略應用于符號網絡．

HC算法的詳細說明如圖2所示, 9個節點對應6個社區的結構示例圖為EGFR網絡提取的一個子圖． 在一次局部搜索操作過程中, 節點A被選作中心節點(對象節點), 其對應的社區編號為1． 初始子圖中, 中心節點有一個負邊相連的鄰居節點B和4個正邊相連的鄰居節點{C, E, G, H}, 其社區編號分別對應為{2, 3, 4, 5, 6}, 故節點A有4條不平衡連邊(圖中紅色連邊), 即節點A初始的FN值為4． 在HC操作中, 首先將中心節點所有鄰居節點的社區作為候選社區(滿足條件的鄰居社區), 然后分別計算節點A歸屬于每個候選社區后的符號模塊度, 最后選擇符號模塊度最大的候選社區作為遷移社區． 圖中當中心節點的社區為6時取得QS最大值為0.143, 因此社區編號6作為遷移社區從遷移節點(被選中的候選節點)遷移至中心節點, 即實現了社區編號在二元組之間的遷移．

圖2 HC算法在EGFR網絡子圖上的詳細說明

HC操作后中心節點A的社區編號更改為6, 節點A的FN值降至3,QS從0.087優化至0.143, 達到HC操作的最優結果． HC算法未利用符號信息, 而是貪婪地尋找符號模塊度最大的遷移社區, 此操作極易使算法陷入局部最優, 并且HC算法缺少跳出局部最優的操作．

2.1.2 改進爬山算法

Amelio等[12]提出算法中使用的局部搜索策略是在爬山策略的基礎上, 增加了僅將節點移動至正相連的鄰居節點社區的限定條件． 改進爬山策略(Hill Climbing Using Positive, HC-P)簡單利用了符號信息, 使爬山策略更適用于符號網絡．

HC-P算法詳細說明如圖3所示, 唯一與HC算法操作不同之處在于中心節點只考慮將正邊相連的鄰居社區{3, 4, 5, 6}作為候選社區, 而負邊相連的鄰居社區2不做考慮, 最后從候選社區中選擇符號模塊度最大社區作為遷移社區． HC-P操作后中心節點A的社區同樣更改為6, 節點A的FN值也降至3,QS從0.087優化至0.143, 達到HC-P操作的最優結果． HC-P算法利用符號信息對候選社區進行篩選, 相較于HC算法的效率和性能有所提升, 但HC-P算法并未對爬山策略極易陷入局部最優的缺陷進行改進．

圖3 HC-P算法在EGFR網絡子圖上的詳細說明

2.1.3 MACD-SN中的局部搜索策略

Che等[13]提出的符號網絡社區檢測算法中使用了局部搜索策略(Local Seek, LS), 使用作者自定義的算子(社區失衡度CID, 表示同社區內節點的平均Frustration值)作為局部優化目標． LS算法結合了符號信息, 并引入概率ρ, 一定概率接受較差的個體, 有利于算法跳出局部最優解．

LS算法的詳細說明如圖4所示, 在同一個子圖上, 節點A初始的FN值為4． 首先, LS算法將正邊相連的鄰居社區{3, 4, 5, 6}作為候選社區, 若無正邊相連的鄰居社區, 才會將負邊相連的鄰居社區作為候選社區． 其次, 選擇CID最小的候選社區6再對比前后QS, 若QS增大或者存在一定概率ρ情況下, 則將該候選社區作為遷移社區; 反之, 不進行社區遷移, 中心節點社區保持不變． 由于節點A的社區改為6時,QS增大至0.143, 因此, LS操作后節點A的社區更換為6, 且FN值為3, 達到LS操作的最優結果．

圖4 LS算法在EGFR網絡子圖上的詳細說明

但對于真實社區劃分為社區間正邊數量較多的網絡, 受局部優化目標影響, LS算法容易將正邊相連不同社區的節點劃分成同一社區, 從而導致社區劃分質量不佳．

2.2 基于高階信息的局部搜索算法

上一小節中的3種基于低階信息的局部搜索算法, 社區只在二元組之間進行遷移, 即從遷移節點遷移至中心節點, 這種遷移方式的效率不高, 每次操作只對中心節點進行社區調整, 中心節點鄰域內的不合理連邊調整緩慢． 此外, 單純關注局部目標來選擇局部優化最佳的候選社區(候選節點)作為遷移對象, 往往會陷入局部最優的社區劃分．

為解決上述問題, 提出一種基于符號模體的三元組局部搜索算法(Triad Local Search, TLS), 可以有效提高收斂速度和局部性能． 核心思想為通過綜合利用符號網絡低階和高階拓撲結構信息, 優化節點的不平衡程度, 盡可能達到節點的結構平衡, 從而提升社區劃分質量． TLS算法對符號網絡高階和低階信息的利用, 分別體現在基于三階符號模體進行三元組社區遷移和依據低階連邊符號信息選擇候選節點． 三元組社區遷移是將遷移節點遷移至中心節點的社區編號再傳遞給其他候選節點, 為更準確表示該遷移模式并探索更深層的規律, 本研究使用三階符號模體表示三元組社區遷移, 并從中挖掘高階結構信息, 進一步指導局部搜索操作．

下面詳細介紹TLS算法具體實現． 研究中主要考慮無向的三階符號模體, 如圖5所示一共有7個三階的無向符號模體, 其中S1,S2和S3只有兩條連邊． 符號模體上的社區遷移需要滿足以下2個條件:

圖5 無向的三階符號模體

1) 根據正鏈接和負鏈接的符號屬性, 社區遷移只發生在節點間的正鏈接, 而社區不可以在負鏈接進行遷移．

2) 模體中的社區遷移只能通過中心節點進行, 兩個都為非中心節點, 無法進行社區遷移．

圖5中的7種符號模體依據中心節點位置的不同, 將會有12種不同的符號模體． 然而, 研究發現并非12種符號模體都能夠滿足符號模體的社區遷移條件, 只有圖6中的3種符號模體滿足遷移條件, 其中紅色節點表示中心節點, 將該模體命名為中心節點符號模體, 并做如下定義:

圖6 中心節點符號模體

定義1中心節點符號模體(Central Node Signed Motif,SC)． 滿足中心節點職能的符號模體稱為中心節點符號模體, 即中心節點符號模體可以讓中心節點實現社區信息的接收和傳遞．

由于非中心節點符號模體不滿足社區遷移條件, 即不參與社區遷移, 因此在TLS算法中只需要關注3種中心節點符號模體以提高計算效率． 算法1為TLS算法偽代碼, 主要步驟如下:

1) 隨機選擇目標個體的若干個節點進行優化, 獲得中心節點正邊相連的鄰居節點(作為候選節點)及對應社區編號(第1行至第4行);

2) 中心節點在候選節點中隨機選擇一個節點作為遷移節點, 并將遷移節點的遷移社區傳遞給中心節點, 實現二元組之間的社區遷移(第5行至第6行);

3) 尋找所有包含中心節點和遷移節點的中心節點符號模體, 為加快代碼執行效率, 可將尋找模體的操作簡化為求中心節點正邊相連且不同社區的鄰居節點． 在進行社區遷移時進行條件判斷, 若傳遞后的符號模塊度大于原符號模塊度或在一定閾值ρ內, 則確認傳遞, 鄰居節點社區編號替換為中心節點的社區編號, 從而實現了社區編號在三元組(模體)之間的遷移． 否則, 傳遞失敗, 鄰居節點社區編號保持不變(第7行至第16行)．

算法1 TLS算法輸入: 目標個體X, 鄰接矩陣A, 閾值參數ρ輸出: 優化后新個體Xnew1. nrand=random(1, n)2. forNc=1 tonranddo3. neighborsp=get neighbors positive(Nc)4. commID(neighborsp)=X[neighborsp]5. Nm=random(neighborsp)6. commID(Nc)=commID(Nm)7. for eachnp∈neighborspdo8. if commID(np)≠commID(Nc) then9. QSold=compute QS10. QSnew=compute QS11. ifQSnew>QSoldor random number r≤ρthen12. commID(np)=commID(Nc)13. end if14. end if15. end for16. end for17. 輸出優化后新個體Xnew

TLS算法的詳細說明如圖7所示, 同樣以EGFR網絡子圖為例, 在一次隨機選擇若干個節點進行局部搜索操作時, 節點A被選作中心節點, 其對應的社區編號為1． 在節點A進行TLS操作時, 初始的FN值為4． 首先, 檢查中心節點所有鄰居節點, 可以發現有一個負邊相連的鄰居節點B和4個正邊相連的鄰居節點{C, E, G, H}, 其社區編號分別對應為{2, 3, 4, 5, 6}． 其次, 將正邊相連的鄰居節點作為候選節點, 并隨機選擇一個候選節點E作為遷移節點, 遷移節點E將遷移社區4傳遞給中心節點A, 此時節點A的FN值減小至3,QS降為0.066． 然后, 尋找所有包含中心節點和遷移節點的中心節點符號模體, 并逐個進行社區遷移． 如圖有3個滿足條件的符號模體, 分別為S1(E, A, C),S4(E, A, G)和S5(E, A, H)． 三元組社區遷移是否成功在于遷移后的符號模塊度是否增大, 并存在概率ρ接受較差情況． 因為不同模體的判別順序不影響最終結果, 所以先對S1(E, A, C)進行判別, 發現節點C社區更改為4后,FN值減小至2,QS增大至0.092, 符合判別條件, 即接受社區遷移． 再對S4(E, A, G)進行判別, 節點G社區更改為4后,FN值減小至1,QS增大至0.184, 接受社區遷移． 最后對S5(E, A, H)進行判別, 若節點H的社區更改為4, 則QS降至0.002, 假設此時未能達到概率ρ, 即不接受這個較差的情況, 那么最終TLS操作將以QS為0.184的個體輸出．

上述操作不難發現, TLS算法與傳統的局部策略截然不同． TLS算法不依賴局部目標隨機選擇候選社區(候選節點)方式, 有助于擴大解空間, 避免陷入局部最優解． 雖然隨機選擇候選社區會獲得更差的社區結構, 如圖7中QS不升反降． 但在TLS操作后期, 以節點的結構平衡(FN=0)為優化方向的三元組社區遷移, 能夠加速中心節點及鄰域收斂至的最優社區劃分． 以EGFR網絡子圖為例, TLS算法能夠獲得3種對比算法都無法獲得的社區劃分, 并且相較于三者的社區劃分質量更優．

2.3 算法復雜度分析

HC算法、 HC-P算法和LS算法的平均時間復雜度都為O(n*d), 其中d代表網絡G中節點的平均度． 在最差的情況下, 網絡G為完全圖, 因此3種算法的時間復雜度為O(n2)． TLS算法平均時間復雜度同樣為O(n*d), 最差時間復雜度為O(n2), 但不同于其他3種算法, 并不是對一個目標個體的所有節點都進行局部操作, 而是隨機選擇若干個節點, 實際運行效率會更高．

3 實驗結果與分析

本節將對提出TLS算法的性能進行驗證, 與現有典型的局部搜索算法進行對比, 分別從不同正負邊比例的模型網絡和實證網絡的實驗來檢驗分析．

3.1 實驗設置

3.1.1 對比策略

為檢驗DE-SN算法在符號網絡中的性能, 并重點驗證提出的三元組局部搜索算法TLS與其他局部策略相比更具優勢, 將DE-SN算法中的局部策略分別替換為HC算法、 HC-P算法、 LS算法, 從而可以得到DE-SNHC,DE-SNHC-P,DE-SNLS3種對比算法．

3.1.2 參數設置

上述搜索策略參數設置均采用原文獻中的推薦值, 其中DE算法中變異因子F取值為0.9, 交叉因子CR取值為0.3． DE-SN算法設置種群規模NP為100, 最大迭代次數tmax為100． 為保持種群個體多樣性及探索能力, 防止算法過早收斂, 僅選擇模塊度值較為優異的前10%個體作為目標個體進行局部操作． 另外, 以下實驗中LS局部搜索策略參數ρ使用原文推薦值0.15．

3.2 模型網絡性能測試

首先, 為檢驗社區之間的正邊對DE-SN算法檢測性能的影響, 在SG(4, 32, 32, 0.5, 0,p+)網絡集合上, 對DE-SN算法與各對比算法進行性能測試． TLS算法的閾值參數ρ取值為0進行測試． 所有算法在模型網絡上的實驗結果如圖8a所示, 圖中數據點代表各算法分別在11個SG(4, 32, 32, 0.5, 0,p+)網絡上獨立運行20次得出社區劃分NMI值的平均值．

圖8 模型網絡上4種DE-SN算法的NMI檢測結果

從圖8a所示結果中可知, 當p+取值為[0, 0.5]時, DE-SNTLS,DE-SNHC和DE-SNHC-P算法在SG(4, 32, 32, 0.5, 0,p+)網絡上均能夠穩定地檢測得到全局最優社區劃分, 對應NMI平均值均達到1.0． 當p+取值為[0.6, 1]時, DE-SNHC和DE-SNHC-P算法NMI平均值接近1.0．p+為0.8時, DE-SNTLS的NMI值為1． 然而DE-SNLS算法的性能表現相對不佳, 當p+≤0.3時, DE-SNLS算法的性能逐漸下降． 當p+>0.3時, 性能趨于相對平衡． DE-SNTLS算法在SG(4, 32, 32, 0.5, 0,p+)網絡上的檢測精度顯著優于DE-SNLS算法, 且與DE-SNHC和DE-SNHC-P算法檢測精度大致相同．

其次, 為檢驗社區內部的負邊對DE-SN算法檢測性能的影響, 在SG(4, 32, 32, 0.5,p-, 0)網絡集合上, 同樣進行各DE-SN算法的測試及對比分析． TLS算法的閾值參數ρ取值為0.15進行測試． 圖8b中數據點代表各算法分別在11個SG(4, 32, 32, 0.5,p-, 0)網絡上獨立運行20次所得社區劃分NMI值的平均值．

從圖8b所示結果可以看出, DE-SNTLS在SG(4, 32, 32, 0.5,p-, 0)網絡上能夠獲得相對最優的NMI, 與其他對比算法相比具有較為明顯的性能優勢． DE-SNHC在p->0.2時,NMI值下降趨勢最為明顯, 且逐漸趨于0． DE-SNTLS,DE-SNHC-P和DE-SNLS在p->0.3時, 所檢測得NMI值開始逐漸下降, 而DE-SNTLS整體檢測性能下降最為緩慢, 對于任意p-的取值, 都能夠優于其他算法．

最后, 為檢驗社區之間的正邊和社區內部的負邊同時存在對DE-SN算法檢測性能的影響． 在SG(4, 32, 32, 0.5,p-,p+)網絡集合上, 進行各DE-SN算法的測試及對比分析． 此時, TLS算法的閾值參數ρ取值為0進行測試． 各圖中數據點代表各算法在36個網絡上獨立運行20次所得社區劃分NMI值的平均值．

如圖9所示, 每張熱力子圖的每一小塊表示對應p-和p+取值, 算法20次檢測得到NMI均值． DE-SNTLS與DE-SNHC和DE-SNHC-P算法檢測結果十分相近, 但仔細觀察可以發現, 在(p-,p+)=(0.4, 0),(p-,p+)=(0.4, 0.1),(p-,p+)=(0.5, 0)和(p-,p+)=(0.5, 0.1)4個塊的檢測精確度要顯著高于DE-SNHC和DE-SNHC-P算法檢測精確度． 然而, DE-SNLS的檢測結果相對較差, 僅在(p-,p+)=(0, 0)和(p-,p+)=(0.1, 0)時, 檢測得NMI值為1.0, 在(p-,p+)=(0.2, 0)和(p-,p+)=(0.3, 0)時, 檢測得NMI值接近1．

圖9 SG(4, 32, 32, 0.5, p-, p+)網絡上4種DE-SN算法的NMI檢測結果

以上模型網絡的實驗表明, TLS算法相較于其他代表性局部搜索算法, 在精確性和穩定性上能夠表現出一定優勢．

3.3 實證網絡性能測試

將DE-SN算法在表1所示2個具有真實社區劃分的符號社交網絡和4個沒有真實社區劃分的符號生物網絡上進行測試, 并與算法進行對比, 社交網絡和生物網絡實驗結果分別如表2和表3所示． 此時, TLS算法的閾值參數ρ取值為0, 同時為確保生物網絡檢測盡可能達到收斂, 迭代次數tmax取值為200． 表3中數據為各算法在每個網絡上獨立運行20次, 所得社區劃分對應符號模塊度QS的平均值和NMI的平均值．

表2 符號社交網絡上各DE-SN算法檢測結果

表3 符號生物網絡上各DE-SN算法檢測結果

表3中的實驗結果表明, DE-SNTLS能夠在社交網絡上達到最優社區劃分的同時, 能在所有生物網絡上獲得比對比算法更優的QS平均值． TLS算法相比較于其他典型代表性的局部搜索算法, 具有較好的質量性和穩定性．

4 通用性和魯棒性檢驗

為深入驗證TLS算法可提升符號網絡社區檢測的局部搜索性能, 并檢驗TLS算法在不同優化策略的模因算法上的通用性． 基于模因算法框架, 選擇共生生物搜索和遺傳算法分別作為模因算法中的元啟發式算法進行全局搜索, TLS算法作為局部搜索策略, 構建SOS-SN算法和GA-SN算法2個新的模因算法． 同上一節中的對比算法、 參數設置和測試數據集對各算法進行實驗．

4.1 SOS-SN算法檢驗分析

SOS-SN算法在模型網絡上的實驗結果如圖10a和10b所示． 從圖10a的實驗結果發現, 對于任意p+的取值, SOS-SNTLS與SOS-SNHC和SOS-SNHC-P大致相同, 當p+取值為[0, 0.5]時, 3種算法檢測得NMI均值都為1.0, 當p+取值為[0.5, 1]時, 3種算法取得NMI均值近似1.0． 而SOS-SNLS的檢測性能依舊隨著p+的增大而整體呈現下降趨勢． 從圖10b的實驗結果發現, 對于不同p-取值, SOS-SNTLS依舊能夠保持相對最優的檢測精度．

圖10 模型網絡上4種SOS-SN算法的NMI檢測結果

如圖11檢驗社區之間的正邊和社區內部的負邊同時存在對SOS-SN算法檢測性能的影響, SOS-SNTLS依舊能夠明顯的優于SOS-SNLS檢測結果, 并且在(p-,p+)=(0.4, 0),(p-,p+)=(0.4, 0.1),(p-,p+)=(0.5, 0)和(p-,p+)=(0.5, 0.1) 4個塊的檢測精確度依舊高于SOS-SNHC和SOS-SNHC-P法檢測精確度．

圖11 SG(4, 32, 32, 0.5, p-, p+)網絡上4種SOS-SN算法的NMI檢測結果

在實證網絡上對SOS-SN算法進行性能檢驗, 由于SPP網絡和GGS網絡相對簡單, 所有算法都能獲得最優社區劃分, 故不再展示． 如表4所示為各個SOS-SN算法在符號生物網絡上的檢測結果, TLS算法在生物網絡上與對比算法相比依舊表現出明顯的優勢．

4.2 GA-SN算法檢驗分析

GA-SN算法在模型網絡上的實驗結果如圖12a和12b所示． 從圖12a的實驗結果發現, GA-SNTLS,GA-SNHC和GA-SNHC-P在GA-SN算法上的實驗結果十分相近． 而GA-SNLS的檢測性能依舊較差, 當p+取值為[0, 0.5]時, 檢測精度緩慢下降, 但當p+>0.5時, GA-SNLS的檢測性能下降明顯． 從圖12b的實驗結果發現, GA-SNTLS的檢測性能依舊能夠保持相對最優． 如圖13為4種算法的熱力圖所示, GA-SNTLS依舊能夠在大多數的區塊上優于其他算法的檢測結果． 同樣在符號生物網絡上對GA-SN算法進行性能檢驗． 如表5符號生物網絡上, 除了在Macrophage網絡上, GA-SNLS的質量性檢測結果要優于GA-SNTLS． 在其他生物網絡上, GA-SNTLS的檢測結果都要優于其他對比算法．

圖12 模型網絡上4種GA-SN算法的NMI檢測結果

表5 符號生物網絡上各GA-SN算法檢測結果

根據以上所有實驗結果表明, 在SOS-SN算法和GA-SN算法中, TLS算法輔助全局搜索算法的社區檢測性能依舊普遍優于其他對比局部搜索策略． 本研究提出的TLS算法可以與不同全局搜索算法相結合, 并輔助算法獲得更優的社區劃分結果, 從而驗證了TLS算法擁有較好的通用性和魯棒性．

5 結論

本研究提出了一種基于符號模體的三元組局部搜索算法TLS． 該算法采用了一種基于符號模體進行社區遷移的新方法, 將傳統社區編號在二元組之間的遷移擴展到了三元組, 綜合利用了符號網絡低階和高階拓撲結構信息, 進一步優化節點的結構平衡性, 提升算法收斂速度和檢測性能． 為驗證提出的局部搜索算法社區檢測性能, 將TLS算法同差分進化策略構建成模因算法DE-SN, 在模型網絡和不同規模及特性的實證網絡上進行了檢驗, 并分別將爬山策略HC、 改進爬山策略HC-P和MACD-SN算法中使用的局部搜索方法LS作為對比局部策略進行對比分析． 實驗結果表明, TLS算法能夠在模型網絡上獲得更加精確和穩定的檢測結果, 并且在實證網絡上同樣表現出相對較好的質量性和穩定性． 此外, 通過將TLS算法遷移至元啟發式優化算法為共生生物搜索算法和遺傳算法的模因算法中, 分別構建了SOS-SN算法和GA-SN算法, 在模型網絡和實證網絡上均驗證了TLS算法的通用性．

本研究提升了現有符號網絡社區檢測的局部搜索策略性能, 拓展了模體理論的應用場景, 有助于加深對網絡結構和功能特性的理解． 未來研究中將擴展到有向符號網絡和加權符號網絡等, 使提出的局部搜索算法能夠適應更多不同類型復雜網絡應用需求．