應對顯著變化的動態社區檢測方法

摘 要：現實中的網絡總是不斷變化，網絡形態和連接關系也在隨著時間推移而不斷演變，在動態網絡中發現社區的變化一直是個重要課題。當這種變化較為顯著時，將導致社區檢測算法難以有效利用前一個網絡快照中有價值的信息，從而導致下一個時間步的負遷移。為解決算法無法較好適應網絡突變問題，提出了一個基于遺傳進化思想和高階知識轉移策略的動態社區檢測算法。首先利用相鄰快照的鄰接矩陣相似度確定使用一階或高階信息，然后利用蛛網模型進行種群初始化，再通過非支配排序遺傳算法NSGA-Ⅱ迭代出位于Pareto前沿的多目標最優解，并設計了新的基因交叉方式以提高種群多樣性。最后通過在多個真實數據集及模擬數據集上的實驗結果表明，與現有算法相比，該算法在發生網絡劇變時能獲得時間平滑性更高的社區檢測結果，同時也能保持良好的社區模塊化程度。

關鍵詞：顯著變化；動態網絡；高階信息；社區檢測

中圖分類號：TP301.6 文獻標志碼：A 文章編號：1001-3695（2024）10-012-2962-08

doi：10.19734/j.issn.1001-3695.2024.01.0024

Dynamic community detection method for coping with significant changes

Liu Ao， Zhang Junjie， Wang Huan， Zhang Qingming

（School of Computer Science & Technology， Southwest University of Science & Technology， Mianyang Sichuan 621000， China）

Abstract：In real-world networks， the structure and connections are constantly evolving over time. Detecting community changes within dynamic networks has always been an important research topic. When such changes are significant， it leads to difficulty for community detection algorithms to effectively utilize valuable information from the previous network snapshot， resulting in negative transfer in the next time step. To address the issue of poor algorithm adaptability to network mutations， this paper proposed a dynamic community detection algorithm based on genetic evolution ideas and higher-order knowledge transfer strategies. Firstly， it used the adjacency matrix similarity of adjacent snapshots to determine the use of first-order or higher-order information. Then， it employed the spider Web model for population initialization， followed by the non-dominated sorting genetic algorithm NSGA-Ⅱ to iteratively obtain multi-objective optimal solutions on the Pareto front. It designed a novel gene crossover method to enhance population diversity. Finally， experimental results on multiple real and simulated datasets demonstrate that， compared to existing algorithms， the proposed method achieves higher temporal smoothness in community detection results during network upheavals while maintaining a good community modularity level.

Key words：significant changes; dynamic networks; higher-order information; community detection

0 引言

動態社區檢測（dynamic community detect，DCD）對于挖掘現實世界網絡中的復雜關系變化起著至關重要的作用，是事件檢測、趨勢分析和用戶行為分析的重要工具。在交通網絡［1］、金融網絡［2］、社交網絡［3，4］和生物網絡［5］等許多領域中表示動態社區的圖都被廣泛運用。例如在醫療保健領域，社區檢測算法可以幫助人們理解和預測疾病的傳播，以及對醫療資源的優化配置，為醫療決策提供有力的數據支持。此外，通過藥物處方網絡，可以發現可能的藥物濫用或欺詐行為；在營銷和廣告領域，公司可以利用動態社區檢測來根據用戶不斷變化的偏好和行為量身定制他們的策略，從而增強客戶參與度和品牌忠誠度；在城市規劃和交通管理中，也可以通過社區檢測算法挖掘的信息優化交通流量和緩解擁堵。許多方法也被提出用于發現和研究社區結構，如量子行走［6］、譜聚類［7］、深度學習［8］以及非負矩陣分解［9］。由于動態社區檢測要求在網絡演化過程中持續地調整社區結構，并且需要考慮社區的模塊化結構及其連續性等因素，所以DCD問題是NP難的。多數工作采用進化算法（EAs）有效解決此問題，EAs也已成為了其中一個主要的解決方案［10，11］。Li等人［12］就將具有時間平滑性的社區檢測模式構建為多目標問題，提出了兩種適用于社區的鄰域融合策略：鄰域多樣性策略和鄰域集群策略。除此之外，Yin等人［13］提出了一種高效有效的多目標方法，即 DYN-MODPSO，并分別修改和增強了傳統的進化聚類框架和粒子群算法。

多數動態社區檢測算法都引入了時間平滑性［14～16］的概念，旨在揭示網絡中的潛在模式、趨勢和周期性變化，為更深入的社區分析提供基礎。然而，在網絡存在嚴重波動時，社區的急劇變化可能使得算法難以追蹤其長期演化趨勢，對社區結構變化的細粒度理解也將受到挑戰。對于多數常用的動態社區檢測算法，在算法進行之前，通常都有一個假設：從一個時間步到下一個時間步的變化是比較平緩的。當事實與這一假設相互背離時，這些算法的性能往往會下降。其有兩點啟發：一方面，現有的動態社區檢測算法不能較好地適應社區結構在相鄰時間步間發生顯著變化的情況，從而使前一個社區檢測結果給后續的檢測任務帶來負遷移；另一方面，利用先前時間步的社區信息來提高動態社區檢測算法性能是可行的。

本文通過實驗確認了動態網絡中發生突變情況的存在，所提出的方法將根據不同時間步的變化程度使用一階或者高階信息進行社區檢測。主要工作如下：a）面向具有顯著變化的動態社區檢測問題，提出了一個動態社區檢測算法HOGA；b）設計了一個新的目標函數，利用高階信息轉移策略CV-HOCV保留先前社區劃分的優勢，從而減少網絡巨大變化帶來的負遷移；c）在利用非支配排序遺傳算法NSGA-Ⅱ［17］進行迭代計算時，通過優化后的交叉和變異方式使獲得的子代種群更具多樣性，提高了算法迭代效率。

