付立冬， 馬小科， 聶靖靖

(1. 西安科技大學(xué) 計算機學(xué)院，陜西 西安 710054;2. 西安電子科技大學(xué) 計算機學(xué)院，陜西 西安 710071)

現(xiàn)實世界中的許多復(fù)雜系統(tǒng)可用網(wǎng)絡(luò)來描述，復(fù)雜網(wǎng)絡(luò)中的節(jié)點表示系統(tǒng)中的實體，節(jié)點之間的連線表示實體間的相互作用關(guān)系．在社會網(wǎng)絡(luò)[1]、信息網(wǎng)絡(luò)[2]、生物網(wǎng)絡(luò)[3-4]等復(fù)雜網(wǎng)絡(luò)中存在著社團結(jié)構(gòu)．例如，在科學(xué)家合作網(wǎng)絡(luò)中，社團結(jié)構(gòu)表示有著相同或相似研究興趣的科學(xué)家群體; 在Web頁面網(wǎng)絡(luò)中，社團結(jié)構(gòu)表示有著相似或相近主題的一組頁面; 在蛋白質(zhì)相互作用網(wǎng)絡(luò)中，社團結(jié)構(gòu)表示提供某種功能的蛋白質(zhì)集合，對分析生物機理及進程有著非凡的意義．這些社團結(jié)構(gòu)為研究整個復(fù)雜系統(tǒng)的結(jié)構(gòu)和功能提供了客觀依據(jù)．

目前，有許多算法基于模塊評估函數(shù)Q及模塊密度函數(shù)D優(yōu)化以檢測靜態(tài)復(fù)雜網(wǎng)絡(luò)中的社團結(jié)構(gòu)[5-6]．但是，現(xiàn)實世界的網(wǎng)絡(luò)不總是靜態(tài)的，而是處于動態(tài)進化中[7-9]．例如，在科學(xué)家合作網(wǎng)絡(luò)中，隨著時間推移，由于科學(xué)家的研究興趣和方向發(fā)生改變，相應(yīng)的社團結(jié)構(gòu)也會發(fā)生變化; 在疾病網(wǎng)絡(luò)中，由于癌細胞的遷移或分裂導(dǎo)致癌細胞組成社團結(jié)構(gòu)發(fā)生改變．在動態(tài)復(fù)雜網(wǎng)絡(luò)中，由于社團中節(jié)點的增加或移除而發(fā)生變化的社團稱為動態(tài)社團．因此，動態(tài)網(wǎng)絡(luò)中的社團結(jié)構(gòu)檢測更能揭示復(fù)雜網(wǎng)絡(luò)的特性、演變規(guī)律及發(fā)展趨勢．如何檢測動態(tài)網(wǎng)絡(luò)中的社團結(jié)構(gòu)已成為當(dāng)前的熱點和難點問題．有許多方法可檢測動態(tài)復(fù)雜網(wǎng)絡(luò)的社團結(jié)構(gòu)，其中進化方法成為運用廣泛的一種策略[6，10]．該策略在一種時間平滑框架下，在每個時間步上生成聚類．這個時間平滑框架假定在一段很短的時間間隔內(nèi)社團的改變不明顯，且最好的社團結(jié)構(gòu)應(yīng)當(dāng)通過同時考慮當(dāng)前時刻和前一時刻的社團結(jié)構(gòu)來獲得．

為有效地在動態(tài)網(wǎng)絡(luò)中檢測社團結(jié)構(gòu)，筆者將模塊函數(shù)Q及模塊密度函數(shù)D在時間平滑框架下進行譜分，以便能夠通過進化譜分方法檢測動態(tài)復(fù)雜網(wǎng)絡(luò)的社團結(jié)構(gòu)，并提出了用進化譜分方法檢測動態(tài)社團結(jié)構(gòu)的算法．

1　相關(guān)工作

1.1　符號定義

1.2　模塊函數(shù)與模塊密度函數(shù)

(1)

其中，L(Pct，Pct)表示t時刻社團i中連邊的數(shù)目，L(V，V)表示網(wǎng)絡(luò)Gt中邊的總數(shù)目．Q值越大，表示網(wǎng)絡(luò)中社團劃分越好．因此，對L(Pct，V)一個網(wǎng)絡(luò)，檢測社團問題可直接轉(zhuǎn)化為求函數(shù)Q值的最大優(yōu)化問題．

模塊密度函數(shù)D可定義為

(2)

