應(yīng)對(duì)顯著變化的動(dòng)態(tài)社區(qū)檢測(cè)方法

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

關(guān)鍵詞：顯著變化；動(dòng)態(tài)網(wǎng)絡(luò)；高階信息；社區(qū)檢測(cè)

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 引言

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

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

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

1 相關(guān)工作

多數(shù)基于進(jìn)化的動(dòng)態(tài)社區(qū)檢測(cè)算法都將動(dòng)態(tài)社區(qū)檢測(cè)問題建模為多目標(biāo)優(yōu)化問題（MOP）。在動(dòng)態(tài)社區(qū)檢測(cè)領(lǐng)域，解決此類問題的普遍方法是將非支配個(gè)體進(jìn)行排序后進(jìn)行迭代擇優(yōu)，例如基于非支配排序的多目標(biāo)進(jìn)化算法（NSGA）［18］。這些基于進(jìn)化聚類的方法在計(jì)算機(jī)領(lǐng)域也引起了越來(lái)越多的興趣［19］。本文方法便是以多目標(biāo)優(yōu)化為基礎(chǔ)，同時(shí)結(jié)合了間接遷移學(xué)習(xí)的策略對(duì)動(dòng)態(tài)網(wǎng)絡(luò)進(jìn)行社區(qū)劃分。因此，本章回顧了遷移學(xué)習(xí)在解決動(dòng)態(tài)多目標(biāo)問題方面的研究，并對(duì)目前的動(dòng)態(tài)社區(qū)檢測(cè)算法進(jìn)行了綜述。

1.1 基于多目標(biāo)的遷移學(xué)習(xí)

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

1.2 動(dòng)態(tài)社區(qū)檢測(cè)方法

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

盡管在發(fā)現(xiàn)動(dòng)態(tài)社區(qū)方面已經(jīng)作出了巨大的努力，但仍然存在著一些問題尚未解決。具體而言，大多數(shù)算法都假定相鄰時(shí)間步的社區(qū)結(jié)構(gòu)不會(huì)突然發(fā)生劇烈變化，例如在非增量社區(qū)檢測(cè)算法中忽略了這種網(wǎng)絡(luò)突變，從而沒有將時(shí)間平滑性融入到社區(qū)檢測(cè)問題中；而在增量社區(qū)檢測(cè)算法中，應(yīng)對(duì)社區(qū)急劇變化的方法則是在網(wǎng)絡(luò)變化超過(guò)一定閾值的時(shí)間步上重新運(yùn)行一次靜態(tài)社區(qū)檢測(cè)算法，但丟失了先前時(shí)間步社區(qū)中有價(jià)值的信息。為探究網(wǎng)絡(luò)突變對(duì)社區(qū)檢測(cè)算法性能的影響，并使算法適應(yīng)更復(fù)雜的網(wǎng)絡(luò)環(huán)境，本文提出基于間接遷移學(xué)習(xí)和進(jìn)化算法的動(dòng)態(tài)社區(qū)檢測(cè)算法HOGA。

2 動(dòng)態(tài)社區(qū)檢測(cè)算法HOGA

本文算法將高階信息轉(zhuǎn)移策略應(yīng)用于動(dòng)態(tài)社區(qū)問題的多目標(biāo)模型中，方法框架如圖1所示。

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

2.1 新的目標(biāo)函數(shù)

在優(yōu)化動(dòng)態(tài)社區(qū)檢測(cè)過(guò)程中，需要同時(shí)考慮聚類質(zhì)量和聚類平滑性，因此本文采用的兩個(gè)目標(biāo)函數(shù)分別為模塊度Q［34］和衡量社區(qū)變化度的CV，并進(jìn)行雙指標(biāo)優(yōu)化。模塊度被廣泛認(rèn)為是評(píng)價(jià)社區(qū)結(jié)構(gòu)質(zhì)量的標(biāo)準(zhǔn)，模塊化程度高時(shí)社區(qū)內(nèi)連接緊密，不同社區(qū)節(jié)點(diǎn)間連接密度稀疏。其定義如下：

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