1 相關工作

多數基于進化的動態社區檢測算法都將動態社區檢測問題建模為多目標優化問題（MOP）。在動態社區檢測領域，解決此類問題的普遍方法是將非支配個體進行排序后進行迭代擇優，例如基于非支配排序的多目標進化算法（NSGA）［18］。這些基于進化聚類的方法在計算機領域也引起了越來越多的興趣［19］。本文方法便是以多目標優化為基礎，同時結合了間接遷移學習的策略對動態網絡進行社區劃分。因此，本章回顧了遷移學習在解決動態多目標問題方面的研究，并對目前的動態社區檢測算法進行了綜述。

1.1 基于多目標的遷移學習

遷移學習作為一種強大的技術工具，旨在通過在源領域上學到的知識來改善目標領域上的學習性能。在求解基于遷移學習的動態多目標問題（DMOPs）方面，研究領域近年來呈現出蓬勃的發展態勢。例如文獻［20］介紹了進化轉移優化（ETO）方法，這是一種將EA求解器與跨相關領域的知識學習和轉移相結合的范例。Jiang等人［21］提出了一種動態多目標進化算法（EA）框架，集成遷移學習和基于種群的EA，重用過去的經驗生成有效的初始種群池，以加速進化過程。但由于遷移過程中存在低質量的個體，傳統的遷移學習難以得到實質性的改進。為了克服負遷移的影響，文獻［22］提出了一種非平衡遷移學習方法KT-DMOEA，通過調整解的權值并利用膝點來權衡不同目標的最佳解。Liu等人［23］提出了一種遷移學習算法，該算法保留了對足夠歷史信息的預測方法，修改種群預測策略提供的解，以構建新環境下的初始種群并進行優化。Li等人［24］提出了兩種新穎的操作來幫助解決DMOPs，當環境發生變化時，使用基于聚類的選擇（CBS）和基于聚類的遷移（CBT）來指導知識轉移。Jiang等人［25］提出了一種基于個體遷移的動態多目標進化算法，該算法從歷史最優解中篩選出一些優秀個體，以避免負遷移。還有一些方法旨在克服線性相關實例的低準確率和訓練樣本不足的障礙，例如Xu等人［19］提出了一種基于增量支持向量機的動態多目標進化算法，將動態多目標優化問題視為一個在線學習過程，用歷史最優解更新并支持向量機，而不會丟棄早期的解信息?？紤]到動態多目標優化問題在決策空間和目標空間中可能發生的變化，Zhou等人［26］提出了一種多視圖預測的進化搜索算法，該算法在再現Hilbert空間中使用核化的自編碼模型來獲得多視圖預測。文獻［27］則提出了一種通過擴展編碼進化搜索的方式來提高種群優秀個體的預測質量。文獻［28］實現了一種快速動態多目標進化算法，該算法使用記憶機制來保留過去的最佳個體，并使用流形轉移學習技術來預測演化中的最優個體。傳統遷移學習方法的有效性通常依賴于源領域和目標領域之間的相似性，而在動態社區檢測中，社區結構可能隨時間發生顯著變化，導致源領域和目標領域之間的差異增加，使得遷移學習方法性能下降。

1.2 動態社區檢測方法

研究社區的核心問題是確定社區，而網絡成員的頻繁變化是動態網絡中社區結構的重要特征，近年來已經提出了多種算法用于動態社區檢測。李輝等人［29］描述了已經提出的幾種動態網絡社區檢測方法。在動態網絡中檢測社區的方法普遍為將網絡視為基于時間戳的快照，并且直接在每個快照的網絡上使用靜態算法［30］。然而，重復使用靜態算法在計算上的成本非常高，特別是當快照的數量非常多時。另一種方式則是利用網絡聚類多樣性的特征來檢測社區。受進化聚類框架的啟發，Folino等人提出了動態多目標遺傳算法（DYNMOGA）［10］來檢測動態網絡中的群落結構章。第一個目標是使當前時間步的模塊度最大化，第二個目標是使當前時間步的社團結構與前一個時間步的社團結構之間的差異最小化。本文也是選取這兩個目標進行優化。之后，Zeng等人［31］引入了共識社區的概念，以使DYNMOGA更好地達到這兩個目標。通過這種方式，他們引導動態社區檢測朝著關注前一個時間步的社區結構方向發展。Niu等人［32］采用標簽傳播方法初始化社區，限制遺傳算法突變過程的條件，進一步提高了檢測效率和有效性。Liu等人［16］發現經典算子無法避免節點經常與其大多數鄰居互連等缺陷，設計了一種與經典遺傳算子相結合的遷移算子來尋找群落間的聯系。為克服社區檢測糾錯和基于模塊化的社區檢測存在NP難等問題，Yin等人［13］提出了一種多目標粒子群優化方法來處理動態社區檢測問題。Qu等人［33］提出了一種基于進化的動態社區檢測方法，解決節點嵌入過程中的數據稀疏性問題，充分考慮了歷史結構信息，提高了動態社區檢測的準確性和穩定性。