1.3　進化方法

進化方法使用了一種時間平滑框架檢測動態(tài)網(wǎng)絡(luò)社團結(jié)構(gòu)．同其他類似的方法一樣，通過調(diào)節(jié)權(quán)重參數(shù)獲得兩個連續(xù)時間上最優(yōu)的目標(biāo)[11-12]．進化方法可表達成

C=λCS+(1-λ)CT,

(3)

其中，CS描述了在當(dāng)前時刻獲得的社團結(jié)構(gòu)是如何好，而CT描述了當(dāng)前時刻的社團結(jié)構(gòu)與前一時刻的社團結(jié)構(gòu)如何相似．λ是權(quán)重參數(shù)，取值在[0，1]之間．當(dāng)λ=0 時，獲得的社團結(jié)構(gòu)僅為前一時刻的社團結(jié)構(gòu)；當(dāng)λ=1 時，獲得的社團結(jié)構(gòu)僅為當(dāng)前時刻的社團結(jié)構(gòu)．

2　函數(shù)進化譜分方法

2.1　模塊Q函數(shù)進化譜分

首先在進化時間平滑框架下優(yōu)化模塊函數(shù)Q，檢測動態(tài)社團需要的整個成本為

CQ=λCSQ+(1-λ)CTQ=λQt|Xt+(1-λ)Qt-1|Xt,

(4)

其中，CSQ表示當(dāng)前時刻模塊性度量，CTQ表示歷史時刻模塊性度量，Qt-1|Xt表示社團Xt在Gt下的模塊密度值．

為解決CQ作為矩陣跡的優(yōu)化問題，首先將式(4)中Qt|Xt變?yōu)榫仃囒E的形式問題:

(5)

為了簡化，重寫Qt|Xt，有

其中，St為動態(tài)網(wǎng)絡(luò)t時刻的總邊數(shù)，可看成常數(shù)；dt∈Rn×1，其元素dit等于t時刻節(jié)點i的度．結(jié)果有

(7)

(8)

同理，式(4)中Qt-1|Xt作為矩陣跡的形式可描述為

(9)

將式(8)和式(9)代入式(4)中，有

(10)

因此，用Q函數(shù)檢測動態(tài)社團結(jié)構(gòu)進化譜分后的最大優(yōu)化問題可表達成

(11)

2.2　模塊密度D函數(shù)進化譜分

據(jù)相似推導(dǎo)，D函數(shù)在進化時間平滑框架下最大化可表達成

(12)

3　動態(tài)網(wǎng)絡(luò)社團結(jié)構(gòu)檢測進化譜分算法

筆者提出了新的基于模塊函數(shù)和模塊密度函數(shù)檢測動態(tài)復(fù)雜網(wǎng)絡(luò)中社團結(jié)構(gòu)的進化譜分算法．該算法基本框架是: 在最大化的CQ及CD值條件下，假設(shè)要在t時刻的動態(tài)網(wǎng)絡(luò)中尋求k個聚類中最優(yōu)的社團結(jié)構(gòu)．可通過計算得到相應(yīng)矩陣的前k個特征向量．對于每一個變量c(2≤c≤k)，可采用傳統(tǒng)的迭代方法尋找最優(yōu)的劃分c．詳細的進化譜分算法描述如下．

輸入R: 動態(tài)網(wǎng)絡(luò);

(2) 對矩陣Mt，通過子圖迭代方法計算它的k個特征值對應(yīng)的首個特征向量u1t，u2t，…，ukt．

(3) 構(gòu)建一個矩陣Xt∈Rn×k，其元素為[u1t，u2t，…，ukt]T．

(4) 對每一個c(2≤c≤kt)值，重復(fù)做:

(a) 生成一個來自矩陣Xt的首個c列的矩陣Uct．

(b) 使用k均值方法或其他基于向量的聚類算法聚類Uct的行向量．對于c=1，社團僅是t時刻動態(tài)網(wǎng)絡(luò)本身．

(5) 重復(fù)步驟4中的(a)和(b)，當(dāng)CQ或CD的值不再增大或達到最大迭代次數(shù)時，c的值就是t時刻網(wǎng)絡(luò)所對應(yīng)的最優(yōu)社團劃分數(shù)目．

(6) 返回．

4　算法檢驗

4.1　計算機合成動態(tài)網(wǎng)絡(luò)