其中：ls為社區(qū)Cs內(nèi)的邊數(shù)；ds為Cs中節(jié)點(diǎn)的度數(shù)之和；m為網(wǎng)絡(luò)Gt中的總邊數(shù)。社區(qū)內(nèi)節(jié)點(diǎn)度數(shù)占比越高，模塊度值越接近1，表示社區(qū)內(nèi)連接越緊密，社區(qū)間區(qū)分度越高，聚類質(zhì)量也越高；而模塊度值越接近0，聚類質(zhì)量越低。

在文獻(xiàn)［10］中使用NMI來(lái)檢測(cè)社區(qū)，可以通過(guò)前一個(gè)快照的社區(qū)標(biāo)簽計(jì)算得到。當(dāng)給定兩組社區(qū)A={A1，A2，…，Ai}和社區(qū)B={B1，B2，…，Bj}，C為兩個(gè)社區(qū)的混淆矩陣，并且C中i行j列的元素Cji表示同時(shí)存在于社區(qū)Ai（AiA）和社區(qū)Bj（BjB）的節(jié)點(diǎn)數(shù)。其中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）中的社區(qū)數(shù)量；Ci.表示混淆矩陣C的第i行元素之和；C.j表示混淆矩陣C的第j列元素之和。NMI在社區(qū)集合A和B完全相同時(shí)取到最大值1，當(dāng)這兩個(gè)社區(qū)集合完全不同時(shí)，取到最小值0。因此，NMI（CRt，CRt－1）越高，相鄰兩個(gè)時(shí)間步的社區(qū)結(jié)構(gòu)越為相似，社區(qū)結(jié)構(gòu)隨時(shí)間的平滑性也越高。為充分利用高階社區(qū)信息，本文設(shè)計(jì)了新的目標(biāo)函數(shù)CV，其定義如下：

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

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

2.2 高階信息轉(zhuǎn)移策略CV-HOCV

本文算法結(jié)合間接遷移學(xué)習(xí)的思想，使用改進(jìn)后的高階知識(shí)轉(zhuǎn)移策略［35］適應(yīng)網(wǎng)絡(luò)社區(qū)的顯著變化。當(dāng)r≥λ時(shí)，將使用一階社區(qū)信息，即利用前一個(gè)時(shí)間步的社區(qū)劃分結(jié)果輔助當(dāng)前時(shí)間步的社區(qū)檢測(cè)，其中r為重疊率，λ為網(wǎng)絡(luò)變化閾值；而當(dāng)r<λ時(shí)，相鄰時(shí)間步社區(qū)可能發(fā)生結(jié)構(gòu)突變，如果使用一階知識(shí)將發(fā)生負(fù)遷移，因此使用高階社區(qū)信息，計(jì)算當(dāng)前快照Gt與之前所有快照之間的CV，再根據(jù)權(quán)重ω將它們相加作為HOCV，由此可以充分利用社區(qū)劃分的先驗(yàn)知識(shí)并連接相鄰社區(qū)。權(quán)重ω由相似性矩陣決定，將在3.3節(jié)中對(duì)其進(jìn)行詳細(xì)闡述。一階知識(shí)與高階知識(shí)的定義如下：

a）一階信息：僅考慮當(dāng)前時(shí)間步t與前一個(gè)時(shí)間步t－1的社區(qū)結(jié)構(gòu)差異。此時(shí)目標(biāo)函數(shù)HOCV值為

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

b）高階信息：考慮當(dāng)前時(shí)間步t與多個(gè)先前時(shí)間步的社區(qū)結(jié)構(gòu)差異。此時(shí)HOCV值為

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

其中：ω（i）為時(shí)間步i（i=1，2，…，t－1）的權(quán)重，且∑ω（i）=1。

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

2.3 染色體編碼