盡管在發現動態社區方面已經作出了巨大的努力，但仍然存在著一些問題尚未解決。具體而言，大多數算法都假定相鄰時間步的社區結構不會突然發生劇烈變化，例如在非增量社區檢測算法中忽略了這種網絡突變，從而沒有將時間平滑性融入到社區檢測問題中；而在增量社區檢測算法中，應對社區急劇變化的方法則是在網絡變化超過一定閾值的時間步上重新運行一次靜態社區檢測算法，但丟失了先前時間步社區中有價值的信息。為探究網絡突變對社區檢測算法性能的影響，并使算法適應更復雜的網絡環境，本文提出基于間接遷移學習和進化算法的動態社區檢測算法HOGA。

2 動態社區檢測算法HOGA

本文算法將高階信息轉移策略應用于動態社區問題的多目標模型中，方法框架如圖1所示。

通常，靜態網絡被建模為圖G=（V，E），其中V為節點集合，E為邊的集合。動態網絡則是序列G={G1，G2，…，GT}，其中Gt是節點和節點之間的連接在t時刻的快照（snaphot）或時間步（timestep），t={1，2，…，T}是一個有限的時間序列集合，T表示該動態網絡所含的網絡快照數量。Gt和Gt-1的區別在于刪除了一些節點和邊，或者新增了一些節點和邊。動態網絡變化如圖2所示。其中包括兩種情況：a）社區發生輕微變化；b）社區發生顯著變化。目前大多數方法都考慮到網絡的輕微變化，如圖2快照t-1至t，僅有節點3和節點7脫離了原本所在社區。而本文方法主要應對網絡發生顯著變化的場景，如圖2快照t至t+1所示。其中社區C1中的節點5脫離該社區，并且與節點3、節點10組成了新的社區C3；此外，社區C2中的成員7又重新加入了該社區；這種相鄰時間步社區出現的較大變動可能引發負遷移，從而導致算法的性能下降和聚類平滑性降低。

2.1 新的目標函數

在優化動態社區檢測過程中，需要同時考慮聚類質量和聚類平滑性，因此本文采用的兩個目標函數分別為模塊度Q［34］和衡量社區變化度的CV，并進行雙指標優化。模塊度被廣泛認為是評價社區結構質量的標準，模塊化程度高時社區內連接緊密，不同社區節點間連接密度稀疏。其定義如下：

Q=∑ks=1［lsm－（ds2m）2］（1）

其中：ls為社區Cs內的邊數；ds為Cs中節點的度數之和；m為網絡Gt中的總邊數。社區內節點度數占比越高，模塊度值越接近1，表示社區內連接越緊密，社區間區分度越高，聚類質量也越高；而模塊度值越接近0，聚類質量越低。

在文獻［10］中使用NMI來檢測社區，可以通過前一個快照的社區標簽計算得到。當給定兩組社區A={A1，A2，…，Ai}和社區B={B1，B2，…，Bj}，C為兩個社區的混淆矩陣，并且C中i行j列的元素Cji表示同時存在于社區Ai（AiA）和社區Bj（BjB）的節點數。其中NMI的定義如下：

NMI（A，B）=－2∑CAi=1 ∑CBj=1Cjilog（CjiN/Ci.C.j）∑CAi=1Ci.log（Ci./N）+∑CBj=1C.jlog（C.j/N）（2）

其中：CA（CB）是A（B）中的社區數量；Ci.表示混淆矩陣C的第i行元素之和；C.j表示混淆矩陣C的第j列元素之和。NMI在社區集合A和B完全相同時取到最大值1，當這兩個社區集合完全不同時，取到最小值0。因此，NMI（CRt，CRt－1）越高，相鄰兩個時間步的社區結構越為相似，社區結構隨時間的平滑性也越高。為充分利用高階社區信息，本文設計了新的目標函數CV，其定義如下：

CV=1－∑Ck∈CcomSameNum（Ctk，Ct－1k）×1N（3）

其中：SameNum（Ctk，Ct－1k）為社區Ck在兩個相鄰快照t和t－1上的公共節點數；Ccom為這兩個快照中具有公共節點的社區集合；N是公共社區總數。CV的取值為0～1，SameNum（Ctk，Ct－1k）越小則相鄰社區相似性越小，CV的值將越接近1，因此社區變化越大；其值越接近0，則表示相鄰快照的社區較為接近，社區變化也較小，因此CV可以用于衡量動態社區的變化程度。本文則主要通過降低相鄰時間步之間社區變化即CV來提高社區平滑性。

2.2 高階信息轉移策略CV-HOCV

本文算法結合間接遷移學習的思想，使用改進后的高階知識轉移策略［35］適應網絡社區的顯著變化。當r≥λ時，將使用一階社區信息，即利用前一個時間步的社區劃分結果輔助當前時間步的社區檢測，其中r為重疊率，λ為網絡變化閾值；而當r<λ時，相鄰時間步社區可能發生結構突變，如果使用一階知識將發生負遷移，因此使用高階社區信息，計算當前快照Gt與之前所有快照之間的CV，再根據權重ω將它們相加作為HOCV，由此可以充分利用社區劃分的先驗知識并連接相鄰社區。權重ω由相似性矩陣決定，將在3.3節中對其進行詳細闡述。一階知識與高階知識的定義如下：

a）一階信息：僅考慮當前時間步t與前一個時間步t－1的社區結構差異。此時目標函數HOCV值為

HOCV=CV（CRt，CRt－1）（4）

b）高階信息：考慮當前時間步t與多個先前時間步的社區結構差異。此時HOCV值為

HOCV=∑ω（i）×CV（CRi，CRt） i=1，2，…，t－1（5）

其中：ω（i）為時間步i（i=1，2，…，t－1）的權重，且∑ω（i）=1。

