楊煜，段威威

基于譜聚類的社交網絡動態(tài)社區(qū)發(fā)現算法

楊煜*，段威威

（電子科技大學 計算機科學與工程學院，成都 611731）（ ? 通信作者電子郵箱yangyu2022@std.uestc.edu.cn）

動態(tài)社區(qū)發(fā)現研究是社交網絡分析（SNA）的重要研究領域。隨著節(jié)點加入或離開社交網絡，節(jié)點間的關系也隨之建立或消失，進而影響著社區(qū)結構的變化。針對社交網絡靜態(tài)社區(qū)發(fā)現算法缺少必要的社區(qū)節(jié)點歷史信息而導致的網絡結構分析、聚類信息不足和計算開銷過大的問題，基于社區(qū)網絡演化事件的劃分并根據主要社區(qū)事件的分析，提出一種基于譜聚類的動態(tài)社區(qū)發(fā)現算法（SC-DCDA）。首先，根據實驗觀察使用譜映射的方法將高維數據降維，并采用改進的模糊C-均值聚類（FCM）算法確定動態(tài)社交網絡中的節(jié)點與待發(fā)現社區(qū)的關聯度；其次，根據演化相似度矩陣分析社區(qū)結構。通過使用真實網絡數據集以及模塊度得分、輪廓系數等社區(qū)發(fā)現算法衡量指標，評估所提算法的效果。實驗結果表明，SC-DCDA的計算開銷相較于傳統(tǒng)譜聚類降低了8.37%，在所有數據集上的平均模塊度得分是0.49，其他衡量指標的定性分析結果也較好，驗證了所提算法在信息交互、聚類效果和精確度上表現較好。

社交網絡分析；動態(tài)社區(qū)發(fā)現算法；模糊C-均值聚類；演化相似度矩陣

0 引言

社區(qū)是社交網絡中拓撲結構的重要研究對象，社區(qū)發(fā)現算法是社交網絡分析（Social Network Analysis， SNA）的主要研究領域，研究社區(qū)發(fā)現算法有助于研究者深入學習社交網絡的復雜拓撲結構及其社區(qū)行為特征。傳統(tǒng)社交網絡社區(qū)發(fā)現算法的研究對象多為靜態(tài)社區(qū)，然而實際的社交網絡都是隨時間的變化而不斷演化，導致多數靜態(tài)社區(qū)發(fā)現建模研究難以識別同一社區(qū)中節(jié)點隨時間變化所具有的相同或相似的屬性及其行為，更難以識別不同社區(qū)中的節(jié)點隨時間變化所具有的潛在信息，無法有效提取動態(tài)社區(qū)的特征，分析動態(tài)網絡結構、網絡特性、網絡信息傳播規(guī)律和優(yōu)化網絡應用不準確。

動態(tài)社區(qū)由一組連接緊密、隨時間變化的節(jié)點組成，并且社區(qū)內部節(jié)點在此刻比社區(qū)外部節(jié)點連接更緊密。社交網絡動態(tài)社區(qū)發(fā)現是在隨時間變化的復雜網絡系統(tǒng)中，發(fā)現連接緊密的社區(qū)結構。研究動態(tài)社區(qū)的網絡建模、行為分析和社區(qū)發(fā)現算法能有效揭示社交網絡中節(jié)點和連接特征、節(jié)點和連接社區(qū)的共性規(guī)律，有助于推動社區(qū)發(fā)現算法相關應用。它的研究意義是探究復雜網絡結構及社區(qū)事件演化的過程，為社交網絡的應用提供支撐。