社區(qū)的基因編碼方式有基于社區(qū)標(biāo)簽的表示和基于位點(diǎn)的表示兩種類型。在基于社區(qū)標(biāo)簽的表示中，種群由N個(gè)個(gè)體X={X1，X2，…，XT}組成，每個(gè)個(gè)體包含n個(gè)基因{g1，g2，…，gn}，其中T為動(dòng)態(tài)網(wǎng)絡(luò)的時(shí)間步數(shù)，n為節(jié)點(diǎn)數(shù)。若k為群落數(shù)，則gi的取值是{1，2，…，k}，為標(biāo)識(shí)節(jié)點(diǎn)i的所屬社區(qū)標(biāo)簽。而在基于位點(diǎn)的表示中，每個(gè)基因的表示即gi的取值是{1，2，…，n}，其被定義為節(jié)點(diǎn)i所屬社區(qū)內(nèi)的相鄰節(jié)點(diǎn)標(biāo)簽，此時(shí)一個(gè)基因表示為社區(qū)內(nèi)一對(duì)節(jié)點(diǎn)的連接。如圖4所示，節(jié)點(diǎn)1、2、3、4、6屬于一個(gè)社區(qū)，節(jié)點(diǎn)5、7、8屬于另一個(gè)社區(qū)。因此，在基于社區(qū)標(biāo)簽的表示中，基因1、2、3、4、6的標(biāo)簽為1，基因5、7、8的標(biāo)簽為2。在基于位點(diǎn)的表示中，基因1的標(biāo)簽為2、3、4、6或8，表示在同一個(gè)社區(qū)中隨機(jī)選擇一個(gè)鄰節(jié)點(diǎn)作為基因1的最終標(biāo)簽。由于節(jié)點(diǎn)2和節(jié)點(diǎn)5不在同一個(gè)社區(qū)，所以基因2和基因5不會(huì)互相作為標(biāo)簽?；谖稽c(diǎn)的一個(gè)明顯優(yōu)勢(shì)是，簇的數(shù)量可以由個(gè)體中所包含的聯(lián)通分量數(shù)量自動(dòng)確定，并通過(guò)解碼［35］步驟獲得對(duì)應(yīng)的社區(qū)結(jié)構(gòu)，而無(wú)須以完整社區(qū)結(jié)構(gòu)參與迭代過(guò)程，從而減少計(jì)算量。因此，本文算法采用基于位點(diǎn)的鄰接表示作為基因編碼方式。

2.4 交叉與變異

遺傳算法（genetic algorithm）作為一種模擬自然選擇和遺傳機(jī)制的優(yōu)化算法，被廣泛應(yīng)用于解決復(fù)雜問題和優(yōu)化搜索空間。其靈感來(lái)源于生物學(xué)中的進(jìn)化過(guò)程，通過(guò)模擬基因的遺傳、交叉和突變等操作，逐步演化出更優(yōu)秀的個(gè)體，從而實(shí)現(xiàn)對(duì)問題的全局搜索和優(yōu)化。本文使用非支配排序算法NSGA-Ⅱ?qū)ΨN群個(gè)體進(jìn)行迭代，具體過(guò)程包括種群初始化、生成子代種群（基因交叉、基因變異）、基因選擇。

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

基因交叉通過(guò)組合不同個(gè)體的優(yōu)勢(shì)基因，產(chǎn)生具有更好適應(yīng)性的子代基因，推動(dòng)種群向全局最優(yōu)進(jìn)化。此過(guò)程需選擇兩個(gè)個(gè)體作為雙親，并通過(guò)隨機(jī)自然數(shù)θ的奇偶性決定基因的交叉方式。當(dāng)θ為奇數(shù)時(shí)，選擇親本1的奇數(shù)位基因和親本2的偶數(shù)位基因構(gòu)建子代基因；當(dāng)θ為偶數(shù)時(shí)，則選擇親本1的偶數(shù)位基因和親本2的奇數(shù)位基因?qū)ψ哟蜻M(jìn)行構(gòu)建。交叉過(guò)程的一個(gè)示例如圖5所示。