本文使用連續兩個時間步的鄰接矩陣來計算時間步t與其前一個時間步t-1的鄰接矩陣重疊比率。計算公式如下：ratio=SameNum/n。其中SameNum是兩個連續時間步的公共邊數，n則是時間步t的總邊數，重疊率計算的示例如圖3所示?？煺誸總共有10條邊，兩個時間步的公共邊為{（1，2），（1，4），（2，1），（2，3），（3，2），（4，1）}。因此SameNum=6，n=10，故此示例的重疊率r=0.6。

2.3 染色體編碼

社區的基因編碼方式有基于社區標簽的表示和基于位點的表示兩種類型。在基于社區標簽的表示中，種群由N個個體X={X1，X2，…，XT}組成，每個個體包含n個基因{g1，g2，…，gn}，其中T為動態網絡的時間步數，n為節點數。若k為群落數，則gi的取值是{1，2，…，k}，為標識節點i的所屬社區標簽。而在基于位點的表示中，每個基因的表示即gi的取值是{1，2，…，n}，其被定義為節點i所屬社區內的相鄰節點標簽，此時一個基因表示為社區內一對節點的連接。如圖4所示，節點1、2、3、4、6屬于一個社區，節點5、7、8屬于另一個社區。因此，在基于社區標簽的表示中，基因1、2、3、4、6的標簽為1，基因5、7、8的標簽為2。在基于位點的表示中，基因1的標簽為2、3、4、6或8，表示在同一個社區中隨機選擇一個鄰節點作為基因1的最終標簽。由于節點2和節點5不在同一個社區，所以基因2和基因5不會互相作為標簽。基于位點的一個明顯優勢是，簇的數量可以由個體中所包含的聯通分量數量自動確定，并通過解碼［35］步驟獲得對應的社區結構，而無須以完整社區結構參與迭代過程，從而減少計算量。因此，本文算法采用基于位點的鄰接表示作為基因編碼方式。

2.4 交叉與變異

遺傳算法（genetic algorithm）作為一種模擬自然選擇和遺傳機制的優化算法，被廣泛應用于解決復雜問題和優化搜索空間。其靈感來源于生物學中的進化過程，通過模擬基因的遺傳、交叉和突變等操作，逐步演化出更優秀的個體，從而實現對問題的全局搜索和優化。本文使用非支配排序算法NSGA-Ⅱ對種群個體進行迭代，具體過程包括種群初始化、生成子代種群（基因交叉、基因變異）、基因選擇。

初始化是遺傳算法中引入個體多樣性的關鍵步驟，為遺傳算法的進化提供起始點。首先需要初始化個體容量為popsize的父代種群。普遍的做法是通過從圖中隨機選擇一個鄰居來對個體的基因進行初始化，每一對基因（i，gi）表示社區內的一組連接。

基因交叉通過組合不同個體的優勢基因，產生具有更好適應性的子代基因，推動種群向全局最優進化。此過程需選擇兩個個體作為雙親，并通過隨機自然數θ的奇偶性決定基因的交叉方式。當θ為奇數時，選擇親本1的奇數位基因和親本2的偶數位基因構建子代基因；當θ為偶數時，則選擇親本1的偶數位基因和親本2的奇數位基因對子代基因進行構建。交叉過程的一個示例如圖5所示。

基因突變對于隨機性的引入以及保持種群多樣性具有重要意義。該步驟選擇節點i對應的等位基因gi進行隨機突變。圖6給出了一個基因突變的示例。基于位點表示的基因初始構成為{2，3，4，2，7，1，8，5}。節點1的同社區鄰節點為{2，3，4，6}，隨機選擇相同社區內節點1的鄰節點3，作為等位基因1突變后的標簽。執行完整突變過程后，該基因的構成變為{3，4，2，6，8，4，5，7}。需要注意的是，突變范圍限定為同一社區的鄰居節點，確保變異后的基因仍保持其合理性。

選擇過程目的在于從當前種群中挑選優秀個體，構建下一代精英種群。首先需要為每個個體分配一個非支配等級，并按照該等級對種群中的個體進行排序，再將親代和子代中等級靠前的個體進行擇優選取，構成一個新的種群。在此種群中，個體再通過交叉和突變產生新的子代種群。

2.5 總體流程

HOGA算法首先通過蛛網模型生成每個快照的初始種群，再對初始種群進行進化迭代，獲得更高質量的子代種群，最終獲得多目標最優的社區結構，其流程如圖7所示。

給定一個動態網絡G={G1，G2，…，GT}，在種群初始化步驟，普遍的做法是僅通過對當前時間步網絡Gt（1≤t≤T）中每個節點進行隨機初始化，隨機選取節點的鄰居節點標簽作為其基因標簽，得到其初始種群。本文則采用蛛網模型［36］進行社區檢測以獲取源個體，再根據此源個體創建一個個體容量為n=|Vt|的隨機初始總體，Vt為當前時間步的節點數量。這是為了避免過于隨機，導致初始種群中存在多數低質量個體而陷入局部最優，提高初始種群質量和迭代效率。初始種群再經過交叉和變異過程生成新種群，接著計算出種群中個體與前一個網絡快照的重疊率r，當r≥λ時，使用一階信息進行當前快照的社區劃分，當r<λ時則應充分利用高階社區信息。對于每一代種群個體，進行個體解碼以生成快照t的社區，計算出第一個目標值Q，以及利用選取的一階或高階信息計算出第二個目標值HOCV，通過這兩個目標值作為適應度，并與父代個體一同根據帕累托支配度對種群中個體進行無支配排序，通過精英策略［35］選擇出優異個體（等級靠前）進行下一次的種群迭代，直到達到最大迭代次數。每次迭代結束，HOGA返回一組解，每個解都反映了對兩個目標值的不同權衡。需要注意的是，t=1時的網絡快照不能使用先前的任何社區信息，而t=2時只有一階信息能夠利用，當t≥3時才能使用高階社區信息。本文最終選取第二目標值HOCV最高的社區作為最終結果，以最小化社區結構波動。算法1描述了HOGA的詳細過程。