目前，動態(tài)社交網絡社區(qū)發(fā)現算法面臨的問題是動態(tài)網絡模型的構建?，F有的動態(tài)模型構建方法通常采用融合非隱匿平滑框架的策略［1-2］，該策略可以量化社區(qū)時間片間的相似性，通過拓展靜態(tài)社區(qū)發(fā)現的方法，借助網絡拓撲結構的連通性和模塊度函數發(fā)現動態(tài)社區(qū)的結構；在概率模型中，使用貝葉斯模型根據擴展隨機塊模型計算演化的動態(tài)社區(qū)結構。在模型構建中，不同社區(qū)之間動態(tài)交互結構通常是稀疏關系，導致它們的相似度矩陣也是稀疏相似度矩陣，影響譜聚類算法的收斂。同時，動態(tài)模型中社區(qū)數隨著相鄰時間片的節(jié)點交互而動態(tài)演化，演化決定著社區(qū)的合并和分裂、生長和收縮、產生和消失及持續(xù)保持，致使在設計算法中社區(qū)數難以確定。綜上，現階段稀疏相似度矩陣對譜聚類算法和確定相鄰時間片動態(tài)社區(qū)數的相關研究較少。

針對社交網絡動態(tài)社區(qū)建模中存在的上述問題，提出基于譜聚類的動態(tài)社區(qū)發(fā)現算法（Spectral Clustering based Dynamic Community Discovery Algorithm， SC-DCDA）。

本文的主要工作如下：

1）針對稀疏矩陣的影響，改進譜聚類算法?；谧V映射優(yōu)化方法提取的社交網絡拓撲結構的特征值，使用模糊C-均值聚類（Fuzzy C-Means clustering， FCM）算法確定動態(tài)社交網絡的節(jié)點與待發(fā)現社區(qū)的關聯程度，即計算數據集數據點間的相似度，通過譜映射優(yōu)化將網絡中節(jié)點轉化成譜聚類算法的近似相似度度量矩陣，降低稀疏矩陣對譜聚類算法的影響，減少動態(tài)譜聚類計算的開銷。

2）針對確定動態(tài)社區(qū)數，考慮網絡社區(qū)的歷史時間片拓撲結構特征，將當前時間片的社區(qū)拓撲結構狀態(tài)信息和它的歷史時間片的拓撲結構狀態(tài)信息進行譜聚類。根據事件演化相似度矩陣確定動態(tài)社區(qū)數，分析和預測時間片上社區(qū)事件的演化結果。

3）在真實的CollegeMsg［1］、email-Eu-core-temporal［2］、sx-askubuntu［2］和wiki-talk-temporal［2］動態(tài)網絡數據集的時間片上，對比SC-DCDA和典型算法的計算開銷和性能，實驗結果驗證了所提算法在信息交互、聚類效果和精確度上均表現較好。

1 相關工作

本文重點關注社交網絡動態(tài)社區(qū)結構演化規(guī)律和社區(qū)發(fā)現算法。關于動態(tài)社交網絡社區(qū)結構發(fā)現算法的研究，Li等［3］歸納出時間權衡社區(qū)發(fā)現方法和跨時間片社區(qū)發(fā)現方法，其中：時間權衡社區(qū)發(fā)現方法的思想是社區(qū)結構發(fā)現的更新依賴于當前社交網絡狀態(tài)和前一時間片網絡結構信息，該方法較接近現實社交網絡場景；跨時間片社區(qū)發(fā)現方法的思想是在不同時間片上社區(qū)結構發(fā)現更新依賴于過去、當前社交網絡狀態(tài)中所有可獲得到的有效信息，該方法認為對社交網絡的生命周期進行時間片劃分，使得相鄰時間片社區(qū)結構關系具有隨機性和不確定性。動態(tài)社區(qū)結構演化和社區(qū)發(fā)現研究的目標是識別具有較高相似度節(jié)點及較高關聯度的社區(qū)。