基因突變對(duì)于隨機(jī)性的引入以及保持種群多樣性具有重要意義。該步驟選擇節(jié)點(diǎn)i對(duì)應(yīng)的等位基因gi進(jìn)行隨機(jī)突變。圖6給出了一個(gè)基因突變的示例?；谖稽c(diǎn)表示的基因初始構(gòu)成為{2，3，4，2，7，1，8，5}。節(jié)點(diǎn)1的同社區(qū)鄰節(jié)點(diǎn)為{2，3，4，6}，隨機(jī)選擇相同社區(qū)內(nèi)節(jié)點(diǎn)1的鄰節(jié)點(diǎn)3，作為等位基因1突變后的標(biāo)簽。執(zhí)行完整突變過(guò)程后，該基因的構(gòu)成變?yōu)閧3，4，2，6，8，4，5，7}。需要注意的是，突變范圍限定為同一社區(qū)的鄰居節(jié)點(diǎn)，確保變異后的基因仍保持其合理性。

選擇過(guò)程目的在于從當(dāng)前種群中挑選優(yōu)秀個(gè)體，構(gòu)建下一代精英種群。首先需要為每個(gè)個(gè)體分配一個(gè)非支配等級(jí)，并按照該等級(jí)對(duì)種群中的個(gè)體進(jìn)行排序，再將親代和子代中等級(jí)靠前的個(gè)體進(jìn)行擇優(yōu)選取，構(gòu)成一個(gè)新的種群。在此種群中，個(gè)體再通過(guò)交叉和突變產(chǎn)生新的子代種群。

2.5 總體流程

HOGA算法首先通過(guò)蛛網(wǎng)模型生成每個(gè)快照的初始種群，再對(duì)初始種群進(jìn)行進(jìn)化迭代，獲得更高質(zhì)量的子代種群，最終獲得多目標(biāo)最優(yōu)的社區(qū)結(jié)構(gòu)，其流程如圖7所示。

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

算法1 動(dòng)態(tài)社區(qū)檢測(cè)算法HOGA

輸入：圖序列G={G1，G2，…，GT};時(shí)間步數(shù)T;時(shí)間步t的權(quán)重ωt（1≤t≤T）;網(wǎng)絡(luò)變化閾值λ。

輸出：社區(qū)檢測(cè)結(jié)果C={C1，C2，…，CT}。

a） 通過(guò)僅優(yōu)化模塊度即式（1）后獲得首個(gè)時(shí)間步的社區(qū)。

b） 遍歷剩余時(shí)間步的網(wǎng)絡(luò)結(jié)構(gòu)，利用蛛網(wǎng)模型得到當(dāng)前時(shí)間步的源個(gè)體s。

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

d） 計(jì)算該時(shí)間步與上一個(gè)時(shí)間步的重疊率r。

e） 通過(guò)重疊率r與網(wǎng)絡(luò)閾值λ確定一階或高階社區(qū)信息用于計(jì)算第二目標(biāo)函數(shù)值。

f） 對(duì)初始種群進(jìn)行交叉、變異獲得子代種群。

g） 子代種群進(jìn)行解碼后獲得社區(qū)結(jié)構(gòu)，分別計(jì)算兩個(gè)目標(biāo)函數(shù)值，并進(jìn)行非支配排序。

h） 通過(guò)精英策略選擇出優(yōu)秀個(gè)體并置于前沿集front中。

i） 達(dá)到終止條件則返回front，否則轉(zhuǎn)步驟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 時(shí)間復(fù)雜度

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

3 實(shí)驗(yàn)及結(jié)果分析

為驗(yàn)證本文算法的有效性，選取四種同為演化聚類的動(dòng)態(tài)社區(qū)檢測(cè)算法與本文算法進(jìn)行對(duì)比實(shí)驗(yàn)，包括FaceNet［37］、DYNMOGA［10］、L-DMGA［32］和HoKT［35］算法。其中FaceNet是一種概率生成模型，通過(guò)當(dāng)前網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和歷史社團(tuán)結(jié)構(gòu)給出的先驗(yàn)分布來(lái)估計(jì)當(dāng)前的社團(tuán)結(jié)構(gòu)；而DYNMOGA、L-DMGA、HoKT與本文算法相同，均采用遺傳算法來(lái)優(yōu)化其目標(biāo)函數(shù)。實(shí)驗(yàn)的硬件環(huán)境為：英特爾Core i7-7700HQ @ 2.80 GHz 四核，8 GB內(nèi)存，Windows 10操作系統(tǒng)，算法采用Python語(yǔ)言實(shí)現(xiàn)。