算法1 動態社區檢測算法HOGA

輸入：圖序列G={G1，G2，…，GT};時間步數T;時間步t的權重ωt（1≤t≤T）;網絡變化閾值λ。

輸出：社區檢測結果C={C1，C2，…，CT}。

a） 通過僅優化模塊度即式（1）后獲得首個時間步的社區。

b） 遍歷剩余時間步的網絡結構，利用蛛網模型得到當前時間步的源個體s。

c） 源個體s交叉與變異后生成隨機初始種群n=|Vt|。

d） 計算該時間步與上一個時間步的重疊率r。

e） 通過重疊率r與網絡閾值λ確定一階或高階社區信息用于計算第二目標函數值。

f） 對初始種群進行交叉、變異獲得子代種群。

g） 子代種群進行解碼后獲得社區結構，分別計算兩個目標函數值，并進行非支配排序。

h） 通過精英策略選擇出優秀個體并置于前沿集front中。

i） 達到終止條件則返回front，否則轉步驟f）。

其偽代碼如下：

Initialize the clustering CR1={C11，C12，…，C1k} of the network N1 by optimizing Eq（2）.

for t=2 to T

compute overlap ratio r;

if（r≥λ） then

HOCV=CV（CRt，CRt-1）;

else

HOCV=∑ω（i）*CV（CRi，CRt），i=1，2，…，t-1;

end if

create a random population of individuals with the number n=|Vt|;

while（Termination criteria not met） do

Get a new offspring population through crossover and mutation operations

Decode each individual to generate the partitioning CRt={Ct1，Ct2，…，Ctk}

Combine the parents and offspring into a new pool

Assign a rank for each individual by non-domination rank

Put the individual with lower level into front

end while

return front

end for

2.6 時間復雜度

首先重疊率計算的時間復雜度可表示為O（n2T），其中T代表時間步數。由文獻［17］可知，NSGA-Ⅱ算法的時間復雜度為O（gp logph－1），其中g為種群代數，p為種群個體總數，h為目標函數個數。由于HOGA優化了兩個目標，其非支配排序的時間復雜度為O（gp log p）。HOGA計算復雜度主要由三個部分組成：個體的解碼、模塊度的計算和NMI計算。解碼步驟時間復雜度為O（n log n）；模塊度計算需要考慮每個節點的鄰居，因此其復雜度為O（m），其中m為邊的數量。對于歸一化互信息的計算，由文獻［10］可知其時間復雜度為O（n），n表示節點的數量。因此HOGA總體復雜度為O（gp log p）×O（n log n+m）。

3 實驗及結果分析

為驗證本文算法的有效性，選取四種同為演化聚類的動態社區檢測算法與本文算法進行對比實驗，包括FaceNet［37］、DYNMOGA［10］、L-DMGA［32］和HoKT［35］算法。其中FaceNet是一種概率生成模型，通過當前網絡拓撲結構和歷史社團結構給出的先驗分布來估計當前的社團結構；而DYNMOGA、L-DMGA、HoKT與本文算法相同，均采用遺傳算法來優化其目標函數。實驗的硬件環境為：英特爾Core i7-7700HQ @ 2.80 GHz 四核，8 GB內存，Windows 10操作系統，算法采用Python語言實現。

3.1 數據集

本文使用表1中的六個數據集對所提算法進行驗證，其中highschool_2011、highschool_2012、primary_school以及workplace_contacts為四個真實網絡數據集，來源于https：//networkrepository.com/asn.php；并且另外新增了兩個模擬數據集作為網絡變化程度不同時的參考，其中synx_muw=0.1與synx_muw=0.5為LFR算法生成的人工數據集，分別表示相鄰時間步之間有0.1和0.5的概率產生新邊，來源于https：//snap.stanford.edu/data。

3.2 評估指標

除2.1節提到的模塊度Q和NMI（CRt，CRt－1）作為聚類質量和聚類平滑性的衡量指標外，本文還采用NMI（CRt，CRtreal）和F1-score兩個指標來評價社區檢測的性能。其中NMI（CRt，CRtreal）是社區檢測結果與真實社區的吻合度，CRtreal為時間步t的真實社區標簽，計算方式與式（2）相同。F1-score是分類問題的度量，是準確率和召回率的調和平均值。F1-score的定義如下：

F1-score=2×TP（TP+FN）（TP+FP）（6）

其中：TP為預測正確的標簽數；FN為實際情況下預測為負但為正的標簽數；FP為實際情況下預測為正但為負的標簽數。

3.3 參數設置

在對HOGA算法的實驗中，由于種群大小（pop_size）設置為100～200時算法已經能夠收斂到較優解的范圍，足以在解空間中進行有效的搜索，而超過200時算法收斂時間比100成倍增長。為了能夠在不大幅犧牲搜索空間的同時縮短收斂時間，最終將pop_size設置為100。同時由于考慮的社區信息最高階數超過3時，最優解集誤差均可控制在10%左右，說明3階信息已經能夠較好地聯系相鄰時間步的社區。為減少計算量最終確定使用的社區信息最高階數為3，并且各階信息的權重ω將根據不同數據集的最佳實驗結果進行調整。除此之外，實驗發現基因變異概率（MP）超過0.5時，算法收斂速度將比MP<0.5時慢兩倍左右，且迭代優化程度不高。因此為了平衡種群多樣性與收斂速度，最終將MP設置為0.4，在提高算法探索搜索空間能力的同時保持較合適的收斂速度。所述參數值均為基準值，數據集不同時，參數也將根據最優實驗結果依據基準值進行相應調整。