由于社交網絡動態(tài)社區(qū)的開放性、動態(tài)性和復雜性，發(fā)現算法主要關注社區(qū)劃分結果的精確度、事件動態(tài)演化、動態(tài)社區(qū)發(fā)現算法和社區(qū)發(fā)現算法質量評價標準等方面：Yin等［4］提出改進的粒子算法，對初始聚類結果調優(yōu)，防止聚類局部最優(yōu)化，提高聚類的精確度；Wang等［5］提出基于馬爾可夫鏈的動態(tài)過程增加社區(qū)檢測算法動態(tài)過程的轉移概率，提高社區(qū)檢測的能力；Besharatnia等［6］提出標簽傳播的優(yōu)化方法，提高動態(tài)社區(qū)檢測的質量和效率；Li等［7］提出局部譜子圖（LOcal SPectral clustering， LOSP）的局部重疊社區(qū)發(fā)現方法；Wharrie等［8］、Mucha等［9］和Palla等［10］提出社區(qū)發(fā)現算法社區(qū)質量評價標準，社區(qū)質量評價標準主要包括核函數、模塊度和進化聚類社區(qū)質量評價方法，分別用于評價動態(tài)社交網絡社區(qū)檢測近似度變化、相鄰時間片社區(qū)結構變化和檢測社區(qū)質量差異度。

1.1　相似度的計算方法

相似度是社交網絡社區(qū)發(fā)現中建模節(jié)點屬性和行為的相似程度的衡量指標，如邊介數（Betweeness）衡量指標［11］。邊介數指網絡中任意節(jié)點之間通過此邊的最多路徑數，并且介數高的邊比介數低的邊更可能是社區(qū)間的邊。不同社區(qū)中節(jié)點之間的最短路徑都經過社區(qū)間的這條邊，這為社區(qū)發(fā)現提供相似度計算的依據。

通過相似度分析可以研究社交網絡社區(qū)節(jié)點特征值，除常用的密度、距離、聚集系數等方法之外，現有研究使用的相似度計算方法逐漸向綜合性的相似度計算方法發(fā)展。Li等［12］提出基于節(jié)點特征值、關系密度和拓撲結構的多相似度計算方法；Qin等［13］提出多相似度譜方法改進已有進化聚類相似度計算準確度，該方法更好地用于檢測動態(tài)網絡的社區(qū)結構；Chen等［14］使用微分方程模擬有向網絡中節(jié)點的連續(xù)變化狀態(tài)，提出基于重構鄰居集（節(jié)點基于自身狀態(tài)和正向連接鄰居集的平均狀態(tài)，以及社區(qū)間正向連接相似度關系更新狀態(tài)）的進化譜算法，較好地檢測動態(tài)網絡的社區(qū)結構；Olszewski等［15］提出在輸入輸出數據空間中改進數據樣本鄰居計算方法，該方法基于數據的離散性，自適應計算數據寬度，先輸入數據聚類，再計算聚類內差異值，最后依據此值決定數據樣本鄰居寬度值進行社區(qū)分割；Guidi等［16］定義鄰接區(qū)域結構，節(jié)點間拓撲結構相似度分析基于相對熵（節(jié)點間關于鄰接區(qū)域信息分布的相似度度量）計算節(jié)點間的相似度。綜上，基于距離的相似度計算將忽略節(jié)點攜帶信息的相似度，相較于距離計算的社區(qū)發(fā)現更重要。

1.2　譜映射和模糊C-均值

譜映射建立矩陣特征向量特征值與多項式的函數關系，即在社交網絡不同時間片上使用譜映射方法提取網絡的拓撲結構的特征值，使用FCM根據提取的特征值發(fā)現社區(qū)。與C-means相比，FCM的劃分引入了彈性空間。與-means相比，FCM的目標函數中引入了隸屬度矩陣，指明節(jié)點屬于待劃分社區(qū)的隸屬程度，并且-means理論上只是確?？焖偈諗康骄植孔顑?yōu)解（因為聚類內節(jié)點對初始聚類中心點的選擇具有依賴性），即-means最優(yōu)解的求解要求對網絡劃分所有可能的社區(qū)。本文使用FCM，通過算法迭代后，根據終止迭代條件將節(jié)點劃分到隸屬度較高的社區(qū)。

1.3　靜態(tài)到動態(tài)社區(qū)發(fā)現算法