3.1 數(shù)據(jù)集

本文使用表1中的六個(gè)數(shù)據(jù)集對(duì)所提算法進(jìn)行驗(yàn)證，其中highschool_2011、highschool_2012、primary_school以及workplace_contacts為四個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集，來(lái)源于https：//networkrepository.com/asn.php；并且另外新增了兩個(gè)模擬數(shù)據(jù)集作為網(wǎng)絡(luò)變化程度不同時(shí)的參考，其中synx_muw=0.1與synx_muw=0.5為L(zhǎng)FR算法生成的人工數(shù)據(jù)集，分別表示相鄰時(shí)間步之間有0.1和0.5的概率產(chǎn)生新邊，來(lái)源于https：//snap.stanford.edu/data。

3.2 評(píng)估指標(biāo)

除2.1節(jié)提到的模塊度Q和NMI（CRt，CRt－1）作為聚類質(zhì)量和聚類平滑性的衡量指標(biāo)外，本文還采用NMI（CRt，CRtreal）和F1-score兩個(gè)指標(biāo)來(lái)評(píng)價(jià)社區(qū)檢測(cè)的性能。其中NMI（CRt，CRtreal）是社區(qū)檢測(cè)結(jié)果與真實(shí)社區(qū)的吻合度，CRtreal為時(shí)間步t的真實(shí)社區(qū)標(biāo)簽，計(jì)算方式與式（2）相同。F1-score是分類問題的度量，是準(zhǔn)確率和召回率的調(diào)和平均值。F1-score的定義如下：

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

其中：TP為預(yù)測(cè)正確的標(biāo)簽數(shù)；FN為實(shí)際情況下預(yù)測(cè)為負(fù)但為正的標(biāo)簽數(shù)；FP為實(shí)際情況下預(yù)測(cè)為正但為負(fù)的標(biāo)簽數(shù)。

3.3 參數(shù)設(shè)置

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

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

為了更好地比較HOGA在網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)波動(dòng)較小以及網(wǎng)絡(luò)波動(dòng)較大的算法性能，選取配置方案在synx_muw=0.1的模擬數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，如表3所示，在synx_muw=0.5的模擬數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，如表4所示。結(jié)果表明，HOGA在網(wǎng)絡(luò)波動(dòng)較小時(shí)能保持良好的性能，而隨著社區(qū)變化程度增大，相較于另外兩種算法，其優(yōu)勢(shì)體現(xiàn)也越明顯。

網(wǎng)絡(luò)變化閾值λ通過(guò)NMI與數(shù)據(jù)集的重疊率矩陣確定。在真實(shí)數(shù)據(jù)集上設(shè)置不同的λ={0.2，0.3，0.4，0.5，0.6，0.7，0.8}，并運(yùn)行HOGA算法，結(jié)果如圖8所示。圖9則給出了數(shù)據(jù)集workplace_contacts的重疊率矩陣。

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

3.4 實(shí)驗(yàn)結(jié)果