該計算機合成的動態(tài)網(wǎng)絡(luò)是在網(wǎng)絡(luò)中社團結(jié)構(gòu)形成和毀滅的基礎(chǔ)上構(gòu)建的[13]．該動態(tài)網(wǎng)絡(luò)開始包含256個節(jié)點，劃分為4個社團結(jié)構(gòu)，每個社團結(jié)構(gòu)內(nèi)包含64個節(jié)點．社團內(nèi)每個節(jié)點的平均度為16，而且與社團外節(jié)點的連接邊數(shù)目為l，l為網(wǎng)絡(luò)拓撲調(diào)和參數(shù)，在實驗中可以調(diào)節(jié)．在t-1 時刻，從每個社團結(jié)構(gòu)中隨機選擇8個節(jié)點；在t時刻，由隨機選擇出的節(jié)點組成一個新的社團結(jié)構(gòu)，這個過程持續(xù)5個時間步．隨后，通過逆過程又將新社團結(jié)構(gòu)中的頂點返回到原始社團中去，同樣持續(xù)5個時間步．因此，在10個時間步上，該動態(tài)網(wǎng)絡(luò)的社團結(jié)構(gòu)數(shù)目分別為4，5，6，7，8，8，7，6，5，4．本實驗的目的在于檢測當(dāng)進化時間平滑框架中的平衡參數(shù)λ以及參數(shù)l變化時，如何影響著筆者提出的進化譜分算法檢測動態(tài)網(wǎng)絡(luò)中社團結(jié)構(gòu)的準(zhǔn)確性．為檢驗算法在動態(tài)網(wǎng)絡(luò)中檢測社團結(jié)構(gòu)的準(zhǔn)確性，可應(yīng)用歸一化互信息作為算法準(zhǔn)確性的評判標(biāo)準(zhǔn)．歸一化互信息值在0和1之間，值越大，暗示算法準(zhǔn)確性越高．

兩種函數(shù)的進化譜分算法在不同參數(shù)λ及l(fā)下檢測動態(tài)網(wǎng)絡(luò)社團的準(zhǔn)確性分別如圖1和圖2所示．圖1和圖2說明了兩種算法具有相似的表現(xiàn):當(dāng)參數(shù)λ增大時，兩種算法的準(zhǔn)確度都提升了．當(dāng)λ= 0.8時，兩個算法的準(zhǔn)確度最高．這是因為當(dāng)λ增大時，CS的相對重要性加強，提升了算法的準(zhǔn)確度．因此在實際中，通常取λ= 0.8．當(dāng)參數(shù)l增大時，暗示了網(wǎng)絡(luò)中社團愈加變得模糊，因此算法將愈來愈難檢測．然而，從圖1和圖2可看出，當(dāng)參數(shù)λ= 0.8時，無論在l=3 或l=5 時，兩種算法都有很好的準(zhǔn)確度．

圖1　Q的進化譜分算法在不同λ及l(fā)下檢測動態(tài)網(wǎng)絡(luò)社團的準(zhǔn)確性

圖2　D的進化譜分算法在不同λ及l(fā)下檢測動態(tài)網(wǎng)絡(luò)社團的準(zhǔn)確性

4.2　手機通話網(wǎng)絡(luò)