如圖1所示，CollegeMsg原始數據集（包含1 899個節(jié)點和5 983條邊）來自https：//snap.stanford.edu/data/CollegeMsg.html，實驗中根據事件演化人為劃分8 000、16 000和24 000條數據記錄。圖1（c）是整個CollegeMsg數據集193 d的動態(tài)可視化結構，社交網絡靜態(tài)社區(qū)結構發(fā)現到動態(tài)社區(qū)結構發(fā)現隨時間推移的過程。

圖1　CollegeMsg原始數據集的可視化結構

圖2為不同時間片上動態(tài)社區(qū)結構發(fā)現的結構演變，SC-DCDA的社區(qū)結構演變基于當前社交網絡拓撲結構狀態(tài)信息和前一相鄰時間片拓撲結構狀態(tài)信息。

圖2　動態(tài)社區(qū)結構的時間依賴圖

靜態(tài)社區(qū)發(fā)現算法較難識別同一社區(qū)中的節(jié)點隨時間片遷移所具有的相同或相似屬性、行為，更難識別不同社區(qū)節(jié)點隨時間片遷移所具有的潛在信息。在社區(qū)發(fā)現算法中引入時間片概念劃分結構演化過程事件，建立演化模型過渡到動態(tài)社區(qū)發(fā)現算法，更精確地分析網絡結構、特性和信息傳播規(guī)律，進而將時間片上的局部最優(yōu)社區(qū)結構向整個網絡演化的全局最優(yōu)社區(qū)結構求解。

2 動態(tài)社交網絡結構和演化

2.1　社區(qū)結構相關定義

社區(qū)結構是自底向上分析復雜社交網絡拓撲結構的重要分析方法，本文為便于闡述基于譜聚類的社交網絡社區(qū)發(fā)現算法，將社區(qū)結構定義如下。

2.2　動態(tài)社區(qū)結構演化

鑒于社交網絡的復雜性及其網絡規(guī)模難以量化，為便于研究基于譜聚類的社交網絡社區(qū)發(fā)現算法和人為劃分時間片，本文引入動態(tài)社區(qū)結構演化。

社區(qū)結構發(fā)現以節(jié)點具有相同或相似的屬性、行為及其連接關系建模。隨著時間的不斷變化，根據新的節(jié)點及其連接關系在網絡中的出現，以及原有節(jié)點及其連接關系的不斷變化，將社交網絡社區(qū)結構的演化劃分為出生事件、死亡事件、生長事件、分裂事件、合并事件、持續(xù)事件和收縮事件等節(jié)點重組的演化過程事件。結合Guidi等［16］定義的相似度矩陣（式（1））和Mohammadmosaferi等［17］引入事件的部分進化。

針對動態(tài)社區(qū)發(fā)現的理論基礎工作，演化相似度矩陣定義如下。

此外，過往研究還將事件細化為：持續(xù)事件（Continue Event）、收縮事件（Contraction Event）和生長事件（Growth Event）。在演化過程事件中，出生事件和死亡事件對社區(qū)結構新增和刪除的影響最大，因此基于譜聚類的社交網絡社區(qū)發(fā)現算法重點關注這兩類事件，難點是關注分裂事件和合并事件。

基于譜聚類的社交網絡社區(qū)發(fā)現算法整體思想為：將時間上有限的動態(tài)社區(qū)網絡結構人為地劃分成具體的時間片，再使用靜態(tài)譜聚類或其他對比算法處理網絡相鄰連續(xù)時間片上的社區(qū)結構，分析和預測時間片上社區(qū)事件演化結果，得到相鄰連續(xù)時間片上（當前時間片和前一時間片）譜聚類動態(tài)社區(qū)。

3 基于譜聚類的動態(tài)社區(qū)發(fā)現算法

基于譜圖理論的聚類算法是社交網絡動態(tài)社區(qū)發(fā)現的研究方法之一，社交網絡社區(qū)發(fā)現聚類算法是將聚類問題轉化為圖最優(yōu)劃分問題，原因是譜聚類算法計算社交網絡的最小割，與相似度矩陣和拉普拉斯矩陣（Laplacian matrix）特征值一致。本文算法基于時間權衡社區(qū)發(fā)現方法的啟發(fā)，提出基于FCM的譜聚類算法計算動態(tài)社區(qū)。