在synx_muw=0.1數據集中，不同種群代數（Gen_num）設置的實驗結果如表2所示。其中Q和NMI（CRt，CRt+1）分別表示平均模塊度和相鄰時間步社區的平均歸一化互信息，time為收斂耗時。能夠看出在種群代數為50時，相較于其他設置能夠使Q和NMI（CRt，CRt+1）值保持在較高水準的同時，收斂時間也相對較短。

為了更好地比較HOGA在網絡社區結構波動較小以及網絡波動較大的算法性能，選取配置方案在synx_muw=0.1的模擬數據集上的實驗結果，如表3所示，在synx_muw=0.5的模擬數據集上的實驗結果，如表4所示。結果表明，HOGA在網絡波動較小時能保持良好的性能，而隨著社區變化程度增大，相較于另外兩種算法，其優勢體現也越明顯。

網絡變化閾值λ通過NMI與數據集的重疊率矩陣確定。在真實數據集上設置不同的λ={0.2，0.3，0.4，0.5，0.6，0.7，0.8}，并運行HOGA算法，結果如圖8所示。圖9則給出了數據集workplace_contacts的重疊率矩陣。

圖8中λ=0.3時的NMI即紅色曲線（見電子版），幾乎在每個時間步上都優于其他曲線，并且由于圖8的重疊率矩陣中網絡相似度在［0.2，0.4］左右，所以本實驗的網絡變化閾值選擇λ=0.3。由此在λ=0.2、0.3、0.4時才可以選用不同階的社區信息，對不同相似度的網絡采取不同的社區劃分策略。此外，由于考慮過早的時間步社區信息對于當前網絡快照的社區劃分意義不大，所以本文主要對二階和三階社區進行利用。

3.4 實驗結果

圖10為本文算法與所選取的四種社區檢測算法在數據集highschool_2011和workplace_contacts中的模塊度Q、每個時間步與前一個時間步的社區結構歸一化互信息NMI（t，t-1）以及社區結構穩定性CS（community stability）的實驗結果。2.1節中，使用CV（community volatility）衡量社區變化，為了方便對圖表的觀察，采用與其互補的變量CS=1－CV對社區結構的穩定性進行表示。對比圖顯示出HOGA能夠將聚類質量保持在一個較好水平的同時，找到具有最佳聚類平滑性的社區劃分方案。雖然HOGA的模塊度Q不是四個算法中最優的，但是能夠在損失相對較少模塊度后，獲取到最高的NMI。這四個數據集相鄰快照的網絡社區大多都發生了顯著變化，即本文算法能夠在網絡發生顯著變化時最大化社區穩定性與平滑性，并且能夠平衡聚類質量和聚類平滑性這兩個社區檢測目標。HOGA在維持社區穩定性方面具有更好的性能，這是因為利用的社區劃分信息越多，算法也能保留更多先前社區劃分的優勢。

由于本文算法所使用的優化函數是以減少相鄰時間步的社區變化為目標，所以劃分出的社區整體變化更小，在對相鄰時間步進行分析時避免因為社區變化過于雜亂而影響對于網絡結構演變的研究。圖11所示為HoKT算法與本文算法在數據集highschool_2012上的部分社區劃分結果，在社區劃分完成后均使用Fruchterman-Reingold算法對網絡結構進行布局。從（a）中可以看出，HoKT算法檢測出的社區中單個節點社區遷移較多，社區間的成員流動較為復雜。而從（b）中能夠觀察到7個紅色邊框（見電子版）標注的節點經歷了社區變動，同時值得注意的是，節點53所在社區有一半的成員移動到了節點81所在的社區。因此本文算法更加利于分析動態網絡中社區整體的演變過程與社區之間的關系。

通過HOGA進行社區劃分后，真實數據集highschool_2011中由高中學生以及老師關系網絡構成的真實社區（選取主要社區）演變過程如圖12所示。能夠明顯觀察到三個社區間存在明顯的成員流動，因此能夠分析出這三個班級可能在這段時間內進行了班級人員調整，例如根據成績分班或者文理分科后調整班級。同時節點124與126離開了原社區，說明這兩個節點所代表的任課老師可能被調整到了其他任課崗位或是辦理了離職，該社區也發生了收縮。

由于算法降低了CV，社區演化事件也會隨之減少。圖13為五個不同社區檢測算法在四個真實數據集上的社區演化事件數。這些事件包括社區的擴張、收縮、合并以及分裂等。由圖可知，在社區演化過程中，HOGA算法檢測出的社區具有更高的穩定性和一致性。具體而言，HOGA算法在每個時間步上劃分出的社區相對于前一個時間步都具有更少的社區變化事件。這意味著在社區的演化過程中，HOGA算法所形成的社區結構更加穩定，變化也更為平滑。

為對算法效率進行公平比較，選取三個基于遺傳算法的動態社區檢測算法與本文算法進行對比。由于算法未使用隨機初始化，而是通過蛛網模型生成質量更高的父代種群，與本文的變異方法共同提高了子代種群多樣性，所以能夠在不影響算法性能的同時減少種群代數，進而提高算法效率。表5為各算法在不同數據集上的運行時間?？梢钥闯鲈谛∫幠祿希疚乃惴℉OGA略快于其他算法，并且隨著數據集規模增大，HOGA所用時間短的優勢也能更為明顯。