該手機通話網(wǎng)絡(luò)(http://www.cs.umd.edu/hcil/VASTchange08/)是虛擬Paraiso移動成員之間的手機通話動態(tài)網(wǎng)絡(luò)，并在2006年6月運行了10天．在手機通話網(wǎng)絡(luò)中，將每個成員個體作為節(jié)點，成員之間的通話作為邊．每一天，一個手機通話網(wǎng)絡(luò)被構(gòu)建．手機總數(shù)目是400．在該網(wǎng)絡(luò)中檢證筆者提出的算法檢測動態(tài)網(wǎng)絡(luò)中社團的正確率．

圖3　各種算法在手機通話網(wǎng)絡(luò)中的準(zhǔn)確性比較

因為真實的社團結(jié)構(gòu)未知，首先采用文獻[14]中的動態(tài)多目標(biāo)遺傳算法(DYNamic Multi-Objective Genetic Algorithm，DYNMOGA)在這個動態(tài)網(wǎng)絡(luò)中發(fā)現(xiàn)社團結(jié)構(gòu)，這些社團結(jié)構(gòu)可看成是對真實網(wǎng)絡(luò)的劃分．動態(tài)多目標(biāo)遺傳算法與筆者提出的算法在每一時刻之間的歸一化互信息值可看成算法的檢測社團準(zhǔn)確性．如圖3所示，筆者提出的兩種譜分算法能很好地識別社團結(jié)構(gòu)，準(zhǔn)確性比動態(tài)多目標(biāo)遺傳算法的高．特別地，Q函數(shù)的進化譜分算法及D函數(shù)的譜分算法得到的平均歸一化互信息值分別為0.63，0.64，而動態(tài)多目標(biāo)遺傳算法得到的平均歸一化互信息值為0.48．

5　總　　結(jié)

以上研究了在進化時間平滑框架下對模塊函數(shù)及模塊密度函數(shù)進行優(yōu)化的問題．通過兩種函數(shù)的優(yōu)化進程，論證了模塊函數(shù)及模塊密度函數(shù)可在進化框架下作為進化譜分聚類方法檢測動態(tài)網(wǎng)絡(luò)中社團結(jié)構(gòu)的理論可行性，在此理論上提出了檢測動態(tài)網(wǎng)絡(luò)社團結(jié)構(gòu)的進化譜分算法．在計算機合成的動態(tài)網(wǎng)絡(luò)及真實世界網(wǎng)絡(luò)中檢驗了該算法的合理性及準(zhǔn)確性，并與其他方法進行了比較．實驗結(jié)果顯示這種算法仍有很高的準(zhǔn)確性．在將來的研究中，可把其他社團評價函數(shù)或圖劃分函數(shù)納入進化時間平滑框架下，并進一步研究它們的特性．

參考文獻：

[2]NEWMAN M E J. Finding Community Structure in Networks Using the Eigenvectors of Matrices[J]. Physical Review E, 2006, 74(3): 036104.

[3]YU L, WANG B B, MA X K, et al. The Extraction of Drug-disease Correlations Based on Module Distance in Incomplete Human Interactome[J]. BMC Systems Biology, 2016, 10(111): 532-548.

[4]GUO X L, GAO L, LIAO Q, et al. Long Non-coding RNAs Function Annotation: a Global Prediction Method Based on Bi-colored Networks[J]. Nucleic Acids Research, 2013, 41(2): e35.

[5]NEWMAN M E J. Modularity and Community Structure in Networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2006, 103(23): 8577-8582.

[6]WANG P Z, GAO L, MA X K. Dynamic Community Detection Based on Network Structural Perturbation and Topological Similarity[J]. Journal of Statistical Mechanics: Theory and Experiment, 2017, 2017(1): 013401.

[7]YANG Y J, YU J X, GAO H, et al. Mining Most Frequently Changing Component in Evolving Graphs[J]. World Wide Web, 2014, 17(3): 351-376.

[8]YANG C, ZHANG X, ZHONG C, et al. A Spatiotemporal Compression Based Approach for Efficient Big Data Processing on Cloud[J]. Journal of Computer and System Sciences, 2014, 80(8): 1563-1583.

[9]CRAENEL B D, BERXL G. Regulatory Networks Defining EMT During Cancer Initiation and Progression[J]. Nature Review Cancer, 2013, 13: 97-110.

[10] FOLINO F, PIZZUTI C. An Evolutionary Multiobjective Approach for Community Discovery in Dynamic Networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(8): 1838-1852.

[11]黃偉華, 馬中, 戴新發(fā), 等. 一種特征加權(quán)模糊聚類的負載均衡算法[J]. 西安電子科技大學(xué)學(xué)報, 2017, 44(2): 127-132.

HUANG Weihua, MA Zhong, DAI Xinfa, et al. Fuzzy Clustering Based Load Balancing Algorithm with Feature Weighted[J]. Journal of Xidian University, 2017, 44(2): 127-132.

[12]李翠蕓, 王精毅, 姬紅兵, 等. 模型參數(shù)未知時的CPHD多目標(biāo)跟蹤方法[J]. 西安電子科技大學(xué)學(xué)報, 2017, 44(2): 37-41.

LI Cuiyun, WANG Jingyi, JI Hongbing, et al. CPHD Multi-target Tracking Algorithm with Unknown Model Parameters[J]. Journal of Xidian University, 2017, 44(2): 37-41.

[13]MA X K, DONG D. Evolutionary Nonnegative Matrix Factorization Algorithms for Community Detection in Dynamic Networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(5): 1045-1058.

[14]FOLINO F, PIZZUTI C. An Evolutionary Behavior of Interaction Graph[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26: 1838-1852.