為了確定動態(tài)建模中社區(qū)數，考慮在每一個時間片上發(fā)現當前網絡和歷史網絡特征的社區(qū)數和結構，克服靜態(tài)社區(qū)發(fā)現算法僅考慮歷史網絡特征的社區(qū)數和結構的缺點。SC-DCDA的流程分3個步驟。

第三步 根據第2章動態(tài)社區(qū)結構事件演化，基于譜聚類算法求解當前網絡和歷史網絡特征的社區(qū)數和結構。

SC-DCDA具體的偽代碼如算法1所示。

算法1 基于譜聚類的動態(tài)社區(qū)發(fā)現算法。

end for

end if

動態(tài)社區(qū)結構發(fā)現按照時間片序列，對每個時間片上的網絡運用譜映射優(yōu)化，將網絡中節(jié)點轉化成譜聚類算法的近似相似度度量矩陣，使用Minkowski distance公式作為相似度的簡化度量；應用拉普拉斯特征處理，將特征數據轉換成適合SC-DCDA的特征矩陣；基于事件演化模型，模擬動態(tài)社交網絡社區(qū)結構算法計算聚類結果，SC-DCDA記錄社區(qū)結構演化事件。

4 實驗與結果分析

主要從獲取真實動態(tài)社交網絡數據集、數據處理、特征處理、FCM譜聚類、動態(tài)社區(qū)演化模型訓練、算法調優(yōu)、算法預測值輸出和算法性能評估方面驗證本文算法的準確度和有效性。

4.1　數據集

實驗在數據集CollegeMsg［1］、email-Eu-core-temporal［2］、sx-askubuntu［2］和wiki-talk-temporal［2］的不同時間片上進行，消融實驗、性能分析實驗和對比實驗中所使用的動態(tài)網絡真實數據集均來自網絡，數據集的統(tǒng)計信息如表1所示。特別的，數據集節(jié)點和鏈接之間關系的結構和屬性需要轉換成Python語言支持的.gml數據類型和存儲。

表1　數據集統(tǒng)計信息

4.2　性能評價指標

3）CH（Calinski-Harabasz）指標［21］。聚類模型質量的評價指標，即相同類別相似性較高，不同類別相似性較低。值越高，聚類模型的質量越好。

4）Davies-Bouldin指數（Davies-Bouldin Index， DBI）［21］。聚類算法聚類質量的評估指標，聚類內距離之和與聚類間距離之比，比值越小，聚類效果越好。

4.3　實驗環(huán)境設置

算法實現使用Python語言，運行時間單位為s。處理器信息為配備Radeon顯卡的AMD 銳龍 7 5800H，主頻為3.20 GHz，內存容量是16.0 GB。

4.4　實驗結果與分析

不同的社區(qū)發(fā)現算法會產生不同的社區(qū)分布和運行時間，實驗中使用的數據集時間片來自表1數據集的手動分片，保證相鄰時間片社區(qū)結構演化的相似度，當前時間片的分片時間跨度包含上一相鄰時間片的時間跨度。

將數據集劃分為3個時間跨度的時間片，即CollegeMsg 0.8、CollegeMsg 1.6、CollegeMsg 2.4，email-Eu-core-temporal 1、email-Eu-core-temporal 6、email-Eu-core-temporal 12，sx-askubuntu 2.5、sx-askubuntu 5、sx-askubuntu 7.5，wiki-talk-temporal 2.5、wiki-talk-temporal 5和wiki-talk-temporal 7.5。其中0.8指8 000條數據集記錄，依此類推，時間片跨度為當地時間2004年4月15日22：56至2004年5月4日14：24。

如表2所示，SC-DCDA基于社區(qū)事件演化相似度矩陣的改進的FCM譜聚類，在消融實驗中，SC-DCDA的計算稀疏矩陣的時間開銷相較于傳統(tǒng)譜聚類降低了8.37%，主要原因是SC-DCDA采用時間權衡社區(qū)發(fā)現方法，社區(qū)結構發(fā)現的更新不僅考慮當前社交網絡狀態(tài)，也考慮前一時間片網絡結構信息，該時間片上沒有演化的節(jié)點聚類的時間開銷則降低。