4 結束語

對于突變的處理在許多領域都是至關重要的，本文主要面向相鄰時間步發生顯著變化的動態網絡，基于進化算法以及高階信息轉移策略設計了一個動態社區檢測算法HOGA，并設計了新的目標函數HOCV，通過非支配排序遺傳算法求解出同時具備較高聚類質量和聚類平滑性的社區劃分方案。

實驗結果表明，HOGA在網絡發生微小變化時能保持良好的性能，而在相鄰網絡快照社區發生劇烈變化的情況下，對于社區穩定性和平滑性的改善更為明顯，檢JD2Qu3kRKTbGDcp6GlUHexwiXaEH0yXycDvta8GAvq8=測到的社區演變事件也更少。但該算法也存在一些缺陷，例如在參數設置方面無法做到自適應，這也為之后的研究提供了一種可能的方向。

在未來的工作中，其不僅用于解決當前的社區檢測問題，而且要面向更多發生顯著變化的場景。例如將高階信息傳遞的概念遷移到動態網絡布局中，構建多目標模型，對發生巨大變化的網絡進行布局，保留先前布局方案的優勢并應用到下一個任務中。因此還需不斷地探索更好的分析交互方式，同時提供一些動態可視化技術以及一定的交互，方便用戶理解和挖掘動態數據背后有價值的信息。

參考文獻：

［1］蔣云， 楊文東. 改進Louvain算法的多層航線網絡社區劃分 ［J］. 北京交通大學學報， 2022， 46（2）： 89-97. （Jiang Yun， Yang Wendong. Community detection of multi-layer air transport network with improved Louvain algorithm ［J］. Journal of Beijing Jiaotong University， 2022， 46（2）： 89-97.）

［2］歐陽資生， 楊希特， 黃穎. 嵌入網絡輿情指數的中國金融機構系統性風險傳染效應研究 ［J］. 中國管理科學， 2022， 30（4）： 1-12. （Ouyang Zisheng， Yang Xite， Huang Ying. Research on the systemic risk contagion effect of Chinese financial institutions embedded with social media sentiment index ［J］. Chinese Journal of Mana-gement Science， 2022， 30（4）： 1-12.）

［3］沈力峰， 王建波， 杜占瑋，等. 基于社團結構和活躍性驅動的雙層網絡傳播動力學 ［J］. 物理學報， 2023， 72（6）： 356-364. （Shen Lifeng， Wang Jianbo， Du Zhanwei，et al. Dynamic propagation in dual-layer networks driven by community structure and activity ［J］. Acta Physica Sinica， 2023， 72（6）： 356-364.）

［4］嚴玉為， 蔣沅， 楊松青，等. 基于時間序列的網絡失效模型 ［J］. 物理學報， 2022， 71（8）： 331-339. （Yan Yuwei， Jiang Yuan， Yang Songqing，et al. Time series-based model for network failures ［J］. Acta Physica Sinica， 2022， 71（8）： 331-339.）

［5］Redekar S S， Varma S L. A survey on community detection methods and its application in biological network ［C］// Proc of International Conference on Applied Artificial Intelligence and Computing. Piscata-way， NJ： IEEE Press， 2022： 1030-1037.

［6］梁文， 閆飛， 陳柏圳. 兩階段量子行走算法在社區檢測中的應用 ［J］. 計算機應用研究， 2023， 40（8）： 2329-2333. （Liang Wen， Yan Fei， Chen Bozhen. Two-stage quantum walk algorithm with application to community detection ［J］. Application Research of Computers， 2023， 40（8）： 2329-2333.）

［7］Peng Yong， Huang Wenna， Kong Wanzeng，et al. JGSED： an end-to-end spectral clustering model for joint graph construction， spectral embedding and discretization ［J］. IEEE Trans on Emerging To-pics in Computational Intelligence， 2023， 7（6）： 1687-1701.

［8］Su Xing， Xue Shan， Liu Fanzhen，et al. A comprehensive survey on community detection with deep learning ［J］. IEEE Trans on Neural Networks and Learning Systems， 2024， 35（4）： 4682-4702.

［9］Wang Xilu， Jin Yaochu， Schmitt S，et al. Transfer learning for Gaus-sian process assisted evolutionary bi-objective optimization for objectives with different evaluation times ［C］// Proc of Genetic and Evolutionary Computation Conference. New York：ACM Press， 2020： 587-594.

［10］Li Tianyi， Chen Lu， Jensen C S，et al. Evolutionary clustering of moving objects ［C］// Proc of the 38th IEEE International Conference on Data Engineering. Piscataway， NJ： IEEE Press， 2022： 2399-2411.

［11］Nordahl C， Boeva V， Grahn H，et al. EvolveCluster： an evolutionary clustering algorithm for streaming data ［J］. Evolving Systems， 2022， 13（4）： 603-623.

［12］Li Weimin， Zhou Xiaokang， Yang Chao，et al. Multi-objective optimization algorithm based on characteristics fusion of dynamic social networks for community discovery ［J］. Information Fusion， 2022， 79： 110-123.

［13］Yin Ying， Zhao Yuhai， Li He，et al. Multi-objective evolutionary clustering for large-scale dynamic community detection ［J］. Information Sciences， 2021， 549： 269-287.

