進(jìn)化譜分算法檢測(cè)動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)

付立冬， 馬小科， 聶靖靖

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

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

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

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

1　相關(guān)工作

1.1　符號(hào)定義

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

(1)

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

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

(2)

1.3　進(jìn)化方法

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

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

(3)

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

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

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

首先在進(jìn)化時(shí)間平滑框架下優(yōu)化模塊函數(shù)Q，檢測(cè)動(dòng)態(tài)社團(tuán)需要的整個(gè)成本為

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

(4)

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

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

(5)

為了簡(jiǎn)化，重寫(xiě)Qt|Xt，有

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

(7)

(8)

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

(9)

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

(10)

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

(11)

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

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

(12)

3　動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)檢測(cè)進(jìn)化譜分算法

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

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

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

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

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

(a) 生成一個(gè)來(lái)自矩陣Xt的首個(gè)c列的矩陣Uct．

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

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

(6) 返回．

4　算法檢驗(yàn)

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

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

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

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

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

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

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

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

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

5　總　　結(jié)

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

參考文獻(xiàn)：

[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)模糊聚類(lèi)的負(fù)載均衡算法[J]. 西安電子科技大學(xué)學(xué)報(bào), 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ù)未知時(shí)的CPHD多目標(biāo)跟蹤方法[J]. 西安電子科技大學(xué)學(xué)報(bào), 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.