在與典型算法對比實驗中，對比算法分別選擇基于遍歷策略求最大模塊度的Louvain算法［22-23］、基于最小熵原理求最優(yōu)解的InfoMap算法［24］、基于貪心策略的最大團合并的Fast Newman（FN）算法［24］和基于邊介數（任意兩節(jié)點間通過此邊的最短路徑數）的Girvan-Newman（GN）算法［22-23］。從圖3可知，SC-DCDA在各個數據集上隨著時間片的時間跨度不斷增加，但相較于其他對比算法，增長較緩慢，表明SC-DCDA的運行時間的增長率沒有顯著增長，進而說明它在不同時間片上具有較好的可擴展性。

使用無標簽的CollegeMsg、email-Eu-core-temporal、sx-askubuntu和wiki-talk-temporal數據集，分別在3個時間片上與Louvain算法、InfoMap算法、FN算法和GN算法對比模塊度得分，結果如圖4所示。在真實數據集上，模塊度得分在0.5～0.7的聚類算法效果較好。SC-DCDA在email-Eu-core-temporal數據集時間片的平均模塊度得分是0.60，在上述數據集平均模塊度得分是0.49，具有較好的聚類效果。

表2　SC-DCDA與譜聚類在動態(tài)數據集上的計算開銷對比

圖3　SC-DCDA與典型算法在動態(tài)數據集上的運行時間對比

使用輪廓系數評價社區(qū)發(fā)現結果的準確性。實驗使用上述無標簽數據集分別在3個時間片上與典型算法的輪廓系數對比：該評價指標越接近1，說明樣本聚類正確性越高；越接近-1，說明聚類的錯誤概率越高。從圖5可以看出，相較于其他算法，SC-DCDA聚類的輪廓系數均為正數，社區(qū)發(fā)現的正確性較好，并且無錯誤聚類的指標概率。

圖4　SC-DCDA與典型算法的模塊度得分對比

圖5　SC-DCDA與典型算法的輪廓系數指標對比

此外，使用CH和DBI指標評價社區(qū)發(fā)現結果的質量。從圖6可以看出，GN算法和SC-DCDA的CH平均值均高于其他對比算法，模型的聚類效果較好。從圖7可以看出，SC-DCDA的DBI平均值較小，說明它取得了較好的社區(qū)發(fā)現結果。實驗中根據DBI值不斷優(yōu)化FCM聚類，防止產生局部最優(yōu)解。

圖6　SC-DCDA與典型算法的CH指標對比

圖7　SC-DCDA與典型算法的DBI對比

5 結語

本文基于動態(tài)社區(qū)結構演化，研究社交網絡動態(tài)社區(qū)結構演化規(guī)律和動態(tài)數據集隨時間變化的社區(qū)發(fā)現規(guī)律，側重于演化事件中的出生事件、死亡事件、分裂事件和合并事件。采用真實數據集實驗驗證SC-DCDA的信息交互、聚類效果和準確度，結果顯示SC-DCDA在動態(tài)數據集上的模塊度得分、輪廓系數、CH指標和DBI較好。SC-DCDA為動態(tài)性、多樣性和復雜性社交網絡演化和結構分析提供研究方法和一定的參考價值；但該模型的抽象建模依賴于具體的領域場景和相似度的優(yōu)化，是目前研究領域的局限和不足，也是下一步研究的方向。

動態(tài)社區(qū)發(fā)現只考慮社交網絡的結構，忽略節(jié)點的屬性特征，但節(jié)點屬性對精準的社區(qū)發(fā)現更具有價值。未來將考慮節(jié)點在不同領域場景、不同時間片下屬性的相似性，挖掘更多社區(qū)信息提高社區(qū)發(fā)現的精確度。此外，動態(tài)社區(qū)事件演化預測方面也需要進一步研究，主要體現在研究事件狀態(tài)隨時間片狀態(tài)的遷移追蹤的精確度：一方面需改進計算特征值和特征向量的算法，提高計算的效率；另一方面可以借助卷積神經網絡歷史信息前一時間片的信息和當前時間片信息去計算當前狀態(tài)，模型上可借助注意力機制Attention做并行，觀測時間片狀態(tài)的遷移和研究事件收斂的關聯度。