圖10為本文算法與所選取的四種社區(qū)檢測(cè)算法在數(shù)據(jù)集highschool_2011和workplace_contacts中的模塊度Q、每個(gè)時(shí)間步與前一個(gè)時(shí)間步的社區(qū)結(jié)構(gòu)歸一化互信息NMI（t，t-1）以及社區(qū)結(jié)構(gòu)穩(wěn)定性CS（community stability）的實(shí)驗(yàn)結(jié)果。2.1節(jié)中，使用CV（community volatility）衡量社區(qū)變化，為了方便對(duì)圖表的觀察，采用與其互補(bǔ)的變量CS=1－CV對(duì)社區(qū)結(jié)構(gòu)的穩(wěn)定性進(jìn)行表示。對(duì)比圖顯示出HOGA能夠?qū)⒕垲愘|(zhì)量保持在一個(gè)較好水平的同時(shí)，找到具有最佳聚類平滑性的社區(qū)劃分方案。雖然HOGA的模塊度Q不是四個(gè)算法中最優(yōu)的，但是能夠在損失相對(duì)較少模塊度后，獲取到最高的NMI。這四個(gè)數(shù)據(jù)集相鄰快照的網(wǎng)絡(luò)社區(qū)大多都發(fā)生了顯著變化，即本文算法能夠在網(wǎng)絡(luò)發(fā)生顯著變化時(shí)最大化社區(qū)穩(wěn)定性與平滑性，并且能夠平衡聚類質(zhì)量和聚類平滑性這兩個(gè)社區(qū)檢測(cè)目標(biāo)。HOGA在維持社區(qū)穩(wěn)定性方面具有更好的性能，這是因?yàn)槔玫纳鐓^(qū)劃分信息越多，算法也能保留更多先前社區(qū)劃分的優(yōu)勢(shì)。

由于本文算法所使用的優(yōu)化函數(shù)是以減少相鄰時(shí)間步的社區(qū)變化為目標(biāo)，所以劃分出的社區(qū)整體變化更小，在對(duì)相鄰時(shí)間步進(jìn)行分析時(shí)避免因?yàn)樯鐓^(qū)變化過(guò)于雜亂而影響對(duì)于網(wǎng)絡(luò)結(jié)構(gòu)演變的研究。圖11所示為HoKT算法與本文算法在數(shù)據(jù)集highschool_2012上的部分社區(qū)劃分結(jié)果，在社區(qū)劃分完成后均使用Fruchterman-Reingold算法對(duì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行布局。從（a）中可以看出，HoKT算法檢測(cè)出的社區(qū)中單個(gè)節(jié)點(diǎn)社區(qū)遷移較多，社區(qū)間的成員流動(dòng)較為復(fù)雜。而從（b）中能夠觀察到7個(gè)紅色邊框（見電子版）標(biāo)注的節(jié)點(diǎn)經(jīng)歷了社區(qū)變動(dòng)，同時(shí)值得注意的是，節(jié)點(diǎn)53所在社區(qū)有一半的成員移動(dòng)到了節(jié)點(diǎn)81所在的社區(qū)。因此本文算法更加利于分析動(dòng)態(tài)網(wǎng)絡(luò)中社區(qū)整體的演變過(guò)程與社區(qū)之間的關(guān)系。

通過(guò)HOGA進(jìn)行社區(qū)劃分后，真實(shí)數(shù)據(jù)集highschool_2011中由高中學(xué)生以及老師關(guān)系網(wǎng)絡(luò)構(gòu)成的真實(shí)社區(qū)（選取主要社區(qū)）演變過(guò)程如圖12所示。能夠明顯觀察到三個(gè)社區(qū)間存在明顯的成員流動(dòng)，因此能夠分析出這三個(gè)班級(jí)可能在這段時(shí)間內(nèi)進(jìn)行了班級(jí)人員調(diào)整，例如根據(jù)成績(jī)分班或者文理分科后調(diào)整班級(jí)。同時(shí)節(jié)點(diǎn)124與126離開了原社區(qū)，說(shuō)明這兩個(gè)節(jié)點(diǎn)所代表的任課老師可能被調(diào)整到了其他任課崗位或是辦理了離職，該社區(qū)也發(fā)生了收縮。

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

為對(duì)算法效率進(jìn)行公平比較，選取三個(gè)基于遺傳算法的動(dòng)態(tài)社區(qū)檢測(cè)算法與本文算法進(jìn)行對(duì)比。由于算法未使用隨機(jī)初始化，而是通過(guò)蛛網(wǎng)模型生成質(zhì)量更高的父代種群，與本文的變異方法共同提高了子代種群多樣性，所以能夠在不影響算法性能的同時(shí)減少種群代數(shù)，進(jìn)而提高算法效率。表5為各算法在不同數(shù)據(jù)集上的運(yùn)行時(shí)間?？梢钥闯鲈谛∫?guī)模數(shù)據(jù)集上，本文算法HOGA略快于其他算法，并且隨著數(shù)據(jù)集規(guī)模增大，HOGA所用時(shí)間短的優(yōu)勢(shì)也能更為明顯。

