動態網絡社團發現及演化模式分析方法

摘 要：

如何充分考慮網絡的演化過程準確發現動態網絡的社團結構，并對社團演化模式進行跟蹤和分析是動態網絡社團發現的重要挑戰。提出一種動態網絡社團發現及演化模式分析算法EC-DCD。該算法利用前一時刻的社團發現結果作為先驗信息來減少網絡噪聲對社團發現的影響，利用演化聚類框架平滑連續時刻的社團演化，獲得每個時刻準確的社團結構。同時，引入社團演化矩陣對社團演化模式進行建模和跟蹤，實現社團演化模式的分析和可視化。實驗部分，將EC-DCD同基線算法FacetNet、DYNMOGA、DNMF、NE2NMF和CoDeDANet在人工數據集與真實數據集上進行了對比實驗，實驗結果證明EC-DCD不僅能夠準確地劃分每個時刻的社團結構，具有較強的穩定性，還能夠跟蹤社團的演化模式。

關鍵詞：社團發現；動態網絡；演化聚類框架；非負矩陣分解；演化模式

中圖分類號：TP181"" 文獻標志碼：A""" 文章編號：1001-3695（2024）12-026-3722-07

doi： 10.19734/j.issn.1001-3695.2024.05.0141

Dynamic network community detection and evolution mode analysis method

Pan Yu1， Yao Feng1， Liu Xin2， Zhang Lei3， Wang Shuaihui4， Wang Pei1

（1.National University of Defense Technology， Changsha 410000， China; 2. Army Engineering University， Nanjing 310000， China; 3. Aca-demy of Military Science， Beijing 110000， China; 4. Naval Command College， Nanjing 310000， China）

Abstract：

How to obtain accurate community structure of the dynamic network， model the dynamic evolution process of the network， and realize the tracking and analysis of the community evolution mode is an important challenge for detecting dynamic network communities. This paper proposed a dynamic network community detection algorithm EC-DCD. The algorithm utilized the previous community detection results as a priori information to reduce the impact of network noise on community detection. It applied an evolutionary clustering framework to smooth the community evolution over consecutive time， achieving community structures at each time step. At the same time， it introduced the community evolution matrix to model and track the evolution mode of the community， which could realize the analysis and visualization of the community evolution mode. In the experiment， this paper tested the EC-DCD algorithm and baseline algorithms such as FacetNet， DYNMOGA， DNMF， NE2NMF， and CoDeDANet on the artificial datasets and the real datasets. The experimental results show that the proposed method EC-DCD can not only accurately detect the community structure at every moment， but also track the evolution pattern of the community.

Key words：community detection; dynamic network; evolutionary clustering; nonnegative matrix factorization; evolution mode

0 引言

在復雜網絡中，社團結構是廣泛存在的重要潛在結構。發現網絡中的社團結構對探索網絡潛在特性、理解網絡組織結構、發現網絡隱藏規律和交互模式等具有重要的理論和現實意義，是網絡分析任務的關鍵研究內容［1］。在現實生活中，隨著網絡中節點和邊的增加與減少，網絡的拓撲結構和社團結構都會不斷發生演化。例如，在學術網絡中，擁有相同研究領域的學者往往構成一個社團，研究熱點的變化和研究者興趣的改變，使得社團具有復雜的動態性。網絡的不斷演化可能導致社團結構的巨大變化和被重新發現的需求。通過挖掘動態變化的社團結構，人們能夠認清網絡中隱含的內部結構，深入理解個體的行為特點和網絡演化趨勢，揭示網絡中存在的普遍性特征和規律。精準挖掘動態網絡的社團結構不僅對揭示復雜網絡的結構和網絡功能具有重要的理論意義，而且對于信息擴散、輿情傳播、病毒感染等不同領域管理水平與治理能力的提高具有重要的現實指導意義。例如，在“新冠”病毒傳播引起的肺炎疫情中，病毒的傳播與感染者社交活動中存在的顯性或隱性社團結構密切相關，呈現聚集性特點。對其進行社團發現可以準確識別和掌握病毒感染者的社團歸屬特征，有助于快速鎖定密切接觸者，從而為疫情的防控起到積極的作用［2］。在云計算中，通過分析服務間的流量挖掘虛擬網元之間的社團結構，可以為數據中心的微服務部署和調度提供指導意見，進一步優化運營商的效率并減少運營代價；在IP網絡中，對IP網絡的社團結構進行挖掘和分析有利于理解網絡流量，從而為網絡優化和安全管理提供有用的信息和決策支持；在通話網絡中對用戶類別進行識別有助于分析用戶通信模式和特征，從而提供定向的推薦服務和安全布控［3］。

文獻［4］定義了社團的新生、消亡、增長、收縮、持續、分裂和重生七種社團演化行為。動態網絡拓撲結構不可預測和快速變化的特性為社團發現提出了嚴峻的挑戰，傳統的靜態社團發現算法已經不能滿足在動態變化的網絡中準確挖掘社團結構的需求。相比于靜態網絡的社團發現，動態社團發現算法的設計更具有挑戰性，主要有以下幾點原因。首先，動態網絡社團發現不僅要考慮社團結構的劃分是否準確，還要充分考慮動態網絡的演化過程。例如，圖1（a）為靜態社團發現示意圖，網絡中的節點根據連接的緊密程度被劃分為3個社團。對于動態網絡的社團發現，圖1（b）的上下兩部分分別表示t和t-1時刻的網絡快照Gt和Gt-1。在t時刻有兩種社團劃分策略，分別用劃分1和2兩條虛線表示。如果不考慮網絡的動態演化，劃分策略1和2在t時刻擁有相同的社團劃分質量。但是，如果考慮網絡的動態演化，劃分策略2要好于策略1。因為劃分策略2在t和t－1時刻的劃分更相近，所以相比于劃分策略1更加合理。所以，動態網絡的社團發現既要考慮每個時刻的社團發現質量還要考慮動態網絡的演化過程。其次，動態社團發現的另一個挑戰是解的不穩定性問題。無法確定劃分結果的變化是由社團的自然演化引起的，還是由于網絡中噪聲或算法不穩定性造成的。對此，研究者們提出了大量的解決方案，其最終目標是使社團的演化更加平滑。為了解決這個問題，Chakrabarti等人［5］提出了演化聚類框架，該框架是目前應用最廣泛的動態社團發現方法之一。其假設在短時間內聚類的突然變化可能是由噪聲引起的，并且不期望聚類發生突然變化。Pallaet等人［6］通過研究科學家合作網絡的動態演變過程，發現在短時間內社團不會發生劇烈的變化，并且提出社團發生大規模演化后，社團的生命周期將會更長。這證明了演化聚類模型的假設與現實網絡的特質相吻合。最后，捕捉動態的社團演化模式對于理解動態網絡深層特征和演化方向至關重要。如何捕捉動態網絡中的社團演化模式和過程、跟蹤動態演化進程是動態社團發現面臨的重要挑戰。

雖然研究者們對于動態網絡的社團發現方法付出了巨大的努力，但仍有許多問題有待解決。a）已提出的大多數方法并沒有利用重要的先驗信息來提高社團發現的準確率。b）在動態網絡中，社團結構和時間演化特征是同步存在的，捕捉社團的演化過程有助于從本質上理解動態網絡的演化模式。然而，大多數動態社團發現算法未對社團的動態演化過程直接進行建模，從而無法描述和可視化社團的演化過程。c）大多數基于演化聚類的算法只適用于社團和節點個數不發生改變的場景。然而，節點的加入和離開，社團的新增和減少是網絡中常見的動態變化場景。如何在演化聚類框架中處理社團和節點數量發生變化的情況是一個亟需解決的問題。

針對以上問題和挑戰，本文提出了一個強大、可解釋的動態網絡社團發現框架EC-DCD來挖掘動態網絡中的社團結構，其主要框架如圖2所示。EC-DCD算法不僅能夠準確地挖掘動態網絡中的社團結構，還可以同步捕捉社團的演化模式，實現社團演化過程的可視化。在動態變化的網絡中，個別節點的變動存在隨機性，所以網絡中往往存在大量噪聲。首先，為了抑制噪聲對社團發現結果的影響，EC-DCD算法將t－1時刻的社團發現結果作為t時刻的先驗信息，從而提高社團發現的準確率。然后基于演化聚類框架，通過對鄰接矩陣進行非負矩陣分解獲得社團指示矩陣來評價當前時刻的社團發現質量。為了分析社團演化過程，本文對社團演化模式進行建模，假設在每個時刻存在一個演化模式，將其表示為一個隨時間變化的社團演化矩陣。并利用演化矩陣來評價當前時刻與歷史時刻社團劃分結果的符合度。

總的來說，本文的主要貢獻如下：

a）算法利用前一時刻的社團發現結果作為先驗信息優化當前的網絡拓撲結構，從而減少網絡噪聲和毫無根據的網絡演化對社團劃分的影響，提高社團發現的準確度；

b）基于演化聚類框架，利用NMF模型得到動態網絡中每個時刻準確的社團結構，同時平滑連續兩個時刻的社團發現結果；

c）對動態社團的演化模式進行建模，引入社團演化矩陣對社團的演化模式進行捕捉和跟蹤，同時實現對社團演化過程的分析和可視化；

d）在多個真實和人工數據集上進行了大量實驗，實驗結果證明EC-DCD與對比算法相比，獲得了準確并且穩定的社團發現性能，同時實現了對社團演化過程的可視化。

1 相關工作

近年來，涌現出了大量方法用于解決動態網絡中的社團發現問題。可以將這些方法分為增量聚類方法和演化聚類方法。

增量聚類算法［7～14］嘗試將靜態網絡的社團發現方法擴展到動態網絡中，其主要思想是利用靜態社團發現方法在第一個網絡快照中發現社團結構，然后根據連續兩個時刻快照之間節點和邊的動態變化來劃分后續快照的社團結構，當前時刻的社團結構是從前一時刻的社團結構中推導而來。代表算法有IA-MCS［7］、GraphScope［8］等。增量聚類方法可以直接使用靜態的社團發現算法，比較容易實現。然而，增量聚類算法忽略了噪聲對每個時刻社團發現的影響，從長期和全局角度來看，這種方法不能保證社團發現結果的一致性。

演化聚類算法［15～29］是目前最流行的一種動態網絡社團發現方法，最早被Chakrabarti等人［5］提出用于流數據的聚類，通過將其應用于K-means和凝聚層次聚類算法以處理不斷變化的數據。演化聚類框架假設短時間內的聚類結果不會發生劇烈變化，網絡的突變多是由于噪聲引起的，并引入時間損失函數對下一時刻突變的社團劃分進行懲罰。Chi等人［18］首次將演化聚類算法用于動態網絡的社團發現問題，通過快照代價（snapshot cost，CS）來評價當前時刻社團發現的準確度，通過時間代價（temporal cost，CT）來度量連續兩個時刻社團發現結果的相似性。以演化聚類框架為基礎，Lin等人［19］提出了時間平滑（temporal smoothness）框架用于動態網絡的社團發現，并提出了研究社團動態演化的統一框架FacetNet，該算法是目前最經典且廣泛使用的動態社團發現算法。FacetNet采用隨機塊模型生成社團，并通過一個健壯的統一過程來分析社團及其演化，該過程考慮了社團演化過程和演化的時間平滑性。隨后，Folino等人［20］提出了一種基于多目標優化的演化聚類算法DYNMOGA，該算法將快照代價和時間代價看做一個多目標函數，在最大化快照代價的同時最小化時間代價。ECGNMF算法［21］通過NMF框架擬合每個時間片的社團發現情況，從而獲得每個時刻的社團結構。對于時間代價，算法不僅考慮了介觀社團歷史信息，還考慮了節點的微觀變化信息，通過引入正則化項對兩個連續時間的微觀節點變化進行約束，平滑連續時間內微觀節點的變化情況。Ma等人［23］提出了一種基于共同正則化非負矩陣分解的動態網絡社團發現算法Cr-ENMF，該算法利用前一時刻的網絡和社團結構來表征時間代價，并將其通過正則化項加入到目標函數中，成功挖掘動態網絡中的社團結構。Wang等人［24］提出了一種新的動態圖正則化對稱非負矩陣分解方法DGR-SNMF，該方法引入網絡的幾何結構來表征網絡拓撲在短時間內的時間平滑性，巧妙地通過把圖正則化項作為時間代價函數，將幾何結構信息充分融合到社團發現過程中。Li等人［25］將圖嵌入引入動態網絡社團發現中，利用前一時刻、當前時刻和下一個時刻的網絡快照設計三階平滑策略，充分表征社團演化。雖然已提出的算法實現了對動態網絡的社團結構挖掘，但大多數算法未對社團的動態演化模式進行直接建模，從而無法描述和可視化社團的演化過程。由此可知，基于演化聚類框架的社團發現方法的主要挑戰是如何平衡快照代價CS和時間代價CT，以及如何量化時間代價CT并對社團演化模式進行建模。

2 相關定義

2.1 符號

對于一個隨時間演化的動態網絡，本文將其表示為一系列時刻{1，2，…，T}的網絡序列快照Gt={G1，G2，…，GT}，T為快照數量。其中，Gt=（Vt，Et）表示t時刻的網絡快照，Vt為t時刻的節點集合，Et為t時刻節點之間邊的集合。本文用網絡快照對應的鄰接矩陣At={A1，A2，…，AT}表示動態網絡，其中At=（aij，t）n×n×T表示t時刻的網絡快照，n為節點數量，如果節點vi和vj在t時刻有連接，則aij，t=1，否則aij，t=0。表1總結了本文所用的符號及定義。

給定一個動態網絡Gt={G1，G2，…，GT}，動態網絡社團發現的目標為：a）對當前時刻的網絡快照進行準確的社團結構挖掘，將網絡中的節點劃分為k個社團，使社團發現結果與真實的社團結構盡可能相同。動態網絡的社團結構由每個時刻社團的集合構成Ct={C1，C2，…，CK}；b）連續時刻的社團發現結果Ct和Ct-1不會發生劇烈變化，社團的演化是平滑的；c）建立描述社團演化生命周期的進化鏈，對社團演化模式進行建模，實現社團演化過程的跟蹤和分析。

2.2 演化聚類框架

演化聚類框架假設社團結構在短時間內不會發生突變，連續兩個時刻的社團結構演化具有平滑性。演化聚類框架由快照代價CS和時間代價CT的線性組合構成。其中，CS用于衡量t時刻社團發現結果Ct與真實社團結構的相符程度，CT用于衡量t時刻社團發現結果Ct與t－1時刻社團發現結果Ct-1之間的差異。基于演化聚類的動態網絡社團發現方法需要滿足兩個條件：一是社團劃分結果應該盡可能準確地表示當前的網絡結構；二是連續兩個時刻，社團發現的結果是平滑的，沒有顯著的突變。演化聚類的最終目標是在兩個子模塊之間取得平衡：

Cost=α·CS+（1－α）·CT（1）

其中：α∈（0，1）為權重系數，用于平衡CS和CT的權重比例。當α=1時，方法返回的結果為沒有考慮連續時刻的社團演化特征，動態社團發現問題等價于靜態社團發現問題。當α=0時，框架得到與上一時刻相同的社團發現結果，即CRt=CRt－1。

3 EC-DCD模型

3.1 快照代價

對于快照代價CS部分，EC-DCD期望在當前時刻獲得與真實社團結構相符的社團劃分。首先引入社團指示矩陣H∈Euclid ExtraaBpn×k，如果兩個節點屬于同一個社團，那么它們之間生成邊的概率很高。因此，本文期望HHT的每個元素都盡可能和網絡鄰接矩陣A相接近。假設網絡中節點之間邊數的期望HHT和鄰接矩陣A中可觀察邊數之間的誤差服從均值為0、標準差為σ的高斯分布：

aij－∑khikhjk～N（0，σ2）（2）

根據高斯概率密度函數，得到其似然函數為

L=∏i≠j12πσ（－12（aij－∑khikhjkσ）2）（3）

最大化L等于最大化log L：

log L=∑ij-12（aij－∑khikhjk）2+c=

－12（∑ij（aij－∑khikhjk）2）+c（4）

因為‖A－HHT‖2F=∑ij（aij－∑khikhjk）2，所以目標函數為

L（A，H）=‖A－HHT‖2F（5）

其中：‖A‖2F=∑ni=1 ∑dj=1|aij|2。在本節中，Ht是t時刻的社團指示矩陣，Ht的每一行表示在t時刻節點屬于每個社團的隸屬度情況，其中him，t代表t時刻節點vi隸屬于社團cm的概率。可以推導出him，thjm，t是節點vi和vj在t時刻在社團cm內連接邊數的期望，∑klhil，thjl，t為整個網絡中節點vi和vj在t時刻連接邊數的期望，所以HtHTt代表在t時刻任意兩個節點之間生成邊的期望。本文期望t時刻的社團發現結果盡可能和t時刻的鄰接矩陣At相似。因此，快照成本CS函數如下：

CS=‖At-HtHTt‖2F（6）

3.2 時間代價

對于時間代價，演化聚類框架假設連續兩個時刻的社團結構演化是平滑的，不會發生劇烈改變。因此，本文假設節點歸屬的社團在連續兩個時刻不會發生劇烈變化，節點在t－1時刻屬于社團ci，那么它有很大的概率在t時刻也屬于社團ci。為了進一步探索和分析動態網絡的時間演化模式，本文引入社團演化矩陣Gt∈Euclid ExtraaBpk×k對社團演化模式進行建模。通過對社團演化矩陣的分析可以捕獲社團演化趨勢、預測社團活動和實現對社團演化過程的可視化，從而實現對社團動態演化過程的跟蹤和分析。其中，矩陣Gt的元素gij，t表示節點在t時刻從社團ci轉移到社團cj的概率。因此，節點在t時刻隸屬于社團的情況Ht，應該由t－1時刻節點隸屬于社團的情況Ht－1和社團轉移概率Gt共同演化而來。節點vi在t－1時刻隸屬于社團cl的概率hil，t－1與t時刻節點vi從社團cl轉移到社團cm的概率glm，t的乘積應該和t時刻節點vi屬于社團cm的概率him，t盡可能相近，即him，t≈hil，t－1glm，t。因此，本文定義時間代價CT函數為

CT=‖Ht－1Gt－Ht‖2F（7）

3.3 先驗信息

為了減少噪聲以及毫無根據的網絡演化對社團發現結果的影響，算法將t－1時刻的社團發現結果作為t時刻的先驗信息來優化t時刻的網絡拓撲，從而提高社團發現的準確度。先驗信息定義為

A*t=At-β（Ht-1HTt-1）（8）

其中：A*t為優化后t時刻的鄰接矩陣；β為先驗信息的權重系數。基于此，通過式（8）將前一時刻的社團發現信息作為當前時刻的先驗信息融合到演化聚類框架中，可以調整兩個連續時刻網絡拓撲之間的平滑度，從而減少噪聲對社團發現的影響，提高算法的精度。因此，最終的目標函數為

minHt，Gt‖A*t-HtHTt‖2F+α‖Ht-1Gt-Ht‖2F "if t≥2

minHt‖At-HtHTt‖2F if t=1

s.t. （Ht）ij≥0， （Gt）ij≥0" i， j（9）

其中：α為權重系數，用于平衡快照代價和時間代價的權重比例。

4 模型優化和分析

由于式（9）的求解是非凸優化問題，很難求出全局最優解。本文采用迭代優化的方法求解目標函數，通過固定其他變量來優化一個變量。首先，為了推導式（9）在非負約束下的更新規則，分別引入拉格朗日乘子和ε，式（9）的拉格朗日函數為

當t=1時，

5 EC-DCD算法

擴展基于演化聚類框架的固有假設較為困難，多數基于演化聚類的算法都無法處理節點和社團數量隨時間變化的場景。但在動態網絡中，節點和社團的增加和減少是常見的情況。因此，本文針對社團和節點發生變化的情況分別提出了相應策略進行解決。

a）處理網絡中節點變化的情況。針對網絡中節點個數發生增加和減少的情況，當網絡中有新的節點加入時，在鄰接矩陣的行和列分別填充0。類似地，如果網絡中的節點減少，則將其對應的行和列刪除。這樣，兩個矩陣變為相同規模，可以進行之后的計算。通過此策略將模型擴展到節點數量隨時間變化的情況。

b）處理網絡中社團變化的情況。針對網絡中社團發生變化的情況，本文引入以下規則來確定每個時刻的社團個數kt：

kt=argmin "k‖∑ki=1ηiTsiTs′iT‖‖At‖gt;τ（21）

其中：ηiT是矩陣At的特征值；siT是特征值對應的特征向量。矩陣At可以根據特征值和特征向量進行重建，At=∑ki=1ηiTsiTs′iT。隨著特征向量的增加，At和特征分解之間的誤差‖At－∑ki=1ηiTsiTs′iT‖2變小。所以當參數τ取適當的值時，可以在特征值盡量小的情況下達到一個很好的平衡，從而確定社團個數。參數τ是一個經驗值，根據文獻［20］，將τ設置為0.55。

此外，考慮到社團結構隨時間演化的平滑性，如果社團數量在連續內時間保持穩定，則用Ht－1來更新Ht；當連續內社團數發生變化，則進行隨機初始化，而不使用前一時刻的社團指示矩陣作為初始值。

算法1：EC-DCD算法

輸入：動態網絡序列Gt={G1，G2，…，GT}；參數α、γ。

輸出：每個時刻的網絡社團劃分Ct={C1，C2，…，CT}。

for t=1， 2，…， T do

根據式（21）確定網絡中社團個數

初始化Ht、Gt

if t=1 do

repeat

根據式（18）更新H1

until convergence

得到t=1時刻的社團C1

else do

repeat

對于每個時刻t，根據式（8）計算先驗信息A*t

根據式（19）更新Ht

根據式（20）更新Gt

until convergence

得到t時刻的社團更新Ct

end for

6 實驗結果分析

6.1 基準方法

為了驗證EC-DCD算法的有效性，實驗選擇五個具有代表性的動態網絡社團發現算法作為對比算法，分別為FacetNet、DYNMOGA、DNMF、NE2NMF和CoDeDANet。

a）FacetNet［19］。FacetNet將快照代價定義為觀測到的節點相似性矩陣與用混合模型計算出的近似社團結構之間的KL散度，并將時間代價定義為t和t－1時刻社團結構劃分的差異。

b）DYNMOGA［20］。DYNMOGA首先最大化快照代價來度量社團發現的質量，然后計算兩個時刻社團劃分的標準化互信息（NMI）來測量當前時刻獲得的社團結構與前一個時刻獲得的社團結構之間的相似性。

c）DNMF［29］。DNMF利用全概率模型挖掘鄰接矩陣與NMF分解結果之間的歐幾里德距離，并對兩個連續快照中的矩陣分解結果進行約束。

d）NE2NMF［25］。NE2NMF從多個角度充分刻畫社團的動態變化，并通過分解每個時間快照的低維圖嵌入來減少運行時間。

e）CoDeDANet［30］。CoDeDANet首先利用譜聚類獲得每個時刻的社團結構，然后利用張量同時考慮社團當前結構和歷史結構。

6.2 人工數據集性能分析

6.2.1 人工數據集1性能分析

人工數據集1是文獻［25］使用的人工數據集，其中包含SYN-FIX和SYN-VAR兩種類型的動態網絡。SYN-FIX網絡由128個節點組成，所有節點被平均分為4個社團，節點的平均度數為16，網絡中的節點與其他社團的節點有zout條邊相連。本節實驗分別設置zout=3和5，當zout增加時，網絡中的噪聲水平也隨之增加，挖掘網絡中社團結構的難度加大。為了引入網絡的動態變化，SYN-FIX網絡在t－1時刻從每個社團中隨機選擇3個節點，并在t時刻分配給其他社團。SYN-FIX網絡在所有時刻的社團數量不發生變化，社團數量始終為4。SYN-VAR網絡由256個節點組成，所有節點被平均分為4個社團，節點的平均度為16。同樣，本節將zout設置為3和5。不同于SYN-FIX網絡，SYN-VAR網絡通過社團的新生和消亡來實現社團的動態變化。SYN-VAR網絡在t－1時刻從每個社團中隨機選擇8個節點，在t時刻將這些節點構成一個新的社團，連續5個時刻重復此過程，然后再經過5個時刻將這些節點返回到原始社團。圖3、4分別為算法在SYN-FIX和SYN-VAR數據集上的社團發現結果。

從圖3、4可以得出，EC-DCD在SYN-FIX和SYN-VAR數據集上的所有時刻都取得了優于其他基線算法的社團發現結果。特別是在SYN-FIX網絡中，在zout=3和5兩種情況下，EC-DCD在10個時刻取得的NMI指標值均為1，算法劃分的社團結構和真實社團結構完全相同。對于社團個數發生變化的SYN-VAR網絡，EC-DCD也取得了所有時刻 NMI均大于0.96的優異性能。相比于其他基線算法，EC-DCD不僅在2個數據集的所有時刻都取得了最好的社團發現結果，而且社團發現結果曲線比較平滑，相鄰時刻的社團發現結果沒有突變，這說明本文方法不僅能夠準確地發現真實的社團結構，而且在連續時刻的社團劃分性能非常穩定。

6.2.2 人工數據集2性能分析

人工數據集2是基于LFR基準［31］生成的冪律網絡。相比于人工數據集1，基于LFR基準生成的數據集更加貼合真實網絡情況，發現社團結構的難度也更大。本節實驗利用LFR基準生成2個人工數據集作為初始網絡，詳細信息如表2所示。對于數據集通過以下兩種操作引入動態網絡生成5個時刻的網絡快照：a）不改變社團的個數，從每個社團中隨機選擇一定數量的節點離開原社團，并隨機加入其他社團；b）改變社團個數，通過社團的新生和消亡實現社團的動態變化。對于LFR-1，通過第一種操作引入動態網絡。在每個時刻，從每個社團中隨機選擇6個節點改變其連接，從而改變其所屬社團情況。對于LFR-2，通過第二種操作引入動態網絡，在第2和3個時刻隨機選擇1個社團分裂成2個社團，并在第4和5個時刻選擇2個社團合并成1個社團。因此，網絡LFR-2在5個時刻社團的個數分別為：26、27、28、27、26。EC-DCD與其他基線算法在5個時刻的NMI結果和所有時刻的平均NMI結果如表3、4所示。

雖然基于LFR基準生成的人工數據集增加了社團發現的難度，但EC-DCD仍然獲得了理想的社團發現結果。與其他的基線算法相比，在所有數據集上的所有時刻均取得了最佳的性能。這主要得益于EC-DCD基于演化聚類框架，利用非負矩陣分解獲得當前時刻社團劃分結果，使其盡可能貼近當前網絡的真實社團結構，同時引入社團演化矩陣平滑連續時刻的社團演化。不僅如此，EC-DCD還利用前一時刻的社團劃分結果作為先驗信息優化當前拓撲，在提高社團劃分準確度的同時平滑每個時刻的劃分結果。

6.3 真實數據集KIT-Email性能分析

KIT-Email數據集（http：//i11www.iti.uni-karlsruhe.de/en/ projects/spp1307/emaildata）是由卡爾斯魯厄理工學院（Karlsruhe Institute of Technology，KIT）計算機科學系從2006年9月至2010年8月共48個月的電子郵件所構成的電子郵件通信網絡。對于KIT-Email電子郵件網絡，節點是KIT計算機科學系的成員，邊的權重對應兩個節點之間發送電子郵件的數量，計算機科學系的不同研究小組對應不同社團。本節分別以2、3、4和6個月為間隔分為幾個時間快照，其中T=24（連續2個月為一個網絡快照），T=16（連續3個月為一個網絡快照），T=12（連續4個月為一個網絡快照），T=8（連續6個月為一個網絡快照）。因為聯系人之間的聯系是稀疏的，所以實驗選擇活躍的用戶構成鄰接矩陣。其中，網絡中的節點數在138～231，社團個數在23～27。每個時刻快照及所有時刻快照上的平均NMI作為社團發現結果，如表5所示。

如表5所示，本文EC-DCD比其他方法獲得更好的性能。隨著快照數的減少，所有算法在NMI上的性能都趨于下降，因為間隔越短，數據點被視為孤立點的次數越多。所提EC-DCD在所有情況下都獲得了最優的動態社團劃分結構，雖然表現次優的CoDeDANet也利用張量充分考慮了歷史信息，但是本文方法對于噪聲具有魯棒性，更加穩定。根據本文方法對動態郵件網絡的用戶進行社團劃分，可以發現經常聯絡的郵件用戶群體，進一步向不同分組提供感興趣的社交內容，定向投放廣告等，給用戶提供更加穩定優質的服務。不僅如此，通過分組可以識別出在動態變化的動態網絡中經常通信的人，識別出網絡的關鍵節點，對網絡的穩定性和信息傳播起著重要作用。對動態變化的動態郵件網絡進行社團發現，能夠幫助優化資源分配，更好地配置網絡資源以滿足經常通信群體的需求，提高網絡的效率和性能。

6.4 真實數據集CPC性能分析

CPC數據集由Paraiso運動成員之間在2006年6月中10天的手機通話記錄組成。該網絡的節點為全網唯一的手機號，兩個手機之間的呼叫構成網絡中的邊。由此，可生成包含10個時刻的動態網絡序列，每個時刻的網絡為每天400個節點之間相互通信形成的網絡。由于數據集真實的社團結構是未知的，本文使用模塊度Q來衡量社團發現的有效性，在CPC手機通信網絡數據上每種方法進行10次實驗，取平均結果作為實驗結果，如圖5所示。

從圖5可以看到，EC-DCD在除第一個沒有歷史幾何結構信息可用的網絡之外的其他所有網絡快照中都得到了最佳的性能，表現為具有更大的模塊度值。CoDeDANet雖然在第一個時刻利用了譜聚類方法獲得了最佳模塊度，但在之后的時刻，性能沒有EC-DCD好，這主要因為EC-DCD不僅充分利用了歷史演化信息，還利用先驗信息減少了噪聲對于社團劃分結果的影響。通過所提算法對用戶類別進行識別分組，有助于分析用戶通信模式和特征，從而提供定向的推薦服務和安全布控。具體地，通過對動態網絡進行社團發現，可以更好地了解他們之間的通信模式和頻率，從而更好地監測和分析網絡中的信息傳播和交互模式。除此之外，將經常通信的人劃分到一個組可以幫助進行更精細化的安全管理，有助于提高網絡的安全性，防范潛在的安全風險和威脅。

6.5 社團演化模式分析

EC-DCD通過引入社團演化矩陣Gt對社團動態演化模式進行建模，矩陣Gt的元素glk，t表示在t時刻節點從社團l轉移到社團k的概率，其量化了節點在社團之間轉移的趨勢。為了分析動態網絡中社團演化的模式，本節在人工數據集2上對連續4個時刻的社團演化過程進行可視化，進一步分析社團的演化過程。其中，在人工數據集2中設置zout=4，C=10%，并生成5個時刻的動態網絡。

圖6展示了連續4個時刻社團演化過程的可視化結果，在圖6中，y軸為當前時刻的社團標簽k，x軸為下一個時刻的節點所屬社團標簽l，每個方格的顏色代表節點從社團k轉移到社團l的概率，其值分別對應轉移概率矩陣G中元素的值。如圖6所示，圖中對角線的值始終大于其他格子，這表示在大多數情況下，相比于轉移到其他社團，節點在下一時刻有較大概率繼續保留在當前社團，這也間接證明了社團演化的平滑性。但隨著網絡的持續演化，網絡中的社團結構也會發生變化。

6.6 參數分析討論

本節對算法參數α和β的敏感度進行討論，分別將其設置為{0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8，0.9，1}，通過不同的參數組合來觀察EC-DCD在LFR-1網絡上的社團發現性能。圖7分顯示了EC-DCD在不同參數組合下的社團發現結果。可以從圖7得到結論，當0.2≤α≤0.8和0.2≤β≤0.6時，EC-DCD取得了比較優異并且平穩的性能。

7 結束語

本文針對復雜網絡不斷演化的動態特性，對動態網絡中的社團結構挖掘問題展開了研究，提出了一種基于演化聚類的動態網絡社團發現算法EC-DCD。該算法利用NMF框架使當前時刻的社團劃分結果盡可能貼近真實的社團結構，同時保證相鄰時刻的社團結構演化具有平滑性。為了探索社團的演化模式，算法引入社團演化矩陣對社團演化過程進行直接建模，實現對社團演變過程的跟蹤和分析。此外，EC-DCD利用前一時刻的社團劃分結果作為先驗信息對當前的網絡拓撲結構進行優化，從而減少噪聲對社團結構挖掘的影響，進一步提高社團發現的準確度。實驗證明，EC-DCD在各種類型的人工數據集和真實數據集上都取得了優異的社團劃分性能，并且實現了對社團演化過程的可視化。

隨著網絡規模和數據維度的不斷擴大，需要更強大的技術來保持有效和高效的性能以及可行的計算速度。近年來，深度學習在社會計算領域發展迅速，其中圖神經網絡將深度學習的方法應用到非歐氏空間結構的數據中，對社團結構挖掘和網絡表示與建模都具有重要的意義。在未來的研究中，可以引入圖神經網絡等先進深度學習技術實現動態網絡社團發現。

參考文獻：

［1］潘雨， 鄒軍華， 王帥輝， 等. 基于網絡表示學習的深度社團發現方法［J］. 計算機科學， 2021， 48（11A）： 198-203. （Pan Yu， Zou Junhua， Wang Shuaihui， et al. Deep community discovery method based on network representation learning［J］. Computer Science， 2021， 48（11A）： 198-203.）

［2］潘雨， 王帥輝， 張磊， 等. 復雜網絡社團發現綜述 ［J］. 計算機科學， 2022， 49（11A）： 208-218. （Pan Yu， Wang Shuaihui， Zhang Lei， et al. A review on the discovery of complex network societies ［J］. Computer Science， 2022， 49（11A）： 208-218.）

［3］潘雨， 胡谷雨， 王帥輝， 等. 基于約束非負矩陣分解的符號網絡社團發現方法 ［J］. 計算機應用研究， 2020， 37（S2）： 82-86. （Pan Yu， Hu Guyu， Wang Shuaihui， et al. Community discovery method for symbolic networks based on constrained non-negative matrix decomposition ［J］. Application Research of Computers， 2020， 37（S2）： 82-86.）

［4］Rossetti G， Cazabet， Rémy. Community discovery in dynamic networks： a survey［J］. ACM Computing Surveys， 2017， 51（2）： 1-37.

［5］Chakrabarti D， Kumar R， Tomkins A. Evolutionary clustering［C］// Proc of the 12th ACM SIGKDD International Conference on Know-ledge Discovery and Data Mining. New York： ACM Press， 2006： 554-560.

［6］Palla G， Barabási A L， Vicsek T. Quantifying social group evolution［J］. Nature， 2007， 446（7136）： 664-667.

［7］Zhuang Di. Modularity-based dynamic community detection ［J］. IEEE Trans on Knowledge and Data Engineering， 2017， 33： 1934-1945.

［8］Karaaslanl Abdullah， Aviyente S. Community detection in dynamic networks： equivalence between stochastic blockmodels and evolutiona-ry spectral clustering ［J］. IEEE Trans on Signal and Information Processing over Networks， 2021， 7： 130-143.

［9］Xu Cong， Lee T C M. Statistical consistency for change point detection and community estimation in time-evolving dynamic networks ［J］. IEEE Trans on Signal and Information Processing over Networks， 2022， 8： 215-227.

［10］Zhuang Di， Chang J M， Li Mingchen. DynaMo： dynamic community detection by incrementally maximizing modularity［J］. IEEE Trans on Knowledge and Data Engineering， 2021， 33（5）： 1934-1945.

［11］Yang Bo， Liu Dayou. Force-based incremental algorithm for mining community structure in dynamic network［J］. Journal of Computer Science and Technology， 2006， 21（3）： 393-440.

［12］Guo Kun， He Ling， Huang Jiangsheng， et al. A local dynamic community detection algorithm based on node contribution ［C］// Proc of Conference on Computer Supported Cooperative Work. Singapore： Springer， 2019： 363-376.

［13］Wu Zhenyu， Chen Jiaying， Zhang Yinuo. An incremental community detection method in social big data［C］// Proc of the 5th International Conference on Big Data Computing Applications and Technologies. Piscataway， NJ： IEEE Press， 2018： 136-141.

［14］Hu Yanmei， Yang Bo， Lyu Chenyang. A local dynamic method for tracking communities and their evolution in dynamic networks［J］. Knowledge-Based Systems， 2016， 110： 176-190.

［15］Al-Sharoa E， Al-Khassaweneh M， Aviyente S. Tensor based temporal and multilayer community detection for studying brain dynamics during resting state fMRI ［J］. IEEE Trans on Biomedical Engineering， 2019， 66（3）： 695-709.

［16］Sariyüce A E， Gedik B， Jacques-Silva G， et al. SONIC： streaming overlapping community detection ［J］. Data Mining and Knowledge Discovery， 2016， 30（4）： 819-847.

［17］Li Xiaoming， Wu Bin， Guo Qian， et al. Dynamic community detection algorithm based on incremental identification ［C］// Proc of IEEE International Conference on Data Mining Workshop. Pisca-taway， NJ： IEEE Press， 2015： 900-907.

［18］Chi Yun， Song Xiaodan， Zhou Dengyong， et al. On evolutionary spectral clustering ［J］. ACM Trans on Knowledge Discovery from Data， 2009， 3（4）： 1-30.

［19］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.

［20］Folino F， Pizzuti C. An evolutionary multiobjective approach for community discovery in dynamic networks ［J］. IEEE Trans on Know-ledge amp; Data Engineering， 2014， 26（8）： 1838-1852.

［21］Yu Wei， Wang Wenjun， Jiao Pengfei， et al. Evolutionary clustering via graph regularized nonnegative matrix factorization for exploring temporal networks ［J］. Knowledge-Based Systems， 2019， 167： 1-10.

［22］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.

［23］Ma Xiaoke， Zhang Benhui， Ma Changzhou， et al. Co-regularized nonnegative matrix factorization for evolving community detection in dynamic networks［J］. Information Sciences， 2020， 528： 265-279.

［24］Wang Shuaihui， Li Guopeng， Hu Guyu， et al. Community detection in dynamic networks using constraint non-negative matrix factorization ［J］. Intelligent Data Analysis， 2020， 24（1）： 119-139.

［25］Li Dongyuan， Zhong Xiaoxiong， Dou Zengfa， et al. Detecting dyna-mic community by fusing network embedding and nonnegative matrix factorization ［J］. Knowledge-Based Systems， 2021， 221： 106961.

［26］Wang Zhen， Wang Chunyu， Li Xianghua， et al. Evolutionary Markov dynamics for network community detection ［J］. IEEE Trans on Knowledge and Data Engineering， 2022， 34（3）： 1206-1220.

［27］Kim M S， Han Jiawei. A particle-and-density based evolutionary clustering method for dynamic networks ［J］. Proceedings of the VLDB Endowment， 2009， 2（1）： 622-633.

［28］Jiao Pengfei， Yu Wei， Wang Wenjun， et al. Exploring temporal community structure and constant evolutionary pattern hiding in dynamic networks［J］. Neurocomputing， 2018， 314： 224-233.

［29］Jiao Pengfei， Lyu Haodong， Li Xiaoming， et al. Temporal community detection based on symmetric nonnegative matrix factorization ［J］. International Journal of Modern Physics B， 2017， 31（13）： 1750102.

［30］Márquez R， Weber R. Dynamic community detection including node attributes ［J］. Expert Systems with Applications， 2023， 223： 119791.

［31］Lancichinetti A， Fortunato S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities ［J］. Physical Review E Statistical Nonlinear amp; Soft Matter Physics， 2009， 80（2）： 016118.