[1] PANZARASA P， OPSAHL T， CARLEY K M. Patterns and dynamics of users' behavior and interaction： network analysis of an online community［J］. Journal of the American Society for Information Science and Technology， 2009， 60（5）： 911-932.

[2] PARANJAPE A， BENSON A R， LESKOVEC J. Motifs in temporal networks［C］// Proceedings of the 10th ACM International Conference on Web Search and Data Mining. New York： ACM， 2017： 601-610.

[3] LI W， ZHONG K， WANG J， et al. A dynamic algorithm based on cohesive entropy for influence maximization in social networks［J］. Expert Systems with Applications， 2021， 169： No.114207.

[4] YIN Y， ZHAO Y， LI H， et al. Multi-objective evolutionary clustering for large-scale dynamic community detection［J］. Information Sciences， 2021， 549： 269-287.

[5] WANG Z， WANG C， LI X， et al. Evolutionary Markov dynamics for network community detection［J］. IEEE Transactions on Knowledge and Data Engineering， 2022， 34（3）： 1206-1220.

[6] BESHARATNIA F， TALEBPOUR A， ALIAKBARY S. An improved grey wolves optimization algorithm for dynamic community detection and data clustering［J］. Applied Artificial Intelligence， 2022， 36（1）： No.2012000.

[7] LI Y， HE K， BINDEL D， et al. Overlapping community detection via local spectral clustering［EB/OL］. （2015-09-26） ［2022-09-10］.https：//arxiv.org/pdf/1509.07996.pdf.

[8] WHARRIE S， AZIZI L， ALTMANN E G. Micro-， meso-， macroscales： the effect of triangles on communities in networks［J］. Physical Review E， 2019， 100（2）： No.022315.

[9] MUCHA P J， RICHARDSON T， MACON K， et al. Community structure in time-dependent， multiscale， and multiplex networks［J］. Science， 2010， 328（5980）： 876-878.

[10] PALLA G， BARABáSI A L， VICSEK T. Quantifying social group evolution［J］. Nature， 2007， 446（7136）： 664-667.

[11] KANAVOS A， VOUTOS Y， GRIVOKOSTOPOULOU F， et al. Evaluating methods for efficient community detection in social networks［J］. Information， 2022， 13（5）： No.209.

[12] LI N， PEN M， JIANG W， et al. A community detection algorithm based on multi-similarity method［J］. Cluster Computing， 2019， 22（S2）： 2865-2874.

[13] QIN X， DAI W， JIAO P， et al. A multi-similarity spectral clustering method for community detection in dynamic networks［J］. Scientific Reports， 2016， 6： No.31454.

[14] CHEN J， WANG H， WANG L， et al. A dynamic evolutionary clustering perspective： community detection in signed networks by reconstructing neighbor sets［J］. Physica A： Statistical Mechanics and its Applications， 2016， 447： 482-492.

[15] OLSZEWSKI D. A clustering-based adaptive neighborhood retrieval visualizer［J］. Neural Networks， 2021， 140： 247-260.

[16] GUIDI B， MICHIENZI A， ROSSETTI G. Towards the dynamic community discovery in decentralized online social networks［J］ Grid Computing， 2019， 17（1）： 23-44.

[17] MOHAMMADMOSAFERI K K， NADERI H. Evolution of communities in dynamic social networks： an efficient map-based approach［J］. Expert Systems with Applications， 2020， 147： No.113221.

[18] IZAKIAN H， ABRAHAM A. Fuzzy C-means and fuzzy swarm for fuzzy clustering problem［J］. Expert Systems with Applications， 2011， 38（3）：1835-1838.

