楊煜，段威威

基于譜聚類的社交網(wǎng)絡(luò)動態(tài)社區(qū)發(fā)現(xiàn)算法

楊煜*，段威威

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

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

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

0 引言

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

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

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

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

本文的主要工作如下：

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

2）針對確定動態(tài)社區(qū)數(shù)，考慮網(wǎng)絡(luò)社區(qū)的歷史時間片拓?fù)浣Y(jié)構(gòu)特征，將當(dāng)前時間片的社區(qū)拓?fù)浣Y(jié)構(gòu)狀態(tài)信息和它的歷史時間片的拓?fù)浣Y(jié)構(gòu)狀態(tài)信息進(jìn)行譜聚類。根據(jù)事件演化相似度矩陣確定動態(tài)社區(qū)數(shù)，分析和預(yù)測時間片上社區(qū)事件的演化結(jié)果。

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

1 相關(guān)工作

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

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

1.1　相似度的計算方法

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

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

1.2　譜映射和模糊C-均值

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

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

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

圖1　CollegeMsg原始數(shù)據(jù)集的可視化結(jié)構(gòu)

圖2為不同時間片上動態(tài)社區(qū)結(jié)構(gòu)發(fā)現(xiàn)的結(jié)構(gòu)演變，SC-DCDA的社區(qū)結(jié)構(gòu)演變基于當(dāng)前社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)狀態(tài)信息和前一相鄰時間片拓?fù)浣Y(jié)構(gòu)狀態(tài)信息。

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

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

2 動態(tài)社交網(wǎng)絡(luò)結(jié)構(gòu)和演化

2.1　社區(qū)結(jié)構(gòu)相關(guān)定義

社區(qū)結(jié)構(gòu)是自底向上分析復(fù)雜社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的重要分析方法，本文為便于闡述基于譜聚類的社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法，將社區(qū)結(jié)構(gòu)定義如下。

2.2　動態(tài)社區(qū)結(jié)構(gòu)演化

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

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

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

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

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

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

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

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

第三步 根據(jù)第2章動態(tài)社區(qū)結(jié)構(gòu)事件演化，基于譜聚類算法求解當(dāng)前網(wǎng)絡(luò)和歷史網(wǎng)絡(luò)特征的社區(qū)數(shù)和結(jié)構(gòu)。

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

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

end for

end if

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

4 實驗與結(jié)果分析

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

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

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

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

4.2　性能評價指標(biāo)

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

4）Davies-Bouldin指數(shù)（Davies-Bouldin Index， DBI）［21］。聚類算法聚類質(zhì)量的評估指標(biāo)，聚類內(nèi)距離之和與聚類間距離之比，比值越小，聚類效果越好。

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

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

4.4　實驗結(jié)果與分析

不同的社區(qū)發(fā)現(xiàn)算法會產(chǎn)生不同的社區(qū)分布和運行時間，實驗中使用的數(shù)據(jù)集時間片來自表1數(shù)據(jù)集的手動分片，保證相鄰時間片社區(qū)結(jié)構(gòu)演化的相似度，當(dāng)前時間片的分片時間跨度包含上一相鄰時間片的時間跨度。

將數(shù)據(jù)集劃分為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條數(shù)據(jù)集記錄，依此類推，時間片跨度為當(dāng)?shù)貢r間2004年4月15日22：56至2004年5月4日14：24。

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

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

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

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

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

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

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

圖5　SC-DCDA與典型算法的輪廓系數(shù)指標(biāo)對比

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

圖6　SC-DCDA與典型算法的CH指標(biāo)對比

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

5 結(jié)語

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

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

[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)科研網(wǎng)絡(luò)的社區(qū)檢測算法［J］. 計算機科學(xué)， 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é)點不對稱轉(zhuǎn)移概率的網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法［J］. 軟件學(xué)報， 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] 周銳，王桂娟，鄧皓天，等. 復(fù)雜網(wǎng)絡(luò)聚類特征層次布局算法［J］. 計算機應(yīng)用研究， 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；

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

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

TP181

A

2023?01?10。