［14］Keriven N. Not too little， not too much： a theoretical analysis of graph （over） smoothing ［J］. Advances in Neural Information Processing Systems， 2022， 35： 2268-2281.

［15］Yuan Limengzi， Zhu Qifeng， Zheng Yuchen，et al. Temporal smoothness framework： analyzing and exploring evolutionary transition behavior in dynamic networks ［C］// Proc of the 33rd IEEE International Conference on Tools with Artificial Intelligence. Piscataway， NJ： IEEE Press， 2021： 1206-1210.

［16］Liu Fanzhen， Wu Jia， Xue Shan，et al. Detecting the evolving community structure in dynamic social networks ［J］. World Wide Web， 2020， 23： 715-733.

［17］Deb K， Pratap A， Agarwal S，et al. A fast and elitist multiobjective genetic algorithm： NSGA-Ⅱ ［J］. IEEE Trans on Evolutionary Computation， 2002， 6（2）： 182-197.

［18］Srinivas N， Deb K. Muiltiobjective optimization using nondominated sorting in genetic algorithms ［J］. Evolutionary Computation， 1994， 2（3）： 221-248.

［19］Xu Dejun， Jiang Min， Hu Weizhen，et al. An online prediction approach based on incremental support vector machine for dynamic multiobjective optimization ［J］. IEEE Trans on Evolutionary Computation， 2021， 26（4）： 690-703.

［20］Tan K C， Feng Liang， Jiang Min. Evolutionary transfer optimization： a new frontier in evolutionary computation research ［J］. IEEE Computational Intelligence Magazine， 2021， 16（1）： 22-33.

［21］Jiang Min， Huang Zhongqiang， Qiu Liming，et al. Transfer learning-based dynamic multiobjective optimization algorithms ［J］. IEEE Trans on Evolutionary Computation， 2017， 22（4）： 501-514.

［22］Jiang Min， Wang Zhenzhong， Hong Haokai，et al. Knee point-based imbalanced transfer learning for dynamic multiobjective optimization ［J］. IEEE Trans on Evolutionary Computation， 2020， 25（1）： 117-129.

［23］Liu Zhening， Wang Handing. Improved population prediction strategy for dynamic multi-objective optimization algorithms using transfer learning ［C］// Proc of IEEE Congress on Evolutionary Computation. Piscataway， NJ： IEEE Press，2021： 103-110.

［24］Li Jianqiang， Sun Tao， Lin Qiuzhen，et al. Reducing negative transfer learning via clustering for dynamic multiobjective optimization ［J］. IEEE Trans on Evolutionary Computation， 2022， 26（5）： 1102-1116.

［25］Jiang Min， Wang Zhenzhong， Guo Shihui，et al. Individual-based transfer learning for dynamic multiobjective optimization ［J］. IEEE Trans on Cybernetics， 2020， 51（10）： 4968-4981.

［26］Zhou Wei， Feng Liang， Tan K C，et al. Evolutionary search with multiview prediction for dynamic multiobjective optimization ［J］. IEEE Trans on Evolutionary Computation， 2021， 26（5）： 911-925.

［27］Ma Xiaoke， Dong Di. Evolutionary nonnegative matrix factorization algorithms for community detection in dynamic networks ［J］. IEEE Trans on Knowledge and Data Engineering， 2017， 29（5）： 1045-1058.

［28］Jiang Min， Wang Zhenzhong， Qiu Liming，et al. A fast dynamic evolutionary multiobjective algorithm via manifold transfer learning ［J］. IEEE Trans on Cybernetics， 2020， 51（7）： 3417-3428.

［29］李輝， 陳福才， 張建朋，等. 復雜網絡中的社團發現算法綜述 ［J］. 計算機應用研究， 2021， 38（6）： 1611-1618. （Li Hui， Chen Fucai， Zhang Jianpeng，et al. Survey of community detection algorithms in complex networks ［J］. Application Research of Compu-ters， 2021， 38（6）： 1611-1618.）

［30］lhan N， üdücüG. Predicting community evolution based on time series modeling ［C］// Proc of IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. Piscataway， NJ： IEEE Press，2015： 1509-1516.

［31］Zeng Xiangxiang， Wang Wen， Chen Cong，et al. A consensus community-based particle swarm optimization for dynamic community detection ［J］. IEEE Trans on cybernetics， 2019， 50（6）： 2502-2513.

［32］Niu Xinzheng， Si Weiyu， Wu C Q. A label-based evolutionary computing approach to dynamic community detection ［J］. Computer Communications， 2017， 108： 110-122.

［33］Qu Song， Du Yuqing， Zhu Mu，et al. Dynamic community detection based on evolutionary DeepWalk ［J］. Applied Sciences， 2022， 12（22）： 11464.

［34］Costa A R. Towards modularity optimization using reinforcement learning to community detection in dynamic social networks ［EB/OL］. （2021-11-25）.https：//api.semanticscholar.org/CorpusID：244729709.

［35］Ma Huixin， Wu Kai， Wang Handing，et al. Higher-order knowledge transfer for dynamic community detection with great changes ［J］. IEEE Trans on Evolutionary Computation， 2024， 28（1）： 90-104.

［36］Yang Haijuan， Cheng Jianjun， Su Xing，et al. A spiderweb model for community detection in dynamic networks ［J］. Applied Intelligence， 2021， 51： 5157-5188.

［37］Lin Yuru， Chi Yun， Zhu Shenghuo，et al. Analyzing communities and their evolutions in dynamic social networks ［J］. ACM Trans on Knowledge Discovery from Data， 2009， 3（2）： 1-31.