[19] BOUDEBZA S. An approach for detecting dynamic communities in social networks［D］. Jijel： Université Mohammed Seddik BenYahia， 2022： 1-165.

[20] TAKAFFOLI M， SANGI F， FAGNAN J， et al. Community evolution mining in dynamic social networks［J］. Procedia — Social and Behavioral Sciences， 2011， 22：49-58.

[21] ?KRLJ B， KRALJ J， LAVRA? N. Embedding-based Silhouette community detection［J］. Machine Learning， 2020， 109（11）： 2161-2193.

[22] 蒲實，趙衛(wèi)東. 一種面向動態(tài)科研網絡的社區(qū)檢測算法［J］. 計算機科學， 2022， 49（1）：89-94.（PU S， ZHAO W D. Community detection algorithm for dynamic research network［J］. Computer Science， 2022， 49（1）：89-94.）

[23] 許平華，胡文斌，邱振宇，等. 節(jié)點不對稱轉移概率的網絡社區(qū)發(fā)現算法［J］. 軟件學報， 2019， 30（12）：3829-3845.（XU P H， HU W B， QIU Z Y， et al. Community detection algorithm based on asymmetric transition probability of nodes［J］. Journal of Software， 2019， 30（12）： 3829-3845.）

[24] 周銳，王桂娟，鄧皓天，等. 復雜網絡聚類特征層次布局算法［J］. 計算機應用研究， 2022， 39（2）：479-484.（ZHOU R， WANG G J， DENG H T， et al. Complex network clustering feature multi-level layout algorithm［J］. Application Research of Computers， 2022， 39（2）： 479-484.）

Spectral clustering based dynamic community discovery algorithm in social network

YANG Yu*， DUAN Weiwei

（，，611731，）

Dynamic community discovery is an important research area in Social Network Analysis （SNA）. As nodes joining or leaving social networks， the relationships between nodes establish or terminate， which affects community structure changes. The discovery algorithms of static communities in social networks lack of the essential historical information of community nodes， resulting in the insufficient network structure analysis as well as clustering information and the high computational cost. Aiming at these problems， based on the division of the community network evolution events， according to the analysis of the major community events， a Spectral Clustering based Dynamic Community Discovery Algorithm （SC-DCDA） was proposed. Firstly， according to the experimental observation， the dimensionality of high-dimensional data was reduced by using the method of spectral mapping. At the same time， the improved Fuzzy C-Means clustering （FCM） algorithm was adopted to determine the correlation between the nodes in the dynamic social network and the communities to be discovered. Secondly， the community structures were analyzed according to the evolutionary similarity matrix. Finally， the real network datasets and community discovery algorithm indicators， such as modularity score and Silhouette coefficient， were used to evaluate the effects of the proposed algorithm. Experimental results show that the computational cost of SC-DCDA is reduced by 8.37% compared with traditional spectral clustering， the average modularity score of the algorithm on all datasets is 0.49， and the qualitative analysis results of other algorithm metrics are also good， indicating that the proposed algorithm performs well in information interaction， clustering effect， and accuracy.

Social Network Analysis (SNA); dynamic community discovery algorithm; Fuzzy C-Means clustering (FCM); evolutionary similarity matrix

This work is partially supported by Science Research Fund Project of Department of Education of Yunnan Province （2020J1110）.

YANG Yu， born in 1988， Ph. D. candidate. His research interests include community discovery， network and system security.

DUAN Weiwei， born in 1998， M. S. candidate. His research interests include machine learning， deep learning， community detection.

1001-9081（2023）10-3129-07

10.11772/j.issn.1001-9081.2022101517

2022?10?14；

2023?01?03；

云南省教育廳科學研究基金資助項目（2020J1110）。

楊煜（1988—），男，安徽太和人，博士研究生，主要研究方向：社區(qū)發(fā)現、網絡與系統(tǒng)安全； 段威威（1998—），男，安徽界首人，碩士研究生，主要研究方向：機器學習、深度學習、社區(qū)檢測。

TP181

A

2023?01?10。