4 結(jié)束語(yǔ)

對(duì)于突變的處理在許多領(lǐng)域都是至關(guān)重要的，本文主要面向相鄰時(shí)間步發(fā)生顯著變化的動(dòng)態(tài)網(wǎng)絡(luò)，基于進(jìn)化算法以及高階信息轉(zhuǎn)移策略設(shè)計(jì)了一個(gè)動(dòng)態(tài)社區(qū)檢測(cè)算法HOGA，并設(shè)計(jì)了新的目標(biāo)函數(shù)HOCV，通過(guò)非支配排序遺傳算法求解出同時(shí)具備較高聚類質(zhì)量和聚類平滑性的社區(qū)劃分方案。

實(shí)驗(yàn)結(jié)果表明，HOGA在網(wǎng)絡(luò)發(fā)生微小變化時(shí)能保持良好的性能，而在相鄰網(wǎng)絡(luò)快照社區(qū)發(fā)生劇烈變化的情況下，對(duì)于社區(qū)穩(wěn)定性和平滑性的改善更為明顯，檢JD2Qu3kRKTbGDcp6GlUHexwiXaEH0yXycDvta8GAvq8=測(cè)到的社區(qū)演變事件也更少。但該算法也存在一些缺陷，例如在參數(shù)設(shè)置方面無(wú)法做到自適應(yīng)，這也為之后的研究提供了一種可能的方向。

在未來(lái)的工作中，其不僅用于解決當(dāng)前的社區(qū)檢測(cè)問題，而且要面向更多發(fā)生顯著變化的場(chǎng)景。例如將高階信息傳遞的概念遷移到動(dòng)態(tài)網(wǎng)絡(luò)布局中，構(gòu)建多目標(biāo)模型，對(duì)發(fā)生巨大變化的網(wǎng)絡(luò)進(jìn)行布局，保留先前布局方案的優(yōu)勢(shì)并應(yīng)用到下一個(gè)任務(wù)中。因此還需不斷地探索更好的分析交互方式，同時(shí)提供一些動(dòng)態(tài)可視化技術(shù)以及一定的交互，方便用戶理解和挖掘動(dòng)態(tài)數(shù)據(jù)背后有價(jià)值的信息。

參考文獻(xiàn)：

［1］蔣云， 楊文東. 改進(jìn)Louvain算法的多層航線網(wǎng)絡(luò)社區(qū)劃分 ［J］. 北京交通大學(xué)學(xué)報(bào)， 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］歐陽(yáng)資生， 楊希特， 黃穎. 嵌入網(wǎng)絡(luò)輿情指數(shù)的中國(guó)金融機(jī)構(gòu)系統(tǒng)性風(fēng)險(xiǎn)傳染效應(yīng)研究 ［J］. 中國(guó)管理科學(xué)， 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］沈力峰， 王建波， 杜占瑋，等. 基于社團(tuán)結(jié)構(gòu)和活躍性驅(qū)動(dòng)的雙層網(wǎng)絡(luò)傳播動(dòng)力學(xué) ［J］. 物理學(xué)報(bào)， 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］嚴(yán)玉為， 蔣沅， 楊松青，等. 基于時(shí)間序列的網(wǎng)絡(luò)失效模型 ［J］. 物理學(xué)報(bào)， 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］梁文， 閆飛， 陳柏圳. 兩階段量子行走算法在社區(qū)檢測(cè)中的應(yīng)用 ［J］. 計(jì)算機(jī)應(yīng)用研究， 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］李輝， 陳福才， 張建朋，等. 復(fù)雜網(wǎng)絡(luò)中的社團(tuán)發(fā)現(xiàn)算法綜述 ［J］. 計(jì)算機(jī)應(yīng)用研究， 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.